Аннотация дисциплины «Теория алгоритмов и математическая логика»

Общая трудоемкость изучения дисциплины составляет 3 зачетные единицы (108 часа).

Цели и задачи дисциплины

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

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

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

Основные дидактические единицы (разделы):

1. Дизъюнктивная и конъюнктивная нормальные формы.

2. Классическое исчисление высказываний. Аксиомы и правила вывода.

3. Теорема о дедукции. Теоремы полноты и непротиворечивости.

4. Предикаты и кванторы. Предикатные формулы.

5. Выполнимость, истинность. Логическая общезначимость.

6. Аксиомы и правила вывода исчисления предикатов 1-го порядка. Структура теории 1-го порядка.

7. Нормальные алгоритмы и машины Тьюринга. Вычисление словарных функций нормальными алгоритмам и машинами Тьюринга.

8. Универсальные алгоритмы. Теоремы сочетания. Разрешимость и перечислимость. Неразрешимые массовые проблемы.

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

знать:

- основные понятия теории алгоритмов: интуитивная концепция алгоритма, уточнения понятия алгоритма (машины Тьюринга и нормальные алгоритмы Маркова), понятия вычислимости, разрешимости, перечислимости; основные неразрешимые массовые проблемы;

уметь:

- доказывать формулы в исчислении высказываний и предикатов 1-го порядка; составлять программы машин Тьюринга и схемы нормальных алгоритмов для решения простых вычислительных задач;

владеть:

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

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

Изучение дисциплины заканчивается зачетом.