zhChinese    enEnglish
  ПМ-ПУ  » Образование  » Программы курсов » Теория информационно-логических систем

Теория информационно-логических систем

Общий курс

Составители: д.ф.-м.н., профессор Горьковой В.Ф., к.ф.-м.н., доцент Добрынин В.Ю.

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

  1. Биркгоф Т., Барти Т. Современная прикладная алгебра.
  2. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976. 595 с.
  3. Холл М. Теория групп. М.: Мир. 1962. 468 с.
  4. Харари Ф. Теория графов. М.: Мир. 1973. 336 с.
  5. Горьковой В.Ф. Графы Бержа: изоморфизм, декомпозиция, раскраски. СПб: Изд-во СПбГУ, 1994. 180 с.
  6. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979. 272 с.
  7. Мендельсон Э. Введение в математическую логику. 1984.
  8. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. 1977.
  9. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. 1995.
  10. Стенли Р. Перечислительная комбинаторика. 1990.
  11. Айгнер М. Комбинаторная теория. 1982.
  12. Сачков В.Н. Введение в комбинаторные методы дискретной математики. 1982.
  13. Мальцев А.И. Алгоритмы и рекурсивные функции. 1986.
  14. Булос Дж., Джеффри Р. Вычислимость и логика. 1994.
  15. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. 1982.
  16. Емеличев В.А. и др. Лекции по теории графов. 1986.
  17. Кнут Д. Искусство программирования. Т.1-3.

Глава 1. МНОЖЕСТВА И ФУНКЦИИ

1.1. Множества и подмножества.
1.2. Булевы алгебры.
1.3. Функции, обратные функции.
1.4. Функции из S в S.
1.5. Суммы, произведения и степени.
1.6. Аксиомы Пеано.
1.7. Принцип Дирихле, алгоритмы деления.

Глава 2. КОМБИНАТОРИКА

2.1. Комбинаторика множеств и мультимножеств.
2.1.1. Выборки с повторением и без повторений.
2.1.2. Биномиальные коэффициенты.
2.1.3. Рекуррентное соотношение для биномиальных коэффициентов.
2.1.4. Треугольник Паскаля, бином Ньютона.
2.1.5. Свойства биномиальных коэффициентов.
2.1.6. Мультиномиальные коэффициенты.
2.2. Разложения и разбиения натуральных чисел.
2.2.1. Число разложений.
2.2.2. Рекуррентная формула для числа разбиений.
2.3. Перестановки множеств и мультимножеств.
2.3.1. Группа перестановок, циклы.
2.3.2. Разложение перестановки на непересекающиеся циклы.
2.3.3. Тип перестановки, число перестановок заданного типа.
2.4. Принцип включения-исключения.
2.4.1. Задача о беспорядках.
2.4.2. Функция Эйлера.
2.4.3. Представление мощности объединения множеств через их пересечения.

Глава 3. МАТЕМАТИЧЕСКАЯ ЛОГИКА

3.1. Булева алгебра.
3.1.1. Функции алгебры логики. Формулы.
3.1.2. Реализация функций формулами. Эквивалентность формул.
3.1.3. Свойства элементарных функций.
3.1.4. Разложения булевых функций по переменным.
3.1.5. Дизъюнктивная и конъюнктивная нормальные формы, полином Жегалкина.
3.1.6. Принцип двойственности.
3.1.7. Полнота и замкнутость.
3.1.8. Замкнутые классы функций алгебры логики.
3.1.9. Необходимые и достаточные условия полноты системы функций алгебры логики.
3.1.10. Функции k-значной логики.
3.2. Исчисление высказываний.
3.2.1. Формальная система, аксиомы, теоремы и вывод.
3.2.2. Аксиомы и правило вывода исчисления высказываний.
3.2.3. Полнота исчисления высказываний.
3.2.4. Независимость системы аксиом исчисления высказываний.
3.3. Исчисление предикатов.
3.3.1. Язык исчисления предикатов.
3.3.2. Примеры описания математических понятий и утверждений на языке исчисления предикатов.

Глава 4. КОНЕЧНЫЕ АВТОМАТЫ

4.1. Двоичные элементы и состояния.
4.2. Конечные автоматы.
4.3. Покрытие и эквивалентность.
4.4. Эквивалентные состояния.
4.5. Процедура минимизации.
4.6. Неполностью описанные автоматы.
4.7. Автоморфизмы автоматов.

Глава 5. БИНАРНЫЕ ОТНОШЕНИЯ И ГРАФЫ

5.1. Матрицы отношений.
5.2. Алгебра отношений.
5.3. Частичное упорядочение.
5.4. Разбиения и отношения эквивалентности.
5.5. Классы вычетов и морфизмов.
5.6. Ориентированные графы.
5.7. Группы, примеры групп.
5.8. Представления графов.
5.9. Теорема об изоморфизме графов. Примеры.
5.10. Автоморфизм графов.
5.11. Теорема об автоморфизме графов.
5.12. Бинарные отношения и графы.
5.13. Операции над графами.
5.14. Операции над представлениями.
5.15. Раскраски. Элементарные преобразования. Минимальные раскраски.

Глава 6. ТЕОРИЯ СЛОЖНОСТИ

6.1. Формализация понятия алгоритма.
6.1.1. Машина Тьюринга.
6.1.2. Примеры машин Тьюринга.
6.1.3. Вычислимая функция.
6.2. Алгоритмически неразрешимые задачи
6.2.1. Продуктивность машины Тьюринга.
6.2.2. Максимальная продуктивность машины Тьюринга с n состояниями.
6.2.3. Доказательство алгоритмической неразрешимости задачи вычисления максимальной продуктивности машины Тьюринга с n состояниями.
6.2.4. Другие примеры алгоритмически неразрешимых задач.
6.3. Теория NP-полных задач
6.3.1. Понятие сложности алгоритма, классы сложности.
6.3.2. Полиномиальная сводимость задач.
6.3.3. Полиномиально разрешимые задачи.
6.3.4. NP-полная задача.
6.3.5. Доказательство полиномиальной разрешимости задачи 2-ВЫПОЛНИМОСТЬ.
6.3.6. Доказательство NP-полноты задачи 3-ВЫПОЛНИМОСТЬ.

Глава 7. АЛГОРИТМЫ

7.1. Алгоритмы на графах.
7.1.1. Минимальное остовное дерево и жадный алгоритм.
7.1.2. Алгоритм построения наибольшего паросочетания в двудольном графе.
7.1.3. Эйлеров цикл, построение эйлерова цикла; построение максимального потока в сети.
7.1.4. Задача коммивояжера: приближенные алгоритмы (алгоритм дерева) и метод ветвей и границ.
7.2. Методы сортировки и поиска.
7.2.6. Алгоритмы быстрой и пирамидальной сортировки.
7.2.7. Алгоритмы частичной сортировки; внешняя сортировка; деревья: AVL-дерево, B-дерево, R-дерево; методы хеширования.

Глава 8. КОДИРОВАНИЕ

8.1. Поля Галуа.
8.2. Смежные классы. Теорема о смежных классах. Примеры.
8.3. Векторные пространства и линейные алгебры.
8.4. Идеалы. Классы вычетов. Теоремы об идеалах.
8.5. Идеалы и классы вычетов многочленов.
8.6. Минимальная функция. Теоремы о минимальных функциях.
8.7. Мультипликативная группа поля Галуа.
8.8. Циклические коды. Матричное представление кодов.
8.9. Коды Боуза-Чоудхури и Рида-Соломона.
8.10. Метод исправления ошибок. Примеры.