МОСКОВСКИЙ ГОРОДСКОЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ
ИНСТИТУТ МАТЕМАТИКИ И ИНФОРМАТИКИ
КАФЕДРА АЛГЕБРЫ, ГЕОМЕТРИИ И МЕТОДИКИ ИХ ПРЕПОДАВАНИЯ
Программа курса
«Теория алгоритмов»
Направление «Педагогическое образование», профиль «Математика», второй курс, четвёртый семестр, 2013/14 учебный год, 28 часов лекций, 14 часов практических занятий, коллоквиум, 1 контрольная работа, 2 проверки домашнего задания, экзамен.
Преподаватель: доцент
Содержаниек дисциплины и её разделы.Модуль 1. Понятие алгоритма. Алгоритм Евклида. Блок-схема и машинная программа. Ассоциативные исчисления, проблема эквивалентности. Машина Тьюринга. Функции вычислимые по Тьюрингу. Нормальные алгоритмы и нормально вычислимые функции. Нумерация машин Тьюринга. Универсальная машина Тьюринга.
Модуль 2. Тезис Чёрча. Пример неразрешимой алгоритмической проблемы. Неразрешимость проблем самоприменимости и применимости. Проблема переводимости. Алгоритмическая сводимость. Неразрешимость общей проблемы эквивалентности.
Модуль 3. Вычислимые числовые функции. Операция суперпозиции и оператор примитивной рекурсии. Определение класса примитивно рекурсивных функций. Операция минимизации и класс частично рекурсивных функций. Рекурсивные и рекурсивно перечисличмые множества и предикаты, операции над такими множествами и предикатами.
2. УЧЕБНО-МЕТОДИЧЕСКОЕ И
ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
ЛИТЕРАТУРА
а) основная литература
1. Мальцев и рекурсивные функции / . – М.: Наука 1965 – 392 с.
2. Трахтенброт и машинное решение задач / . М.: Государственное издательство физико-математической литературы, 1960 – 120 с.
б) дополнительная литература
Успенский о вычислимых функциях / . М.? Государственное издательство физико-математической литературы, 1960- 492 с. , Плиско алгоритмов / , . М.: Издательский центр «Академия», 2009 – 208 с.3. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ И ПЛАН ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ
КАЛЕНДАРНО-ТЕМАТИЧЕСКИЙ ПЛАН ОСВОЕНИЯ ДИСЦИПЛИНЫ
№ | Тема | Общая трудоемкость | Самостоятельная работа | Всего аудиторных часов | Лекции часов | Практические и семинарские занятия часов | Контроль самостоятельной работы |
1. | Модуль 1. Понятие алгоритма. Алгоритм Евклида. Блок-схема и машинная программа. Ассоциативные исчисления, проблема эквивалентности. Машина Тьюринга. Функции вычислимые по Тьюрингу. Нормальные алгоритмы и нормально вычислимые функции. Нумерация машин Тьюринга. Универсальная машина Тьюринга. | 36 | 10 | 22 | 14 | 8 | 4 |
Выполнение домашних заданий и контрольной работы | |||||||
2. | Модуль 2. Тезис Чёрча. Пример неразрешимой алгоритмической проблемы. Неразрешимость проблем самоприменимости и применимости. Проблема переводимости. Алгоритмическая сводимость. Неразрешимость общей проблемы эквивалентности. | 18 | 10 | 6 | 6 | - | 2 |
Собеседование по теоретическому материалу | |||||||
3. | Модуль 3. Вычислимые числовые функции. Операция суперпозиции и оператор примитивной рекурсии. Определение класса примитивно рекурсивных функций. Операция минимизации и класс частично рекурсивных функций. Рекурсивные и рекурсивно перечисличмые множества и предикаты, операции над такими множествами и предикатами. | 28 | 10 | 14 | 8 | 6 | 4 |
Собеседование по теоретическому материалу | |||||||
4. | Форма промежуточной аттестации – экзамен | 27 | |||||
5. | Итого за семестр (часов) | 108 | 30 | 42 | 28 | 14 | |
108 (часов) | 3 зач. ед | ||||||
ПЛАН ЛЕКЦИЙ
Модуль 1.
Лекция 1. Понятие алгоритма Алгоритм Евклида. Характерные черты алгоритма. ([1], с. 9-12).
Лекция 2.Блок-схема алгоритма. Автоматическое вычислительное устройство. Машинная программа для алгоритма Евклида. ([3], с. 46-60).
Лекция 3. Ассоциативные исчисления, проблема эквивалентности. Пример исчисления с разрешимой проблемой эквивалентности. ([3], с. 38-46).
Лекция 4. Машина Тьюринга. Реализация алгоритма Евклида в форме машины Тьюринга. ([1], с. 237-246).
Лекция 5. Определение функции, вычислимой по Тьюрингу. Всюду определяемые и частичные вычислимые по Тьюрингу функции. Нумерация машин и универсальная машина Тьюринга. ([3], с. 94-101).
Лекция 6. Нормальные алгоритмы Маркова. Функции, вычислимые по Маркову. ([1], с. 311-313).
Модуль 2.
Лекция 7. Тезис Чёрча. Пример неразрешимой алгоритмической проблемы. ([3], с. 90-94).
Лекция 8. Неразрешимость проблем применимости и переводимости. Алгоритмическая сводимость. Неразрешимость проблемы эквивалентности. ([3], с. 101-116).
Модуль 3.
Лекция 9. Вычислимые числовые функции. Операции суперпозиции и примитивной рекурсии. Класс примитивно рекурсивных функций. ([1], с. 32-42).
Лекция 10. Примитивная рекурсивность некоторых числовых функций. ([1], с. 38-40, 57-63).
Лекция 11. Операции суммирования и мультиплицирования над примитивно рекурсивными функциями. Кусочно заданная функция. ([1], с.52-55).
Лекция 12. Оператор минимизации. Класс частично рекурсивных функций. Общерекурсивные функции. Связь с функциями вычислимыми по Тьюрингу и по Маркову. ([1], с. 42-49).
Лекция 13. Невозможность универсальной функции в классах примитивно рекурсивных и общерекурсивных функций. Существование универсальной функции в классе частично рекурсивных функций (без доказательства). ([1], с. 105-106, 150).
Лекция 14. Разрешимые и перечислимые множества и предикаты. Операции над разрешимыми и перечислимыми множествами. Логические операции над разрешимыми предикатами. ([1], с. 91-94).
Основные теоретические вопросы
Модуль 1
1. Описание понятия алгоритма. Алгоритм Евклида.
2. Решение проблемы эквивалентности для конкретного ассоциативного исчисления.
3. Реализация алгоритма Евклида в автоматическом вычислительном устройстве.
4. Описание машины Тьюринга. Определение и при мер функции, вычислимой по Тьюрингу.
5. Реализация алгоритма Евклида в форме машины Тьюринга.
6. Нормальные алгоритмы и пример нормально вычислимой функции.
Модуль 2
7. Тезис Черча. Нумерация машин и пример невычислимой по Тьюрингу функции.
8. Универсальная машина Тьюринга.
9. Неразрешимость проблем применимости и самоприменимости.
10. Неразрешимость проблемы переводимости. Алгоритмическая сводимость.
11. Неразрешимость проблемы эквивалентности
Модуль 3
12. Операции подстановки и рекурсии. Примитивно рекурсивные функции.
13. Примитивная рекурсивность функций сложения, умножения, возведения. в степень, sgx, sgx, x – y, |x – y|.
14. Теорема о кусочно заданной функции.
15. Операция минимизации. Определение частично рекурсивных и общерекурсивных функций. Связь с функциями, вычислимыми по Тьюрингу и по Маркову.
16. Несуществоваие универсальной функции в классе примитивно рекурсивных и общерекурсивных функций.
17. Существование универсальной функции в классе частично рекурсивных функций.
18. Характеристическая функция множества. Разрешимые множества, операции над ними.
19.Сумма и пересечение перечисленных множеств.
20. Разрешимые предикаты. Логические операции над разрешимыми предикатами.
ПЛАН ПРАКТИЧЕСКИХ ЗАНЯТИЙ
№ | Тема занятия | Задачи для решения в аудитории | Задачи для самостоятельного решения |
1 | 2 | 3 | 4 |
Модуль 1 | |||
1 | Ассоциативные исчисления, решение проблемы эквивалентности. | ||
2 | Составление программы для машины Тьюринга. | ||
3 | Составление программы для машины Тьюринга. | ||
4 | Построение схемы нормального алгоритма | ||
5 | Построение схемы нормального алгоритма | ||
6 | Контрольная работа по темам занятий 1-5 | ||
Модуль 3 | |||
7 | Доказательство примитивной рекурсивности числовых функций |
Все задачи указываются по отдельному списку
Департамент образования города Москвы
Государственное бюджетное образовательное учреждение
высшего профессионального образования города Москвы
«МОСКОВСКИЙ ГОРОДСКОЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ»
Институт математики и информатики
Наименование дисциплины / курса | Уровень образования | Статус дисциплины в рабочем учебном плане | Количество зачетных единиц | Форма отчетности | Курс, семестр |
Теория алгоритмов | Бакалавриат | Вариативная часть | 3 | экзамен | 2 курс бакалавриата, 4 семестр |
Модуль 1. | ||||
Понятие алгоритма. Алгоритм Евклида. Блок-схема и машинная программа. Ассоциативные исчисления, проблема эквивалентности. Машина Тьюринга. Функции вычислимые по Тьюрингу. Нормальные алгоритмы и нормально вычислимые функции. Нумерация машин Тьюринга. Универсальная машина Тьюринга. | ||||
Тема или задание текущей аттестационной работы | Виды текущей аттестации | Аудиторная или внеаудиторная | Минимальное количество баллов | Максимальное количество баллов |
Посещение лекционных и семинарских занятий, дисциплинированность, культура поведения | Посещаемость | Аудиторная | 0 | 2 |
Активная работа на лекционных и семинарских занятиях – коммуникативная компетенция | Выступления, ответы на вопросы | Аудиторная | 0 | 6 |
Выполнение контрольных работ и отчеты по домашним заданиям – академическая компетенция (8 баллов за контрольную и 8 баллов за собеседование) | Письменная работа, собеседование. | Аудиторная и внеаудиторная | 0 | 16 |
Итого | 24 |
Модуль 2. | ||||
Тезис Чёрча. Пример неразрешимой алгоритмической проблемы. Неразрешимость проблем самоприменимости и применимости. Проблема переводимости. Алгоритмическая сводимость. Неразрешимость общей проблемы эквивалентности. | ||||
Тема или задание текущей аттестационной работы | Виды текущей аттестации | Аудиторная или внеаудиторная | Минимальное количество баллов | Максимальное количество баллов |
Посещение лекционных и семинарских занятий, дисциплинированность, культура поведения | Посещаемость | Аудиторная | 0 | 2 |
Активная работа на лекциях – коммуникативная компетенция | Выступления, ответы на вопросы | Аудиторная | 0 | 6 |
Ответы по домашнему заданию – академическая компетенция | Собеседование | Аудиторная и внеаудиторная | 0 | 10 |
Итого | 18 |
Модуль 3. | ||||
Вычислимые числовые функции. Операция суперпозиции и оператор примитивной рекурсии. Определение класса примитивно рекурсивных функций. Операция минимизации и класс частично рекурсивных функций. Рекурсивные и рекурсивно перечисличмые множества и предикаты, операции над такими множествами и предикатами. | ||||
Тема или задание текущей аттестационной работы | Виды текущей аттестации | Аудиторная или внеаудиторная | Минимальное количество баллов | Максимальное количество баллов |
Посещение лекционных и семинарских занятий, дисциплинированность, культура поведения | Посещаемость | Аудиторная | 0 | 2 |
Активная работа на семинарах и лекциях – коммуникативная компетенция | Выступления, ответы на вопросы | Аудиторная | 0 | 6 |
Собеседование по материалу модуля | Собеседование | Аудиторная | 10 | |
Итого | 18 | |||
Итого по трем модулям | 60 |
Необходимый минимум для допуска к промежуточной аттестации – 31 балл, экзамен – 70 баллов, 31-60 (тройка), 61-80 (четверка), 81-100 (пятёрка)
Дополнительные требования для студентов, отсутствующих на занятиях по уважительной причине: устное или письменное собеседование по тематике пропущенных занятий, выполнение заданий практических занятий, выполнение контрольных работ.
Форма промежуточной аттестации: экзамен – максимальное количество баллов 40 дополнительно к набранным.
Составитель доцент_______________________
Рабочая программа курса «Математическая логика» обсужден и утвержден на заседании кафедры алгебры, геометрии и методики их преподавания, протокол № 7 заседания кафедры от « 6 » февраля 2014 г.»
