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

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

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

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

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

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

Вид учебной работы	Всего зачетных единиц (часов)	Семестр
		3
Общая трудоемкость дисциплины	3 (108)	3 (108)
Аудиторные занятия:	1,5 (54)	1,5 (54)
лекции	0,5 (18)	0,5 (18)
лабораторные работы	0,5 (18)	0,5 (18)
практические занятия	0,5 (18)	0,5 (18)
Самостоятельная работа:	1,5 (54)	1,5 (54)
изучение теоретического курса	0,5 (18)	0,5 (18)
подготовка к лабораторным работам	0,5 (18)	0,5 (18)
выполнение домашних заданий	0,25 (9)	0,25 (9)
текущий контроль	0,25 (9)	0,25 (9)
Вид промежуточного контроля	зачет	зачет

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

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

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

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

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

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

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

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

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

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

знать:

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

уметь:

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

владеть:

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

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

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