«Математическая логика и теория алгоритмов»

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

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

знать основные понятия математической логики и теории алгоритмов,

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

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

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

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

Алгебра высказываний.

Перевод высказываний естественного языка на язык алгебры логики. Построение таблиц истинности. Приведение формул к КНФ, ДНФ, СДНФ, СКНФ. Интерпретация формул.

Исчисление высказываний.

Определения формулы, части формулы. Выводы формул. Доказательства выводимости формул.

Логика предикатов.

Перевод высказываний естественного языка на язык логики предикатов. Области действия кванторов. Интерпретация формул. Разрешающие функции.

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

Определения формулы, части формулы. Выводы формул. Доказательства выводимости формул. Приведение формул к нормальному виду.

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

Рекурсивные функции. Машина Тьюринга. Нормальные алгоритмы Маркова. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP – полные задачи.

Логические основы ЭВМ.

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

Аннотация примерной программы дисциплины

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

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

Задачи дисциплины развитие навыков работы с комбинаторными объектами и числами, графами, сетями и основами теории кодирования.

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

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

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

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

Содержание дисциплины: Бинарные отношения. Бинарные отношения и их свойства. Отношения эквивалентности и частичного порядка. Отношения Парето. Принятие решений при многих критериях. Булевы функции. Булевы функции. Элементарные булевы функции. Совершенные нормальные формы. Полином Жегалкина. Основы теории графов. Основные понятия теории графов. Матричное представление графов. Числовые характеристики графов. Деревья. Обходы графов. Эйлеровы и гамильтоновы циклы в графах. Планарность. Раскраска графов. Прикладные задачи и алгоритмы анализа графов. Двухполосные сети. Задача о наибольшем потоке. Оптимизационные задачи на графах. Алгоритмы их решения. Сетевое планирование. Критический путь и критическое время сетевого графа. Алгоритмы и автоматы. Оценки сложности алгоритмов. Классы Р и NР, подходы к решению NР –полных задач. Основы теории автоматов.

Аннотация примерной программы дисциплины