Математическая логика и теория алгоритмов. Усенко О.А. - 5 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

5
Лекция 16. Машина Тьюринга. Тезис Тьюринга. Композиция машин Тьюринга, универсальная ма-
шина Тьюринга. Реализация алгоритмов в машине Тьюринга. Нормальные алгоритмы.
Лекция 17. Элементы общей теории алгоритмов, нумерация алгоритмов. Вычислимость и разреши-
мость. Понятие исчисления. Алгоритмическая сводимость проблем. Проблема останова.
Лекция 18.
Алгоритмически неразрешимые проблемы. Проблема сложности алгоритмов. Классифи-
кация алгоритмов по сложности, эффективные алгоритмы.
2.1.2. Основная литература:
1. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. – М.: Высшая школа , 1999.
2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы, построение и анализ. – М.: МЦ НМО, 1999.
3. Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2001.
4. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории
алгоритмов
. – М.: Физматлит, 2001.
5. Вишняков Ю.М. Введение в теорию алгоритмов. – Таганрог: Изд-во ТРТУ, 1995.
2.1.3. Дополнительная литература
1. Хопкрофт Дж., Матвани Р. и др. Введение в теорию автоматов и вычислений. – М., С.-П: 2002.
2. Обработка нечеткой информации в системах принятия решения /А.Н. Борисов, А.В. Алексеев, Г.В.
Меркулова и др. – М.: Радио и связь, 1989.
3. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. –
М.: Наука,
1987.
4. Кофман А. Введение в теорию нечетких множеств. – М.: Радио и связь, 1982.
5. Марков А.А., Нагорный Н.И. Теория алгоритмов. – М.: Наука, 1984.
6. Мелихов А.Н., Берштейн Л.С. Конечные четкие и расплывчатые множества. Ч.2. – Таганрог: Изд-
во ТРТИ, 1981.
7. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука
, 1987.
2.2. Лабораторные занятия
Программой не предусмотрены.
2.3. Практические занятия
На практических занятиях студенты решают задачи под руководством лектора по следующим разде-
лам теоретического курса:
Занятие 1. Переход от высказываний на естественном языке к формулам логики высказываний. Оп-
ределение истинности сложных составных высказываний.
Занятие 2.
Построение таблиц истинности. Основные законы логики и равносильности, преобразо-
вания логических формул.
Занятие 3. Доказательства тождественной истинности формул. Применение правил вывода для дока-
зательства теорем. Применение теоремы дедукции при доказательстве математических утверждений.
Занятие 4. Исчисление предикатов. Получение нормальной и предваренной нормальной формы фор-
мулы логики предикатов.
Занятие 5. Нечеткие высказывания. Построение
таблиц истинности и свойства основных соотноше-
ний нечеткой логики. Полиномиальные формы функции нечетких переменных.
Занятие 6. Нечеткие предикаты и кванторы. Нечеткая арифметика. Свойства и построение функций
принадлежности на основе экспертных оценок.
Занятие 7. Рекурсивные функции. Получение производных частично-рекурсивных и общерекурсив-
ных функции.
Занятие 8.
Реализация алгоритмов на машинах Тьюринга. Композиции машин Тьюринга. Построе-
ние алгоритмов в виде схем нормальных алгоритмов Маркова.
Занятие 9. Оценка временной и емкостной сложности алгоритмов. Построение численных и логиче-
ских алгоритмов.
2.4. Индивидуальные занятия

Страницы