ВУЗ:
Составители:
13
№ 14
с___по___
Основные положения теории алгоритмов.
Свойства, классификация, способы задания и
этапы полного построения алгоритмов.
Принцип логического программирования.
Алгоритмическая логика Ч.Хоара.
Ак. 2
Рекурсивные функции. По-
лучение производных час-
тично-рекурсивных и обще-
рекурсивных функции.
2
№ 15
с___по___
Рекурсивные функции, примитивно-
рекурсивные функции и операторы, схем-
ная интерпретация примитивной рекурсии,
частично рекурсивные и общерекурсивные
функции. Тезис Черча.
Ак. 2
№ 16
с___по___
Машина Тьюринга. Тезис Тьюринга. Ком-
позиция машин Тьюринга, универсальная
машина Тьюринга. Реализация алгоритмов
в машине Тьюринга. Нормальные алгорит-
мы.
Ак. 2
Реализация алгоритмов на
машинах Тьюринга, их ком-
позиции. Нормальные алго-
ритмы Маркова.
2
№ 17
с___по___
Элементы общей теории алгоритмов, нуме-
рация алгоритмов. Вычислимость и разре-
шимость. Понятие исчисления. Алгоритми-
ческая сводимость проблем. Проблема оста-
нова.
Ак. 2
№ 18
с___по___
Алгоритмически неразрешимые проблемы.
Проблема сложности алгоритмов. Класси-
фикация алгоритмов по сложности, эффек-
тивные алгоритмы.
Ак. 2
Оценка временной и емко-
стной сложности алгорит-
мов. Построение численных
и логических алгоритмов.
2
2. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ
Самостоятельная работа
студентов под контролем
преподавателя
Число
часов
Практические занятия
Число
часов
Контроль
усвоения
материала
Студенты приводят при-
меры простых и сложных
высказываний, получают
навыки формализации
фраз естественного языка,
решают практические
задачи по определению
значений истинности со-
ставных высказываний.
0,5 Логика высказываний. Ос-
новные логические опера-
ции.
1,5 контрольная
работа
Студенты приобретают
навыки по составлению
таблиц истинности слож-
ных высказываний, изу-
чают основные свойства
законов логики и правила
равносильных преобразо-
ваний.
0,5 Основные законы логики
высказываний.
1,5 контрольная
работа
Студенты изучают основ-
ные методы определения
тождественной истинно-
сти формул логики выска-
зываний, решают практи-
ческие задачи по приме-
нению правил логическо-
го вывода, приобретают
навык использования тео-
0,5 Доказательства тождест-
венной истинности формул.
Применение правил вывода
Теорема дедукции.
1,5 контрольная
работа
