Литература

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

3-й семестр 2012–2013, спец. ИУ8

ЛИТЕРАТУРА

Основная литература (ОЛ)

1.Белоусов А.И., Ткачев С.Б. Дискретная математика. М: Изд-во МГТУ им. Н.Э. Баумана, 2006. 744 с.

2.Яблонский С.В. Введение в дискретную математику. Изд. 2-е. М.: Наука, 1986. 384 с.

3.Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. Изд. 3-е. М.: Физматлит, 2005. 416 с.

4.Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. М.: Наука, 1990. 383 с.

5.Винберг Э.Б.. Курс Алгебры. М.: Факториал, 2002. 544 с.

6.Кострикин А.И. Введение в алгебру. Основы алгебры. М.: Физматлит, 1994. 320 с.

Дополнительная литература (ДЛ)

1. 
   Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир, 1976. 400 с.
   

7.Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975. 480 с.

8.Шиханович Ю.А. Введение в современную математику. М.: Наука, 1965. 376 с.

9.Сборник задач по алгебре / Под ред. А.И. Кострикина. М.: Наука, 1987. 352 с.

10.Лавров И.М., Максимова Л.М. Задачи по теории множеств математической логике и теории алгоритмов. М.: Наука, 1975. 240 с.

Методические пособия (МП)

1. 
   Белоусов А.И., Мартынов Б.В., Щетинин А.Н. Лекции по дискретной математике. М: изд-во МГТУ им. Н.Э. Баумана, 1994. 95 с.
   

11.Виноградова М.С., Ткачев С.Б. Булевы функции. М.: Изд-во МГТУ им. Н.Э. Баумана, 2007. 32 с.

Лекции

МОДУЛЬ 1: Элементы теории множеств и высшей алгебры

Лекция 1. Предмет и метод дискретной математики. Множества. Операции над множествами. Декартово произведение. Отображения. Метод характеристических функций. Композиция отображений. Обратное отображение. Теорема об обратном отображении.

ОЛ-1 1.1–1.2, Д1.2; ОЛ-6 гл. 1 §5.

Лекция 2. Бинарное отношение. Способы задания бинарных отношений. Отношения эквивалентности и фактор-множества. Частично упорядоченные множества. Супремум и инфимум. Мощность множества. Счетные и несчетные множества.

ОЛ-1 1.4–1.9; ОЛ-6 гл. 1 §6.

Лекция 3. Полугруппы, группы. Гомоморфизм и изоморфизм. Подгруппа. Циклическая подгруппа. Порядок элемента. Теоремы Кэли и Лагранжа.

ОЛ-1 2.1–2.2, 2.6–2.8, ОЛ-6 гл. 4 §§1–2.

Лекции 4–5. Полукольца, кольца и поля. Решение уравнения ax=b в группе и системы линейных уравнений над полем. Идемпотентные полукольца. Замкнутые идемпотентные полукольца. Решение систем линейных уравнений в замкнутых полукольцах.

ОЛ-1, 2.3–2.4, 2.9, 3.1–3.3.

МОДУЛЬ 2: Булевы функции

Лекции 6–7. Булевы функции, равенство функций, суперпозиция, формулы. Реализация булевых функций стандартными формулам: ДНФ, СДНФ, полиномы Жегалкина. Минимизация в классе ДНФ. Карты Карно, алгоритм Блейка.

ОЛ-1 6.1–6.6; ОЛ-2 ч. I гл. 1 §§1–4, ч. V гл.1.

Лекции 8–9. Полные системы булевых функций. Классы Поста. Критерий Поста. Схемы из контактных элементов. Метод каскадов синтеза схемы из контактных элементов.

ОЛ-1 6.7–6.8; ОЛ-2 ч. I гл. 1 §§5–7, ч. V гл. 2.

МОДУЛЬ 3: Введение в теорию графов

Лекция 10. Простые и ориентированные графы. Подграфы. Изоморфизм. Маршруты, пути, циклы, связность. Матричные представления графа. Деревья.

ОЛ-1 5.1–5.3; ОЛ-4 гл. I §§1–8, гл. II §1.

Лекции 11. Взвешенные графы. Остовное дерево минимального веса. теорема Кирхгофа (формулировка) и алгоритм Краскала.

ОЛ-1 5.4; ОЛ-4 гл. II §§2–3.

Лекция 12. Задача о достижимости и задача о кратчайшем пути в ориентированном графе. Алгоритмическое и алгебраическое решения. Методы систематического обхода вершин графа: поиск в глубину и поиск в ширину.

ОЛ-1 5.6.

МОДУЛЬ 4: Языки, автоматы и грамматики

Лекция 13. Алфавит, слово, язык. Операции над языками, регулярные языки и регулярные выражения. Мощность множества регулярных языков. Существование нерегулярных языков. Понятие конечного автомата-распознавателя как взвешенного орграфа. Язык. допускаемый КА.

ОЛ-1 7.1–7.4.

Лекция 14. Теорема Клини. Детерминизация КА. Регулярность дополнения регулярного языка. Лемма о разрастании для регулярных языков. Примеры нерегулярных языков.

ОЛ-1 7.5–7.6, 7.8.

Лекции 15. Конечные детерминированные автоматы с выходом. Задача о минимальном покрывающем автомате. Эквивалентные состояния. Процедура минимизации.

ОЛ-1 7.7, Д7.2.

Лекции 16–17. Языки порожденные грамматиками. Иерархия Хомского. Праволинейные грамматики и регулярные языки. НК грамматики и задача распознавания. Счетность множества языков, порожденных грамматиками, и существование языков не порождаемых грамматиками.

ОЛ-1 7.2, 7.4.

Практические занятия

МОДУЛЬ 1: Элементы теории множеств и высшей алгебры

Занятие 1. Множества. Доказательство теоретико-множественных равенств методом характеристических функций и методом двух включений. Отображения. Проверки биективности, инъективности, сюрьективности.

ОЛ-1 гл. 1 (вопросы и задачи) 1.1–1.8.

Занятие 2. Бинарные отношения, проверка их свойств, порядки, эквивалентности. Классы эквивалентности. Наибольшие и наименьшие элементы, максимальные и минимальные элементы.

ОЛ-1 гл. 1 (вопросы и задачи) 1.9–1.30.

Занятие 3. Группы, примеры, подгруппы, циклические подгруппы, порядки элементов. Группа перестановок. Решение уравнений в группах.

ОЛ-1 гл. 2 (вопросы и задачи) 2.1–2.8.

Занятие 4. Полукольца, кольца и поля. Решение уравнений и систем уравнений в полях. Решение уравнений в группах и систем уравнений в полях. Решение уравнения x=ax+b в полукольцах.

ОЛ-1 гл. 2 (вопросы и задачи) 2.9–2.21.

Занятие 5 (первая половина). Рубежный контроль по модулю 1.

МОДУЛЬ 2: Булевы функции

Занятие 5 (вторая половина). Булевы функции. СДНФ, СКНФ, полином Жегалкина, фиктивные переменные.

ОЛ-1 гл. 6 (вопросы и задачи) 6.4, 6.7, 6.8; ОЛ-3, гл. I § 1; МП-2.

Занятия 6-7. Сокращенная ДНФ (карты Карно и алгоритм Блейка). Тупиковые формы (функция Патрика). Минимизация ДНФ.

ОЛ-1 гл. 6 (вопросы и задачи) 6.11; ОЛ-3, гл. 1 § 1; МП-2.

Занятия 8–9. Полные системы булевых функций. Реализация стандартных булевых функций с помощью функций полной системы. Разбор типового Домашнего задания.

ОЛ-1 гл. 6 (вопросы и задачи) 6.13–6.25; ОЛ-3 гл. II; МП-2.

Занятие 10. Контактные схемы. Метод каскадов.

ОЛ-3 гл. X; МП-1.

Занятие 11. Рубежный контроль по модулю 2.

МОДУЛЬ 3: Введение в теорию графов

Занятие 12. Графы и матрицы. Вычисления в идемпотентных полукольцах. Поиск матриц достижимости и стоимости кратчайших путей.

ОЛ-1 гл. 5 (вопросы и задачи) 5.32–5.33; ОЛ-3 гл. VI §1; ОЛ-4 гл. I (упражнения).

Занятия 13. Алгоритмы на графах. Поиск в ширину. Поиск в глубину. Алгоритм Краскала.

ОЛ-1 гл. 5 (вопросы и задачи) 5.29–5.31,

Занятие 14. Рубежный контроль по модулю 3.

МОДУЛЬ 4: Языки, автоматы и грамматики

Занятие 15. Регулярные языки и регулярные выражения. Построение автомата по регулярному выражению. Вычисление языка автомата. Построение автомата по регулярному выражению.

ОЛ-1 гл. 7 (вопросы и задачи) 7.1–7.18, 7.29–7.33.

Занятие 16. Детерминизация автоматов. Автомат для дополнения языка. Примеры грамматик. Грамматика регулярного языка. Минимизация детерминированных автоматов с выходом/

ОЛ-1 гл. 7 (вопросы и задачи) 7.10, 7.14, 7.15, 7.16, 7.17, 7.20, 7.21.

Занятия 17. Рубежный контроль по модулю 4.

Материалы для подготовки

МОДУЛЬ 1: Элементы теории множеств и высшей алгебры

Вопросы для подготовки к рубежному контролю

12.Множества, равенство множеств, стандартные операции над множествами.

13.Характеристическая функция множества. Свойства характеристических функций.

14.Отображения множеств. Cюръективные, инъективные и биективные отображения. Операция суперпозиции отображений.

15.Обратное отображение. Единственность обратного отображения. Теорема существования обратного отображения (формулировка).

16.Бинарные отношения, отношения эквивалентности, классы эквивалентности, теорема о разбиении на классы эквивалентности (формулировка).

17.Отношения порядка, максимальный (минимальный) элемент, инфинум и супремум.

18.Мощность множества, счетные множества, их свойства, мощность отрезка.

19.Полугруппы, группы, подгруппы, гомоморфизмы, изоморфизмы.

20.Группа перестановок.

21.Циклическая группа. Циклическая подгруппа. Порядок элемента. Теорема Лагранжа.

22.Решения уравнений в группах.

23.Полукольца, кольца, делители нуля, поля, примеры конечных полей.

24.Решение систем уравнений в полях.

25.Идемпотентные полукольца, замкнутые полукольца, решение уравнения x=ax+b.

Типовые задачи рубежного контроля

1. 
   Записать характеристическую функцию симметрической разности множеств A и B через характеристические функции самих множеств.
   

26.Описать классы эквивалентности для отношения, заданного на множестве целых чисел, при котором два целых числа эквивалентны, если они дают одинаковый остаток при делении на число 6.

27.Найти минимальные (максимальные) элементы в заданном отношении порядка.

28.В группе перестановок указать все подгруппы, изоморфные группе вычетов (относительно сложения).

29.Найти порядок элемента 3 в мультипликативной группе вычетов по модулю 13.

30.Решить уравнение в заданной группе (группы перестановок, движений плоскости, множеств).

31.Решить систему уравнений в поле вычетов по модулю 7.

32.Решить уравнение в полукольце подмножеств.

МОДУЛЬ 2: Булевы функции

Вопросы для подготовки к рубежному контролю

1. 
   Булевы функции, способы задания, существенные и фиктивные переменные, отношение равенства.
   

33.Суперпозиция булевых функций. Формулы над множеством функций.

34.Стандартные формулы (СДНФ. СКНФ, полином Жегалкина).

35.Задача о минимизации ДНФ, меры сложности ДНФ, сокращенные ДНФ, алгоритм Блейка.

36.Тупиковые ДНФ, карта Карно для трех и четырех переменных. Теорема о тупиковости минимальной ДНФ. Функция Патрика.

37.Контактные схемы, метод каскадов.

38.Замкнутые классы: классы функций сохраняющих константу, класс самодвойственных функций, класс монотонных функций класс линейных функций.

39.Теорема Поста о полноте, построение заданной функции из функций полной системы.

Типовые задачи рубежного контроля

1. 
   Для булевой функции трех переменных с изображающим числом #01101110 найти СДНФ, СКНФ, полином Жегалкина.
   

40.Разложить данную булеву функцию трех переменных по первым двум переменным с помощью теоремы о разложении.

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

42.Найти сокращенную ДНФ для функции #0111 1001 0110 0101.

43.Нарисовать контактную схему данной булевой функции методом каскадов.

МОДУЛЬ 3: Введение в теорию графов

Вопросы для подготовки к рубежному контролю

1. 
   Графы, вершины, ребра, степень вершины, изоморфизмы графов.
   

44.Подграфы, пути, циклы, остовы, связный граф.

45.Графы и матрицы: матрица смежности, матрица Кирхгофа, матрица инцидентности, матрица ориентированной инцидентности.

46.Деревья.

47.Взвешенные графы. Задача о поиске остова наименьшего веса. Алгоритмы Краскала и Прима поиска остова наименьшего веса.

48.Ориентированные графы, матрица смежности, матрица достижимости, их связь. Вычисление матрицы достижимости.

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

50.Алгоритмы перечисления: поиск в глубину и поиск в ширину.

51.Алгоритм Дейкстры поиска кратчайшего пути.

Типовые задачи рубежного контроля

1. 
   Сколько компонент связности может иметь граф с 5 вершинами и двумя ребрами?
   

52.Сколько ребер может иметь неориентированное дерево с 2012 вершинами?

53.Сколько циклов может быть у связного графа с 2012 вершинами и 2012 ребрами?

54.Выполнить поиск в глубину (в ширину) для данного ориентированного графа.

55.Выполнить алгоритм Краскала для данного взвешенного графа.

56.Решив линейную систему уравнений в полукольце , вычислить первый столбец матрицы стоимостей кратчайших путей графа с матрицей смежности

МОДУЛЬ 4: Языки, автоматы и грамматики

Вопросы для подготовки к рубежному контролю

1. 
   Алфавит, слово, язык, множество языков над данным алфавитом, его мощность, операции над языками. Идемпотентное замкнутое полукольцо языков.
   

57.Регулярные операции и регулярные языки. Мощность множества регулярных языков.

58.Регулярные языки и автоматы. Построение языка по автомату и автомата по языку. Поиск языка автомата с помощью итерации матрицы смежности.

59.Детерминизация. Автомат для дополнения.

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

61.Языки, порожденные грамматиками. Иерархия Хомского.

62.Грамматики и автоматы-распознаватели. Место регулярных языков в Иерархии Хомского.

63.Существование нерегулярных контекстно-свободных языков.

Типовые задачи рубежного контроля

1. 
   Показать, что язык над алфавитом является регулярным. Построить для него автомат и грамматику. Является ли полученная грамматика контекстно-свободной?
   

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

65.Детерминизировать заданный автомат.

66.Построить автомат, без пустых переходов, реализующий объединение данных языков.

67.Построить грамматику, порождающую данный язык.

68.Найти язык, порожденный данной праволинейной грамматикой.