Рабочая программа дисциплины дискретная математика (наименование) Направление подготовки: 230100. 62 «Информатика и вычислительная техника»
Скачать 496.62 Kb.
|
| Тема 1. Основные определения теории графов. Лекционное занятие. Графы неориентированные, ориентированные и смешанные. Понятие инцидентности и смежности. Степени вершин. Текущий контроль. Введение вопросов по теме занятия во 2-й рубежный контроль. Тема 2. Виды графов. Понятия маршрута, цепи, цикла в графах. Связность графов. Лекционное занятие. Мультиграфы, псевдографы, полный граф, нуль-граф, взвешенный граф. Части графа: подграф, суграф. Графы и бинарные отношения. Некоторые виды графов: дерево и лес, двудольные графы. Изоморфизм графов. Планарные графы. Текущий контроль. Введение вопросов по теме занятия во 2-й рубежный контроль. Практическое занятие. Цель занятия: закрепление основных понятий теории графов, построение графов разных типов. Рассмотрение бинарных отношений на графах. План практического занятия. Решение задач:
Текущий контроль. Опрос знания лекционного материала в начале и в ходе решения задач. Введение вопросов по теме занятия во 2-й рубежный контроль. Тема 3. Числовые характеристики графа. Раскраска вершин графа. Метрика графов. Лекционное занятие. Цикломатическое число, числа внутренней и внешней устойчивости графа. Хроматическое число графа. Понятие расстояния между вершинами графа, матрица расстояний, диаметр, центр, радиус графа. Достижимость и контрдостижимость в графе. Текущий контроль. Введение вопросов по теме занятия во 2-й рубежный контроль. Практическое занятие. Цель занятия: овладение приемами определения числовых характеристик графа. План практического занятия. Решение задач:
Текущий контроль. Опрос знания лекционного материала в начале и в ходе решения задач. Введение вопросов по теме занятия во 2-й рубежный контроль. Тема 4. Способы задания графов. Лекционное занятие. Задание графа с точки зрения теории множеств перечислением множества вершин и дуг. Задание графа отображением его вершин. Матричные способы задания. Матрица смежности и ее свойства, способы представления графов в ЭВМ. Матрица инциденций. Текущий контроль. Введение вопросов по теме занятия во 2-й рубежный контроль. Практическое занятие. Цель занятия: получение практических навыков при построении графа по заданным матрицам смежности и инциденций и решении обратной задачи. План практического занятия. Решение задач:
Текущий контроль. Опрос знания лекционного материала в начале и в ходе решения задач. Введение вопросов по теме занятия во 2-й рубежный контроль. Тема 5. Операции над графами. Лекционное занятие. Объединение графов, пересечение графов, кольцевая сумма (сумма по модулю 2) двух графов. Удаление вершины. Удаление ребра или удаление дуги. Замыкание или отождествление. Стягивание. Текущий контроль. Введение вопросов по теме занятия во 2-й рубежный контроль. Практическое занятие. Цель занятия: получение практических навыков при построении графа по заданным операциям над исходными графами. План практического занятия. Решение задач:
Текущий контроль. Опрос знания лекционного материала в начале и в ходе решения задач. Введение вопросов по теме занятия во 2-й рубежный контроль. Тема 6. Нахождение кратчайшего пути в графе. Лекционное занятие. Постановка задачи. Правило для решения задачи частного вида, когда длина каждого ребра равна единице. Алгоритм Дейкстры. Правило расстановки пометок в алгоритме нахождения кратчайших путей во взвешенном графе. Правило для построения массива предков. Пример нахождения кратчайшего пути. Текущий контроль. Введение вопросов по теме занятия во 2-й рубежный контроль. Практическое занятие. Цель занятия: получение практических навыков при решении задач нахождения кратчайшего пути в графе. План практического занятия. Решение задачи нахождения кратчайшего пути в графе с помощью алгоритма Дейкстры. Текущий контроль. Опрос знания лекционного материала в начале и в ходе решения задач. Введение задач по тематике практического занятия в число задач индивидуального задания №2. Тема 7. Транспортные сети. Задача о наибольшем потоке. Лекционное занятие. Транспортные сети: основные понятия и определения. Сечение сети, пропускная способность сечения, понятие минимального разреза. Задача о наибольшем потоке. Метод расстановки пометок для решения задачи о максимальном потоке. Текущий контроль. Введение вопросов по теме занятия во 2-й рубежный контроль. Практическое занятие. Цель занятия: получение практических навыков при решении задач нахождения максимального потока в транспортной сети. План практического занятия. Решение задачи нахождения максимального потока в заданной транспортной сети с помощью алгоритма Форда-Фалкерсона. Текущий контроль. Опрос знания лекционного материала в начале и в ходе решения задач. Введение задач по тематике практического занятия в число задач индивидуального задания №2. 3. Задания, обеспечивающие достижение студентом комплексной цели модуля По разделу «Основы теории графов» студентам выдается индивидуальное задание №2, включающее две задачи: Задача №1. Используя алгоритм Дейкстры, найти кратчайший путь от заданной вариантом вершины до всех вершин в заданном графе. Веса ребер графа заданы матрицей. Задача №2. С помощью алгоритма Форда-Фалкерсона найти максимальный поток между вершиной с номером 1 (“источником”) и вершиной с максимальным номером (“стоком”). Пропускные способности ребер заданы матрицей. Критерии оценки индивидуального задания №2: выполнение задания оценивается числом баллов от 10 (минимум) до 18 (максимум). 4. Формы рубежного контроля Рубежная аттестация производится на основании оценки выполнения индивидуального задания №2 и оценки рубежного тестирования. 4.1. Тест 2-го рубежного контроля 4.1.1. Назначение теста: установление степени усвоения учебного материала раздела «Основы теории графов» 4.1.2. Продолжительность тестирования: два академических часа. 4.1.3. Тестовые задания: образец теста приведен в пп. 6.2.2. 4.1.3. Система оценивания результатов тестирования: максимум 15 баллов, минимум 8 баллов. 4.2. Результаты 2-го рубежного контроля
5. Список рекомендуемой литературы к модулю. 5.1. Основная литература к модулю 1. Спирина М.С., Спирин П.А. Дискретная математика: учебник. М.: Академия,2004. – стр. 69-96. 2. Судоплатов С.В., Овчинникова Е.В. Дискретная математика: учебник. М.: ИНФРА-М, 2005. – стр. 107-128. 5.2. Дополнительная литература к модулю 3. Кузнецов О.П. Дискретная математика для инженера. - СПб: Издательство “Лань”, 2004. – стр. 91-137. 4. Соболева Т.С., Чечкин А.В. Дискретная математика: учебник для студ. Вузов. – М: Академия, 2006. – стр 19-71. 5. Андерсон Джеймс. Дискретная математика и комбинаторика. М.: Вильямс, 2006. – стр. 244-290. Модуль (раздел) «Алгебра высказываний» 1. Комплексная цель модуля
2. Содержание модуля Тема 1. Логика. Основные понятия логики высказываний. Основные логические связки. Лекционное занятие. Понятие высказывания. Простые и составные высказывания. Основные логические связки: отрицание, дизъюнкция, конъюнкция, импликация, эквиваленция. Условные обозначения, таблицы истинности. Текущий контроль. Введение вопросов по теме занятия в 3-й рубежный контроль. Практическое занятие. Цель занятия: получение практических навыков при решении задач формализации сложных высказываний на основании заданных простых с использованием логических связок. Установление истинности формализованных сложных высказываний. План практического занятия. Решение задач перевода на язык алгебры логики заданных на естественном языке высказываний. Установление истинности или ложности заданных высказываний. Текущий контроль. Опрос знания лекционного материала в начале и в ходе решения задач. Введение вопросов по теме занятия в 3-й рубежный контроль. Введение задач по тематике практического занятия в число задач индивидуального задания №3. Тема 2. Формулы алгебры высказываний. Равносильность формул логики высказываний и равносильные преобразования. Лекционное занятие. Правило построения таблицы истинности на основании формулы алгебры логики. Понятие равенства логических формул. Основные свойства логических формул. Два основных способа доказательства равенства логических формул. Основные равносильности. Равносильности, выражающие одни логические операции через другие. Равносильности, выражающие основные законы алгебры логики. Текущий контроль. Введение вопросов по теме занятия в 3-й рубежный контроль. Практическое занятие. Цель занятия: получение практических навыков при решении задач на построение таблиц истинности на основании заданной формулы алгебры логики. Доказательство равенства логических формул с помощью равносильных преобразований. План практического занятия. Построение таблиц истинности для заданных формул алгебры логики. Решение задачи на доказательство равенства логических формул. Текущий контроль. Опрос знания лекционного материала в начале и в ходе решения задач. Введение вопросов по теме занятия в 3-й рубежный контроль. Введение задач по тематике практического занятия в число задач индивидуального задания №3. Тема 3. Функции алгебры логики. Полнота и замкнутость систем логических функций. Нормальные формы представления функций алгебры логики. Лекционное занятие. Определение функции алгебры логики. Способы задания функций алгебры логики: табличный и аналитический. Дизъюнктивная и конъюнктивная нормальная форма представления. Правила приведения функции алгебры логики к нормальной дизъюнктивной или конъюнктивной формам. Совершенные дизъюнктивная и конъюнктивная формы. Алгоритмы получения совершенных дизъюнктивных форм формам. Двойственность в алгебре высказываний: принцип двойственности и закон двойственности. Текущий контроль. Введение вопросов по теме занятия в 3-й рубежный контроль. Практическое занятие. Цель занятия: получение практических навыков при решении задач приведения заданной в произвольной форме функции алгебры логики к нормальным и совершенным нормальным формулам представления. План практического занятия. Решение задач на приведение исходной формулы алгебры логики к нормальным и совершенным формам. Текущий контроль. Опрос знания лекционного материала в начале и в ходе решения задач. Введение вопросов по теме занятия в 3-й рубежный контроль. Введение задач по тематике практического занятия в число задач индивидуального задания №3. 3. Задания, обеспечивающие достижение студентом комплексной цели модуля По разделу «Алгебра высказываний» студентам выдается индивидуальное задание №3, включающее две задачи: Задача №1. Формализовать заданное вариантом сложное высказывание: выделить и обозначить простые высказывания, обосновать применяемые логические связки, проверить истинность полученных сложных высказываний. Задача №2. Составьте таблицу истинности для заданной вариантом формулы алгебры логики. С помощью равносильных преобразований привести формулу сначала к дизъюнктивной нормальной форме, а затем к совершенной дизъюнктивной нормальной форме. Подтвердить правильность решений с помощью таблиц истинности. Критерии оценки индивидуального задания №3: выполнение задания оценивается числом баллов от 8 (минимум) до 15 (максимум). 4. Формы рубежного контроля Рубежный контроль проводится по материалу двух разделов: «Алгебра высказываний» и «Элементы комбинаторики». Информация о нем содержится в модуле «Элементы комбинаторики». 5. Список рекомендуемой литературы к модулю. 5.1. Основная литература к модулю 1. Спирина М.С., Спирин П.А. Дискретная математика: учебник. М.: Академия,2004. – стр. 131-170. 2. Судоплатов С.В., Овчинникова Е.В. Дискретная математика: учебник. М.: ИНФРА-М, 2005. – стр. 170-183. 5.2. Дополнительная литература к модулю 1.Яблонский С.В. Введение в дискретную математику. М.: Лань, 2010. – стр. 9-25. 4. Соболева Т.С., Чечкин А.В. Дискретная математика: учебник для студ. Вузов. – М: Академия, 2006. – стр. 112-125. 5. Андерсон Джеймс. Дискретная математика и комбинаторика. М.: Вильямс, 2006. – стр. 15-45. Модуль (раздел) «Элементы комбинаторики» 1. Комплексная цель модуля
2. Содержание модуля | ||||||||||||||||||
Похожие:
 | Рабочая программа дисциплины объектно-ориентированное программирование... Фгос впо к структуре и результатам освоения основных образовательных программ бакалавриата по Профессиональному циклу по направлению... | | Рабочая программа дисциплины web-технологии в разработке информационных... |
| Рабочая программа дисциплины экономика направление подготовки: 230100.... Программа предназначена для бакалавров по направлениям 230100. 62 информатика и вычислительная техника; все неэкономические направления,... | | Рабочая программа дисциплины системы и сети пакетной коммутации (сспк)... Рабочая программа предназначена для преподавания дисциплины «Системы и сети пакетной коммутации» студентам заочной сокращенной формы... |
| Рабочая программа дисциплины когнитивная психология (наименование... Об обеспечении требований пожарной безопасности в Кузнецовской средней общеобразовательной школе | | Рабочая программа дисциплины теория вероятностей и математическая... Данный приказ в течение 5 дней с момента его подписания |
| Программа разработана в соответствии с: Федеральному Государственному... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов для направления 230100. 68... |  | Программа дисциплины «философия» по направлениям подготовки 230100... Программа предназначена для преподавателей, ведущих данную дисциплину, ассистентов и студентов направлений 230100 «Информатика и... |
| Программа дисциплины «Социальная философия» по направлениям подготовки... Программа предназначена для преподавателей, ведущих данную дисциплину, ассистентов и студентов направлений 230100 «Информатика и... | | Программа дисциплины «управление ит проектами» Направление подготовки магистров 230100. 68 «информатика и вычислительная техника» |
| Рабочая программа учебной дисциплины Основы алгоритмизации и программирования... Фгос нпо, входящей в состав укрупненной группы профессий 230000 Информатика и вычислительная техника, по направлению подготовки 230100... | | Рабочая программа дисциплины технологии разработки информационных... Программа разработана доцентом каф. СаиТ, Свиридовым А. С., ассистентом каф. СаиТ, Кучеровым С. А |
| Программа дисциплины «Системы управления, ориентации и навигации»... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки специальности... | | Программа дисциплины «Лазерная гироскопия» для специальности 230100.... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки специальности... |
| Программа дисциплины «Навигационные системы» для специальности... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки специальности... | | Учебной дисциплины Фгос) по профессии начального профессионального образования (далее нпо), входящей в состав укрупненной группы профессий 230000 Информатика... |
