МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ
(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)

Главная  

О кафедре  

Программы  

Учебные пособия  

Публикации  

Гранты  

Экзамены  

Труды семинара  

:: Программы

По данному запросу не найдено записей!

» Версия для печати

Лекции

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

ЛЕКЦИЯ 1. Введение в математическую логику. Логика Буля, отношение эквивалентности. Логика высказываний, логика предикатов. Диаграмма Эйлера-Венна. Множество истинностных значений. Логическая переменная. Логическая функция. Отрицание логической переменной, логической функции. Таблица истинности логической функции. Операции булевой логики.

ЛЕКЦИЯ 2. Булевы функции от двух переменных. Дизъюнкция, ее таблица истинности. Конъюнкция, ее таблица истинности. Двойственность конъюнкции и дизъюнкции.

ЛЕКЦИЯ 3. Стрелка Пирса и штрих Шеффера, их таблицы истинности. Разность и импликация, их таблицы истинности. Симметрическая разность и эквивалентность, их таблицы истинности. Формы представления булевых функций.

ЛЕКЦИЯ 4. Понятие конституенты. Тавтология и противоречие. Совершенная дизъюнктивная нормальная форма, совершенная конъюнктивная нормальная форма и совершенная полиномиальная нормальная форма представления логических функций. Принцип двойственности в логике Буля. Нахождение булевой функции по ее таблице истинности.

ЛЕКЦИЯ 5. Методы доказательств в логике Буля. Основные законы логики Буля: законы идемпотентности, законы коммутативности, законы ассоциативности, законы дистрибутивности, законы нуля и единицы, законы поглощения, законы де Моргана, законы склеивания.

ЛЕКЦИЯ 6. Независимая система законов логики Буля: законы коммутативности, законы ассоциативности, законы дистрибутивности, законы нуля и единицы.

ЛЕКЦИЯ 7. Аксиоматический и конструктивный методы доказательств в логике Буля. Доказательства законов логики Буля: идемпотентности, поглощения, законов де Моргана, законов склеивания с помощью независимой системы законов логики Буля.

ЛЕКЦИЯ 8. Логика высказываний. Понятие высказывания. Создание сложных высказываний с помощью отрицания, дизъюнкции, конъюнкции, импликации и эквивалентности. Понятие логического круга. Строгая дизъюнкция. Язык и метаязык, объектные и субъектные высказывания. Парадокс лжеца. Парадокс Рассела о парикмахере.

ЛЕКЦИЯ 9. Построение доказательств в логике высказываний. Символ импликации в логике Буля и в логике высказываний. Посылка и заключение, понятие клаузы. Отношение порядка, законы рефлексивности, антисимметричности и транзитивности.

ЛЕКЦИЯ 10. Понятие предиката. Операции над предикатами и кванторами. Логика предикатов. Построение доказательств в логике предикатов.

ЛЕКЦИЯ 11. Сортировка данных и ее алгоритмы. Линейный выбор. Линейный выбор с обменом. Стандартный обмен (метод "пузырька"). Челночная сортировка. Сортировка Шелла. Сортировка по методу Неймана.

ЛЕКЦИЯ 12. Линейная вставка. Центрированная и двоичная вставки. Центрированная вставка. Двоичная вставка. Быстрая сортировка по методу Quicksort (метод Хоара). Быстрая сортировка по методу Heapsort (метод Уильямса).

ЛЕКЦИЯ 13. Поиск данных и его алгоритмы. Последовательный (линейный) поиск. Бинарный (двоичный) поиск. Интерполяционный поиск.

ЛЕКЦИЯ 14. Криптография. Понятие бита, механическая интерпретация понятия бита. Системы счислений. Хранение информации в ЭВМ. Элементы теории чисел. Общий делитель. Наибольший общий делитель. Взаимно простые числа. Определение наибольшего общего делителя с помощью алгоритма Евклида.

ЛЕКЦИЯ 15. Передача информации, кодирование. Кодировка и декодировка. Оптимальное, корректирующее и секретное кодирование. Информационная избыточность. Экономичность кода, средняя длина кодового слова. Кодирование по методу Фано. Префиксное кодирование и по методу Хаффмана. Оптимальное кодирование по методу Фано и Хаффмана.

ЛЕКЦИЯ 16. Код "Горячей линии Белый Дом - Кремль". Создание электронной подписи. Передача 8-битовой информации по 6-битовым каналам.

Практика

ЗАНЯТИЕ 1. Логика Буля. Логика высказываний, логика предикатов. Диаграмма Эйлера - Венна.

ЗАНЯТИЕ 2. Булевы функции от двух переменных. Нахождение булевой функции по ее таблице истинности.

ЗАНЯТИЕ 3. Методы доказательств в логике Буля. Основные законы логики Буля.

ЗАНЯТИЕ 4. Аксиоматический и конструктивный методы доказательств в логике Буля.

ЗАНЯТИЕ 5. Построение доказательств в логике высказываний. Построение доказательств в логике предикатов.

ЗАНЯТИЕ 6. Сортировка данных и ее алгоритмы.

ЗАНЯТИЕ 7. Поиск данных и его алгоритмы.

ЗАНЯТИЕ 8. Передача информации, кодирование.

Курсовые работы

Курсовых работ нет.

Рекомендуемая литература

Основная

1. Акимов О.Е. Дискретная математика: логика, группы, графы, М., Лаборатория базовых знаний, 2001.

2. Жемерев А. В. Введение в булеву логику. Методическое посо-бие для студентов 2-го факультета МАТИ. М., 2003.

3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М., Лаборатория базовых знаний, 2001.

4. Романовский И.В. Дискретный анализ, Невский диалект, 2001.

Дополнительная

5. Виленкин Н.Я, Ивашев-Мусатов О.С, Шварцбурд С.И. Алгебра и математический анализ для 11 класса, М., Просвещение, 1995.

6. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математи-ка для инженера. М., Энергоатомиздат, 1988.

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

8. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М., Изд. МАИ, 1993.

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

10. Яблонский С.В. Введение в дискретную математику, М., Выс-шая школа, 2001.