Программа дисциплины «Дискретная математика» - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Непрерывная математика Дискретная математика 3 1314.78kb.
Рабочая программа дисциплины математика (наименование дисциплины) 4 615.01kb.
К рабочей программе дисциплины «Математика» 6 класс Место дисциплины... 1 113.78kb.
Рабочая программа дисциплины математика направление подготовки 222000... 1 351.97kb.
Программа дисциплины Теория колебаний 1 201.41kb.
Программа дисциплины нис «Геометрия комплексных поверхностей» 1 72.89kb.
Программа дисциплины Спецкурс «Дополнительные главы теории чисел 1» 1 128.3kb.
Литература по математике (алгебра, геометрия, математический анализ... 1 224.35kb.
Перечень вопросов для подготовки к зачету по дисциплине «Дискретная... 1 13.02kb.
2Цели освоения дисциплины 3 306kb.
Программа дисциплины "Высшая математика" 1 328.14kb.
Основные комбинаторные объекты. Размещения. Число размещений 1 38.04kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Программа дисциплины «Дискретная математика» - страница №1/1




Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины «Дискретная математика»

для направления 010400.62 «Прикладная математика и информатика» подготовки бакалавра







Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"

Факультет Бизнес-информатики

Отделение прикладной математики и информатики



Программа дисциплины
Дискретная математика


для направления 010400.62 «Прикладная математика и информатика»

подготовки бакалавра

Автор программы: О.П. Кузнецов, д.т.н., проф. olkuznes@ipu.rssi.ru

С.О. Кузнецов, д.ф.-м.н., skuznetsov@hse.ru

Одобрена на заседании кафедры высшей математики на факультете экономики «___»____________ 20 г

Зав. кафедрой Ф.Т. Алескеров
Рекомендована секцией УМС [Введите название секции УМС] «___»____________ 20 г

Председатель [Введите И.О. Фамилия]


Утверждена Ученым Советом факультета бизнес-информатики «___»_____________20 г.

Ученый секретарь [Введите И.О. Фамилия] ________________________ [подпись]


Москва, 2011



Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы.

1Область применения и нормативные ссылки


Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности.

Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010400.62 «Прикладная математика и информатика» подготовки бакалавра, изучающих дисциплину «Дискретная математика».

Программа разработана в соответствии с:


  • Образовательным стандартом государственного образовательного бюджетного учреждения высшего профессионального образования «Государственный университет – Высшая школа экономики», в отношении которого установлена категория «Национальный исследовательский университет»;

  • Образовательной программой 010400.62, направление «Прикладная математика и информатика» подготовки бакалавра;

  • Рабочим учебным планом университета по направлению 010400.62 «Прикладная математика и информатика», утвержденным в 2011г.



2Цели освоения дисциплины


Целями освоения дисциплины «Дискретная математика» являются

знание понятий и методов основных разделов дискретной математики: теории множеств, комбинаторики, теории графов, математической логики и теории алгоритмов;



знакомство с прикладными задачами, при решении которых используются методы дискретной математики.


3Компетенции обучающегося, формируемые в результате освоения дисциплины


В результате освоения дисциплины студент должен:

  • Знать основные понятия и методы дискретной математики, необходимые для дальнейшего изучения последующих дисциплин, предусмотренных базовым и рабочим учебными планами;

  • Уметь пользоваться методами дискретной математики (в частности, методами комбинаторики, теории отношений, теории графов, математической логики) для формализации и решения прикладных задач, в том числе экономических;

  • Иметь представление о теоретических основах современных информационных технологий.



В результате освоения дисциплины студент осваивает следующие компетенции:


Компетенция

Код по ФГОС / НИУ

Дескрипторы – основные признаки освоения (показатели достижения результата)

Формы и методы обучения, способствующие формированию и развитию компетенции

Общенаучная

ОНК-1

Способность к анализу и синтезу на основе системного подхода

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-2

Способность перейти от проблемной ситуации к проблемам, задачам и лежащим в их основе противоречиям

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-3

Способность использовать методы критического анализа, развития научных теорий, опровержения и фальсификации, оценить качество исследований в некоторой предметной области

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-4

Готовность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования при работе в какой-либо предметной области

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-5

Готовность выявить естественнонаучную сущность проблем, возникающих в ходе профессиональной деятельности, привлечь их для решения соответствующий аппарат дисциплины

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-6

Способность приобретать новые знания с использованием научной методологии и современных образовательных и информационных технологий

Стандартные (лекционно-семинарские)

Общенаучная

ОНК-7

Способность порождать новые идеи (креативность)

Стандартные (лекционно-семинарские)

Инструментальные

ИК-2

Умение работать на компьютере, навыки использования основных классов прикладного программного обеспечения, работы в компьютерных сетях, составления баз данных

Стандартные (лекционно-семинарские)

Профессиональные

ПК-1

Способность демонстрации общенаучных базовых знаний естественных наук, математики и информатики, понимание основных фактов, концепций, принципов теорий, связанных с прикладной математикой и информатикой

Стандартные (лекционно-семинарские)

Профессиональные

ПК-2

Способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат

Стандартные (лекционно-семинарские)

Профессиональные

ПК-4

способность критически оценивать собственную квалификацию и её востребованность, переосмысливать накопленный практический опыт, изменять при необходимости вид и характер своей профессиональной деятельности

Стандартные (лекционно-семинарские)



4Место дисциплины в структуре образовательной программы


Настоящая дисциплина относится к циклу математических и естественнонаучных дисциплин, является базовой для подготовки бакалавра по направлению 010400.62 «Прикладная математика и информатика».
Изучение данной дисциплины базируется на следующих дисциплинах:

  • Математика в объеме средней школы

Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями:



  • Знаниями основных понятий и теорем математики в объеме средней школы;

  • Навыками решения типовых задач математики в объеме средней школы.

Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин:



  • Алгоритмы и структуры данных

  • Прикладная теория графов

  • Исследование операций

  • Анализ данных

  • Дискретная математика 2



5Тематический план учебной дисциплины




№ тем

Наименование тем

(с разбивкой по модулям)



Аудиторные часы

Контр. работы

Самост. занятия

Всего часов







лек-ции

семи-нары

всего










Первый модуль (32 часа)

1

Множества, функции, отношения

6

6

12




12

24

2

Комбинаторика

6

6

12




12

24

3

Элементы общей алгебры

4

4

8




10

18

Второй модуль (32 часа)

4

Математическая логика

(алгебраический подход)



6

6

12




16

28

5

Теория графов

10

10

20




24

44

Третий модуль (48 часов)

6

Теория алгоритмов

8

8

16




16

32

7

Теория формальных систем. Формальные языки и грамматики

6

6

12




12

24

8

Математическая логика (аксиоматический подход). Исчисление высказываний

6

6

12




16

28

9

Математическая логика (аксиоматический подход).

Исчисление предикатов



4

4

8

2

14

24


Четвертый модуль (40 часов)

10

Комбинаторные алгоритмы и их сложность

20

20

40




40

80




























Итого

76

76

152

2

172

326

6Формы контроля знаний студентов


Тип контроля

Форма контроля

1 год

Параметры

1

2

3

4

Текущий

(неделя)


Контрольная работа

1




1

1

Письменные работы в аудитории – 5-6 задач на 2,5 часа в последнюю неделю 1, 3 и 4 модулей

Домашнее задание

1

1

1




Письменные работы – 7-8 задач в предпоследнюю неделю 1, 3 и 4 модулей

Промежу­точный

Зачет




1







Письменная работа в аудитории – 5-6 задач на 2,5 часа

Итоговый

Экзамен










1

Письменная работа в аудитории на 2,5 часа



6.1Критерии оценки знаний, навыков


Для прохождения контроля студент должен продемонстрировать понимание основных определений, знание теорем и методов; умение решать типовые задачи, разобранные на семинарских занятиях.

Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.


7Содержание дисциплины

Тема 1. Множества, функции, отношения.


Множества - основные понятия. Диаграммы Венна. Операции над множествами: объединение, пересечение, дополнение. Векторы, их проекции. Прямое произведение множеств.

Соответствия и их свойства. Взаимно-однозначные соответствия. Мощности бесконечных множеств. Понятие функции. Обратные функции. Суперпозиции и формулы. Способы задания функций.

Общее понятие отношения. Бинарные отношения и их свойства (рефлексивность, симметричность, транзитивность). Отношение эквивалентности и классы эквивалентности. Отношение порядка. Линейный порядок и частичный порядок. Диаграммы Хассе. Лексикографический порядок. Ранжирование и проблема выбора.
Основная литература:


  1. Кузнецов О.П. Дискретная математика для инженера, изд. 3. Спб: Лань, 2004, гл.1.

  2. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2001, ч.1, пп.1-3.

Дополнительная литература:

  1. Колмогоров А.Н., Драгалин А.Г. Математическая логика. М.: Едиториал УРСС, 2004, гл.1, пп.3, 4.

  2. Столл Роберт Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968, гл.1.


Тема 2. Комбинаторика

Предмет комбинаторики. Правило суммы и правило произведения. Принцип включения и исключения. Размещения, перестановки, сочетания без повторений и с повторениями. Биномиальные коэффициенты и соотношения для них. Задачи перечисления. Подсчет числа функций с конечными областями определения. Рекуррентные соотношения и их решения. Понятие производящей функции.


Основная литература:

Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. М.: ФИМА, МНЦМО, 2006, гл.1, 2.


Тема 3. Элементы общей алгебры.

Алгебры и подалгебры. Свойства алгебраических операций: ассоциативность, коммутативность, дистрибутивность. Изоморфизм и гомоморфизм. Основные алгебраические структуры: полугруппы, группы, решетки. Связь решеток с частично упорядоченными множествами.



Основная литература:

Кузнецов О.П. Дискретная математика для инженера, изд. 3. Спб: Лань, 2004, гл.2.



Дополнительная литература:

Колмогоров А.Н., Драгалин А.Г. Математическая логика. М.: Едиториал УРСС, 2004, гл.1, п.5.



Тема 4. Математическая логика (алгебраический подход).


Основные понятия логики: высказывания и рассуждения. Основные логические связки. Алгебра высказываний. Логические функции и способы их задания - таблицы и формулы. Алгебраический подход к логике. Функциональная полнота. Булева алгебра и ее законы. Дизъюнктивные и конъюнктивные нормальные формы. Алгебра Жегалкина. Линейные и монотонные функции. Теорема о функциональной полноте.

Логика предикатов. Предметная область и предметные переменные. Кванторы общности и существования. Свободные и связанные переменные. Эквивалентные соотношения в логике предикатов. Общезначимые и противоречивые формулы. Запись утверждений естественного языка в логике предикатов.



Основная литература:

  1. Кузнецов О.П. Дискретная математика для инженера, изд. 3. Спб: Лань, 2004, гл.3.

  2. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2001, ч.2, пп.1, 2, 4.

Дополнительная литература:

  1. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М., Наука, 1977, гл.1, 2.

  2. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М., Наука, 1980, пп.1.1-1.3.


Тема 5. Теория графов.

Основные определения: неориентированные и ориентированные графы, мультиграфы и кратные ребра. Смежность и инцидентность. Способы представления графов. Матрица смежности. Графы и бинарные отношения. Изоморфизм графов. Полные графы и клики.

Пути, циклы, цепи, простые цепи в неориентированных графах. Связность и компоненты связности. Расстояния. Центр, радиус, диаметр графа. Обходы графов.

Виды связности в ориентированных графах: сильная связность, односторонняя связность. Ациклические графы и топологическая сортировка. Конденсация.

Матрицы графов и операции над ними.

Двудольные графы и формулировка задачи о паросочетаниях. Знаковые графы и понятие стабильности. Применение знаковых графов для формализации задач в социальной сфере.

Деревья и их свойства. Цикломатическое число. Приложения деревьев: иерархии, классификации. Обходы деревьев.

Оптимизационные задачи на графах. Кратчайшие пути и алгоритм Дейкстры. Потоки в сетях: определения, понятие увеличивающей цепи, алгоритм нахождения минимального потока. Сетевое планирование: ранние и поздние сроки, критические пути, виды резервов времени.

Основная литература:


  1. Кузнецов О.П. Дискретная математика для инженера, изд. 3. Спб: Лань, 2004, гл.4.

Дополнительная литература:

  1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. / Пер. с английского под ред. А.Шеня. - М.: МЦМНО, 2002, гл.VI.

  2. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М., Мир, 1980, гл.8.

  3. Свами М., Тхуласираман К. Графы, сети, алгоритмы. М., Мир, 1984, пп. 1.1–1.6, 2.1-2.4, 3.1, 3.2, 4.3, 4.4, 7.1-7.3, 8.5, 8.6, 9.1, 9.2.


Тема 6. Теория алгоритмов Универсальные модели. Общее понятие алгоритма. Требования к алгоритмам. Тезис Черча. Машины Тьюринга. Универсальная машина Тьюринга. Понятие рекурсии. Рекурсивные функции. Алгоритмические неразрешимости. Разрешимые и перечислимые множества.

Конечные автоматы. Основные определения. Примеры автоматных алгоритмов. Эквивалентность автоматов. Логические автоматы и логические схемы. Автоматные языки. Программная реализация автоматных алгоритмов.

Сети Петри и примеры их использования для моделирования параллельных процессов: схема обслуживания, распараллеливание и синхронизация, дедлок и зависание процесса. Проблема достижимости в сетях Петри.

Основная литература:

  1. Кузнецов О.П. Дискретная математика для инженера, изд. 3. Спб: Лань, 2004, гл.5.

  2. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М., Наука, 1980, гл.4, 5.

  3. Питерсон Дж. Теория сетей Петри и моделирование систем. М.:Мир,1984.


Дополнительная литература:

  1. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2001, ч.3, пп.1-3.

  2. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений., 2-е изд., : Пер. с англ. - М.: Издательский дом "Вильямс", 2002.


Тема 7. Теория формальных систем. Формальные языки и грамматики

Общие понятия о формальных системах и методах формализации. Понятие вывода в формальной системе.

Формальные грамматики. Контекстно-свободные грамматики. Синтаксический разбор. Алгоритмы синтаксического разбора. Эквивалентность грамматик.
Основная литература:


  1. Кузнецов О.П. Дискретная математика для инженера, изд. 3. Спб: Лань, 2004, гл.7, 8.

Дополнительная литература:

  1. Столл Роберт Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968.

  2. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений., 2-е изд., : Пер. с англ. - М.: Издательский дом "Вильямс", 2002.



Тема 8. Математическая логика (аксиоматический подход).

Логические исчисления и аксиоматические системы. Логическое следование, вывод, доказательство. Интерпретации и модели. Непротиворечивость, полнота и разрешимость логических исчислений. Логические теории. Теоремы Геделя. Метод резолюции для исчисления высказываний. Метод резолюции для логики предикатов первого порядка. Различные стратегии метода резолюций. Метод аналитических таблиц для исчисления высказываний и логики предикатов первого порядка. Неклассические логики. Логика и правдоподобные рассуждения.


Основная литература:

  1. Кузнецов О.П. Дискретная математика для инженера, изд. 3. Спб: Лань, 2004, гл.6.

  2. Мендельсон Э. Введение в математическую логику. М.: Наука, 1984.


Дополнительная литература:

  1. Вагин В.Н. и др. Достоверный и правдоподобный вывод в интеллектуальных системах. М.: Физматлит, 2004, пп.1.1-1.5, 4.1, 4.2, 10.2.

  2. Верещагин Н.К., Шень А. Языки и исчисления. М.: МЦНМО, 2002, гл.2, 4.

  3. Гладкий А.В. Математическая логика. М., Российск. гос. гуманит. ун-т, 1998, гл.5, 6.

  4. Столл Роберт Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968, гл.2, 3.

  5. Чень Ч., Ли Р. Математическая логика и доказательство теорем. Пер. с англ. - М.: Наука, 1983, гл.2-5.


Тема 9. Комбинаторные алгоритмы и их сложность

Алгоритмы сортировки. Асимптотический анализ алгоритмов, рекуррентные соотношения, корректность алгоритмов. Бинарные деревья поиска. Поиск в глубину (пример - построение остовного дерева). Поиск кратчайших путей в графе, алгоритм Дейкстры, поиск в ширину. Сложность алгоритмов поиска в деревьях различного вида. Алгоритмы поиска в trie-деревьях. Алгоритм построения транзитивного замыкания отношения. Алгоритм построения графа диаграммы (Хассе) для отношения порядка. Алгоритмы поиска максимальных паросочетаний.

Алгоритм построения эйлерова маршрута. Алгоритм построения циклического базиса графа. Эффективные алгоритмы для перечисления структур из большого семейства. Задержка и полиномиальная задержка. Кумулятивная задержка. Эффективные эвристики для приближенного решения трудноразрешимых задач.
Основная литература:


  1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К., Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. - М.: Вильямс, 2007, гл. 1-3, 8, 12, 13, 22-26.

Дополнительная литература:

  1. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М., Мир, 1980, гл. 4, 6, 8.

  2. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений., 2-е изд., : Пер. с англ. - М.: Издательский дом "Вильямс", 2002.

Тематика практических занятий (семинаров)

Семинары 1.1 - 1.3. Множества, функции, отношения.


Операции над множествами: объединение, пересечение, дополнение. Мощности множеств, получаемых в результате этих операций. Диаграммы Венна. Векторы, их проекции. Прямое произведение множеств. Мощность прямого произведения.

Соответствия и их свойства. Примеры соответствий с различными свойствами. Функции, их области определения и области значений. Обратные функции. Иллюстрация этих понятий на примерах нечисловых функций. Суперпозиции и формулы. Способы задания функций.

Бинарные отношения и их свойства (рефлексивность, симметричность, транзитивность). Примеры числовых и нечисловых отношений с различными свойствами. Операции над отношениями. Матричное задание отношений. Отношение эквивалентности и свойства его матрицы. Отношение порядка. Линейный порядок и частичный порядок. Диаграммы Хассе. Лексикографический порядок. Ранжирование и проблема выбора.

Семинары 1.4 - 1.5. Комбинаторика

Правило суммы и правило произведения. Связь этих правил с операциями над множествами. Принцип включения и исключения. Примеры задач на этот принцип. Размещения, перестановки, сочетания без повторений и с повторениями. Биномиальные коэффициенты и соотношения для них. Подсчет числа функций, определенных на конечных множествах. Методы перечисления комбинаторных объектов.



Семинары 1.6 - 1.7. Элементы общей алгебры.

Алгебры и подалгебры - примеры. Свойства алгебраических операций: ассоциативность, коммутативность, дистрибутивность. Изоморфизм и гомоморфизм. Примеры числовых и нечисловых алгебраических структур: полугрупп, групп, решеток. Связь решеток с частично упорядоченными множествами.


Семинары 2.1 - 2.3. Математическая логика (алгебраический подход).


Основные логические связки и запись высказываний с их помощью. Способы задания логических функций - таблицы и формулы. Вычисление функций, заданных формулами. Булева алгебра и ее законы. Методы перехода от таблиц к формулам и обратно. Дизъюнктивные и конъюнктивные нормальные формы. Эквивалентные преобразования булевых формул. Алгебра Жегалкина. Функциональная полнота. Линейные и монотонные функции. Теорема о функциональной полноте.

Логика предикатов. Предметная область и предметные переменные. Кванторы общности и существования. Свободные и связанные переменные. Эквивалентные соотношения в логике предикатов и их использование для преобразования формул логики предикатов. Запись математических утверждений и утверждений естественного языка в логике предикатов.



Семинары 2.4 - 2.8. Теория графов.

Способы представления графов и переход от одного представления к другому. Матрицы смежности для неориентированных и ориентированных графов. Графы и бинарные отношения; свойства отношений в терминах свойств графов, представляющих эти отношения.

Пути, циклы, цепи, простые цепи в неориентированных графах. Связность и компоненты связности. Расстояния. Центр, радиус, диаметр графа. Необходимые и достаточные условия существования эйлерова обхода и алгоритм его построения.

Построение примеров ориентированных графов с различными видами связности.

Необходимые и достаточные условия существования топологической сортировки и алгоритм ее построения.

Алгоритм построения конденсации ориентированного графа.

Матрицы графов и операции над ними. Матричные методы анализа графов.

Знаковые графы и понятие стабильности. Алгоритм Харари определения стабильности.

Деревья и их свойства. Цикломатическое число. Приложения деревьев: иерархии, классификации. Обходы деревьев.

Оптимизационные задачи на графах. Алгоритм Дейкстры нахождения кратчайших путей во взвешенных ориентированных графах. Алгоритм нахождения увеличивающей цепи в потоковой сети и алгоритм нахождения минимального потока. Методы анализа сетевых графиков: нахождение ранних и поздних сроков, критических путей, анализ резервов времени.



Семинары 3.1 - 3.3. Теория алгоритмов.

Примеры построения машин Тьюринга, реализующих простые алгоритмы, и протоколов их функционирования. RAM-машины и другие современные модели, эквивалентные машине Тьюринга. Примеры разрешимых и перечислимых множеств. Доказательство неразрешимости. Доказательство вычислимости. Иерархия неразрешимостей.



Семинары 3.4 - 3.7. Теория формальных грамматик и автоматов, сети Петри

Примеры формальных грамматик, контекстно-свободных грамматик. Классификация Хомского. Алгоритмы синтаксического разбора. Понятие вывода. Языки программирования как формальные системы.

Примеры конечных автоматов, автоматных алгоритмов и различных методов их описания.

Сети Петри и примеры их использования для моделирования параллельных процессов: схема обслуживания, распараллеливание и синхронизация, дедлок и зависание процесса.


Семинары 3.8-3.14. Математическая логика (аксиоматический подход). Примеры вывода в исчислении высказываний и исчислении предикатов. Примеры прикладных теорий. Понятия интерпретации, модели, непротиворечивости. Автоматические методы доказательства теорем. Метод резолюции для исчисления высказываний и логики предикатов первого порядка. Разновидности стратегий метода резолюций.

Метод аналитических таблиц. Понятие о неклассических логиках. Примеры логического моделирования правдоподобных рассуждений.


Семинары 4.1-4.4. Комбинаторные алгоритмы и их сложность.

Алгоритмы сортировки. Корректность алгоритмов. Схема Горнера. Бинарные деревья поиска, обход дерева. Поиск в графе: поиск в глубину, топологическая сортировка, кратчайшие пути в ориентированных ациклических графах. Алгоритмы поиска максимальных паросочетаний. Сложность алгоритмов поиска в деревьях различного вида. Поиск в trie-деревьях. Эффективные алгоритмы для перечисления структур из большого семейства: иллюстрация понятий (кумулятивной) задержки и полиномиальной (кумулятивной) задержки. Эффективные эвристики для приближенного решения трудноразрешимых задач.



8Оценочные средства для текущего контроля и аттестации студента

8.1Тематика заданий текущего контроля


Задание 1 (модуль 1).

  1. Какие из операций над множествами (объединение, пересечение, разность) ассоциативны и какие коммутативны? Обосновать ответ.

  2. Сколько разных слов получится при перестановке букв в слове КРОКОДИЛ, если слова должны начинаться с гласной буквы и оканчиваться на согласную?

  3. Множество M содержит 3 элемента, а N – 4 элемента, К – 5 элементов. Сколько существует функций типа f: NM К?

  4. Множества A, B, C содержат 2, 4 и 6 элементов, соответственно, причем A B C. Сколько элементов может содержать множество Х, если B \ X = A, BX = C? Как его выразить с помощью A, B, C и операций над множествами?

  5. Доказать, что множество целых степеней 10 образует группу по умножению. Привести пример другой группы, которой она изоморфна.


Задание 2 (модуль 2).

1. Множество М определено как множество двоичных наборов, на которых логическая функция f(a, b, c) равна 1. Верно ли для М утверждение? (Отношение  понимается как отношение частичного порядка на множестве двоичных наборов.)

2. Для функции, заданной таблицей, получить полином Жегалкина; путем подстановок констант получить отрицание и конъюнкцию или дизъюнкцию.

3. Найти диаметр, радиус и центры графа, заданного списком ребер.

4. В графе, заданном матрицей, найти кратчайший путь из вершины 1 в вершину 8, показав все шаги алгоритма.
Задание 3 (модуль 3).

1. Построить машину Тьюринга, которая для любого слова  в алфавите {a, b, c} сохраняет в  в том же порядке буквы a, b и удаляет c, не оставляя пробелов. Написать протокол построенной машины для слова acbbc.

2. Построить многоленточную машину Тьюринга, которая вычисляет ту же функцию.

3. Перечислимо ли множество машин Тьюринга, состояния и символы ленты которых выбираются из заданных алфавитов? Если нет, обосновать ответ. Если да, описать процедуру перечисления.

4.Построить минимальный автомат для автомата, заданного таблицей переходов.
Задание 4 (модуль 3).


  1. Построить дерево вывода для цепочки в заданной грамматике типа 2.

  2. Доказать или опровергнуть тождественную истинность высказывания методом резолюций.

  3. Доказать или опровергнуть тождественную истинность высказывания методом семантических таблиц.


Задание 5 (модуль 4).

1. Верно ли, что массив из n чисел, каждое из которых равно -1, 0 или 1, можно отсортировать за время O(n) в худшем случае? Объясните ответ.

2. Решите рекуррентное соотношение: Результатом должна быть асимптотически точная оценка (в терминах Θ).

3. Покажите, что проверить, является ли последовательность вершин простым путем с числом ребер не более m в заданном графе, можно за время, полиномиальное от размера графа.


Задание 6 (модуль 4).

  1. Дан отсортированный массив A, состоящий из n различных целых чисел, некоторые из которых могут быть отрицательными. Приведите эффективный алгоритм нахождения индекса i, такого что A[i] = i, если такой индекс существует. Если таких индексов несколько, алгоритм должен вернуть любой из них.

  2. Покажите, что проверить, является ли последовательность вершин гамильтоновым путем между двумя заданными вершинами графа, можно за время, полиномиальное от размера графа.

  3. Решите рекуррентное соотношение: T(n) = 8T(n / 2) + n3. Результатом должна быть асимптотически точная оценка (в терминах Θ).

В некоторой программе осуществляется n последовательных вызовов операции f. Известно, что эта последовательность вызовов занимает время Θ(n log n) в худшем случае. Каким может быть максимальное время выполнения (в терминах Θ) одной операции f из этой последовательности? Объясните ответ.

8.2Вопросы для оценки качества освоения дисциплины


  1. Может ли отношение эквивалентности быть одновременно и отношением порядка?

  2. Каковы свойства графов, представляющих отношения эквивалентности?

  3. Что такое диаграммы Хассе и к какому виду относятся их графы?

  4. Каково число различных функций типа АВ3С, если А= 3, В= 4, С= 2?

  5. Какова мощность множества логических функций 5 переменных, которые принимают значение 1 только на тех наборах значений переменных (но необязательно на всех), которые содержат ровно 2 единицы?

  6. Как связано понятие функциональной полноты с реализацией логических функций логическими схемами?

  7. Может ли радиус графа равняться его диаметру?

  8. Какие виды связности возможны в ориентированных деревьях?

  9. Можно ли представить неориентированное дерево в виде двудольного графа?

  10. Может ли разрешимое множество не быть перечислимым?

  11. Что такое вывод в формальной системе?

  12. Каким формальным языкам соответствуют автоматы?

  13. Возможен ли полиномиальный алгоритм для NP-полной задачи?

Можно ли задачу о выполнимости КНФ свести к задаче о максимальном паросочетании в двудольном графе за полиномиальное время?

8.3Примеры заданий промежуточного /итогового контроля





        1. Может ли рефлексивное и транзитивное отношение быть несимметричным? Если да, приведите пример; если нет, докажите это.

        2. Для заданной логической функции 4-х переменных проверить, образует ли она полную фнкуиональную систему.

        3. Построить топологическую сортировку для заданного графа.

        4. Построить дерево вывода для слова aaabbbb.



9Порядок формирования оценок по дисциплине


Итоговая оценка Оитог по 10-балльной шкале формируется как сумма пяти оценок: оценок контрольных за 1-й, 2-й и 4-й модули; оценки зачета в 3-м модуле и оценки за экзамен в 4-м модуле. Веса всех оценок одинаковы и равны 0,21:

Оитог. = 0,2 Оконтр1 + 0,2 Озачет2 + 0,2 Оконтр3 + 0,2 Оконтр4 + 0,2 Оэкз

Оценка за экзамен – блокирующая.

Перевод в 5-балльную шкалу осуществляется по правилу:


Оценка по 10-балльной шкале

Оценка по 5-балльной шкале

1, 2, 3

неудовлетворительно

4, 5

удовлетворительно

6, 7

хорошо

8, 9, 10

отлично

Оценка за зачет формируется на основе письменной работы, состоящей из 5 (как правило) задач. Каждая задача оценивается по 10-балльной системе, общая оценка равна 1/5 суммы оценок задач с точностью до десятых. Домашнее задание оценивается аналогично. Не сдавшим домашнее задание или получившим по нему оценку ниже 4,0 оценка за зачет снижается на 1 балл.

Округление до целого числа десятичных баллов производится по следующим правилам:



  1. Округление в пределах одной пятибалльной оценки производится по обычным правилам округления (например, 6,6  7).

  2. Округление, переводящее в следующую пятибалльную оценку, производится только в индивидуальном порядке с учетом активности на семинарах с добавлением не более 0,2 (по принципу «четыре с минусом не равно три с плюсом»).

Например, оценка 7,8 для активного студента может быть округлена до 8,0;

для пассивного студента 7,9  7;

оценка 7,7 во всех случаях равна 7.

10Учебно-методическое и информационное обеспечение дисциплины

10.1Базовый учебник


Кузнецов О.П. Дискретная математика для инженера, изд. 3. Спб: Лань, 2004.

10.2Основная литература


  1. 1. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. М.: ФИМА, МНЦМО, 2006.

  2. 2. Гэри М., Джонсон Д, Вычислительные машины и трудно решаемые задачи. М., Мир, 1982.

3. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 2001.

4. Мендельсон Э. Введение в математическую логику. М.: Наука, 1984.

5. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К., Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. - М.: Вильямс, 2007.

6. Питерсон Дж. Теория сетей Петри и моделирование систем. М.:Мир,1984.

7. Свами М., Тхуласираман К. Графы, сети, алгоритмы. М., Мир, 1984.

10.3Дополнительная литература


1. Булос Дж., Джеффри Р. Вычислимость и логика. М., Мир, 1994.

2. Вагин В.Н. и др. Достоверный и правдоподобный вывод в интеллектуальных системах. М.: Физматлит, 2004.

3. Верещагин Н.К., Шень А. Языки и исчисления. М.: МНЦМО, 2002. 2-е издание, стереотипное.

4. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М., Наука, 1977.

5. Гладкий А.В. Математическая логика. М., Российск. гос. гуманит. ун-т, 1998.

6. Колмогоров А.Н., Драгалин А.Г. Математическая логика. М.: Едиториал УРСС, 2004.

7. Крупский В.Н. Введение в сложность вычислений. – М.: Факториал Пресс, 2006.

8. Майника Э. Алгоритмы оптимизации на сетях и графах. М., Мир, 1981.

9. Новиков Ф. Дискретная математика для программистов. Спб, Питер, 2000.

10. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М., Мир, 1980.

11. Столл Роберт Р. Множества. Логика. Аксиоматические теории. М.: Просвещение, 1968.

12. Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. – 2-е изд. - М, 2007.

13. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений., 2-е изд., : Пер. с англ. - М.: Издательский дом "Вильямс", 2002.

14. Чень Ч., Ли Р. Математическая логика и доказательство теорем. Пер. с англ. - М.: Наука, 1983.



15. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М., Наука, 1980.


1 Равенство весов объясняется тем, что, на наш взгляд, знания в любом модуле одинаково важны, независимо от того, оценивались ли они зачетом или контрольной.




izumzum.ru