Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"
Факультет Математики
Программа дисциплины Спецкурс «Доказательства и вычисления»
для направления 010100.62 «Математика» подготовки бакалавра
и направления 010100.68 «Математика» подготовки магистра
Автор программы:
, к. ф.-м. н., daniyar. *****@***com
Рекомендована секцией УМС по математике «___»____________ 2012 г.
Председатель
Утверждена УС факультета математики «___»_____________2012 г.
Ученый секретарь _____________________
Москва, 2012
Настоящая программа не может быть использована другими подразделениями университета и другими вузами без разрешения кафедры-разработчика программы.
1 Область применения и нормативные ссылки
Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности.
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 010100.62 «Математика» подготовки бакалавра, направления 010100.68 «Математика» подготовки магистра.
Программа разработана в соответствии с:
· ГОС ВПО;
· Образовательными программами: 010100.62 «Математика» подготовки бакалавра и 010100.68 «Математика» подготовки магистра.
· Рабочими учебными планами университета: по направлению 010100.62 «Математика» подготовки бакалавра и по направлению 010100.68 «Математика» подготовки магистра, специализации Математика, утвержденными в 2012 г.
2 Цели освоения дисциплины
Целями освоения дисциплины:
· получение представления о классических результатах в теории вычислимых функций и теории доказательств, без которых нельзя себе представить знакомство с математической логикой;
· умение решать простейшие задачи из этих областей.
3 Компетенции обучающегося, формируемые в результате освоения дисциплины
В результате освоения дисциплины студент должен:
· Знать точный смысл слов: вычислимая функция, разрешимая (неразрешимая) алгоритмическая проблема, m-сводимость, теорема Райса-Успенского, сложностные классы P и NP, формальная арифметика Пеано, первая терема Гёделя о неполноте, вторая теорема Гёделя о неполноте.
· Уметь пользоваться техникой сведения, а также применять теорему Райса-Успенского для доказательства неразрешимости простейших алгоритмических проблем.
· Уметь уметь строить формальные выводы простейших утверждений в арифметике Пеано.
· Приобрести начальный опыт использования техники «неподвижных точек» в общей теории алгоритмов и теории доказательств.
4 Место дисциплины в структуре образовательной программы
Настоящая дисциплина относится к циклу специальных дисциплин и блоку дисциплин по выбору.
Изучение данной дисциплины базируется на следующих дисциплинах:
· Логика и алгоритмы
Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями:
· Уметь реализовывать простые алгоритмы с помощью машин Тьюринга. Владеть методами доказательства теорем в исчислении высказываний и исчислении предикатов. Знать теорему о полноте исчисления предикатов первого порядка и уметь её применять.
Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин:
·
5 Тематический план учебной дисциплины
№ | Название раздела | Всего часов | Аудиторные часы | Самостоятельная работа | ||
Лекции | Семинары | Практические занятия | ||||
1 | Общая теория алгоритмов | 12 | 18 | |||
2 | Сложность вычислений | 8 | 12 | |||
3 | Теоремы Гёделя о неполноте | 20 | 20 | |||
Итого: | 90 | 40 | 50 |
6 Формы контроля знаний студентов
Тип контроля | Форма контроля | 1 год | 2 год | Параметры ** | ||||||
1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | |||
Текущий (неделя) | Коллоквиум | 8 | ||||||||
Итоговый | Экзамен | V | Например: письменный экзамен 90 мин |
Критерии оценки знаний, навыков
Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.
Коллоквиум: устный, на 1,5 часа. Задания носят исследовательский характер и предъявляют повышенные требования к теоретической подготовке студента.
Экзамен (зачет): письменная работа, состоящая из 4 задач на 1,5 часа. Студент должен продемонстрировать хорошее умение применять знания, полученные в курсе, к несложным конкретным задачам.
Порядок формирования оценок по дисциплине
Оценка за текущий, промежуточный и итоговый контроль выставляется по 10 балльной шкале.
Результирующая оценка за итоговый контроль складывается из результатов накопленной оценки, удельный вес которой составляет k1 = 0,5 и оценки за экзамен, удельный вес k2 = 0,5.
Оитоговый = 0,5 * Отекущий + 0,5 * Оэкзамен
Способ округления накопленной оценки промежуточного (итогового) контроля в форме зачета/экзамена в пользу студента.
Студент может получить возможность пересдать низкие результаты за текущий контроль.
В диплом ставится оценка за итоговый контроль, которая является результирующей оценкой по учебной дисциплине.
7 Содержание дисциплины
Раздел представляется в удобной форме (список, таблица). Изложение строится по разделам и темам. Содержание темы может распределяться по лекционным и практическим занятиям.
1. Раздел 1 Общая теория алгоритмов
Основные понятия теории вычислимых функций. Универсальная машина Тьюринга. Неразрешимость проблем остановки. Пример полугруппы, заданной порождающими и определяющими соотношениями, с неразрешимой проблемой равенства. Неразрешимость чистого исчисления предикатов в сигнатуре (1,+,=).
Универсальная вычислимая функция. Пример вычислимой функции, не имеющий всюду определенного вычислимого продолжения. Перечислимые рекурсивно неотделимые пары множеств. Существование главной универсальной вычислимой функции для класса вычислимых функций из N в N. Теорема Клини о неподвижной точке. Теорема Райса-Успенского.
Базовая литература: [1]
Дополнительная литература: [5], [7], [8]
2. Раздел 2. Сложность вычислений
Время и зона (память) работы машины Тьюринга. Классы P и NP. Сводимость по Карпу и NP-полные задачи. Ограниченной проблемы остановки для недетерминированных машин Тьюринга. NP-полнота ограниченной проблемы замощения и проблемы выполнимости булевых формул.
Базовая литература: [2]
Дополнительная литература: [6], [9]
3. Раздел 3. Теоремы Гёделя о неполноте
Формальная арифметика Пеано. Вычислимость и Σ-определимость в арифметике. Теорема о Σ1-полноте арифметики. Первая теорема Геделя о неполноте. Теорема Чёрча об алгоритмической неразрешимости арифметики и чистой логики предикатов. Рекурсивно неотделимые пары множеств, теорема Россера.
Формула доказуемости, лемма о неподвижной точке. Вторая теорема Гёделя о неполноте, теорема Лёба, теорема Тарского о невозможности определения истинности.
Базовая литература: [3], [4].
Дополнительная литература: [10]
8 Образовательные технологии
Методические рекомендации преподавателю
Методические указания студентам
9 Оценочные средства для текущего контроля и аттестации студента
Образец листочка с задачами (для самостоятельной работы студентов)
 |
Вопросы для оценки качества освоения дисциплины
1.Что такое вычислимая функция? Бывают ли функции, не являющиеся вычислимыми?
2. Что такое универсальная машина Тьюринга? Разрешима ли проблема остановки?
3. Содержится ли класс P в классе NP? А NP в P? Что такое NP-полная задача? Какие примеры задач такого типа вы знаете?
4. Сформулируйте первую теорему Гёделя о неполноте. Приведите пример пары перечислимых рекурсивно неотделимых множеств. Докажите теорему Гёделя-Россера.
5. Сформулируйте лемму о неподвижной точка для формальной арифметики. Докажите теорему Лёба.
Примеры заданий итогового контроля
Образец задания письменного экзамена:
1. Приведите пример универсальной вычислимой функции для класса вычислимых функций из N в N, которая не является главной.
2. Пусть языки K и L принадлежат NP. Верно ли, что их объединение принадлежит NP? А пересечение?
3. Доказать в арифметике Пено утверждение x(y+z) = xy + xz.
4. Найти арифметическую неподвижную точку формулы x^2 +1 = 0..
10 Учебно-методическое и информационное обеспечение дисциплины
Основная литература
1. , Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. М: МЦНМО, 2002. http://www. *****/free-books/shen/shen-logic-part3-2.pdf
2. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
3. Теоремы о неполноте. // Справочная книга по математической логике: В 4-х частях /Под ред. Дж. Барвайса. – Ч. IV. Теория доказательств и конструктивная математика: Пер. с англ.– М.: Наука, 1983. С. 9-53.
4. Введение в математическую логику. М.: Наука, 1984.
Дополнительная литература
5. , Плиско алгоритмов. М.: Издательский центр «Академия», 2009.
6. Крупский в сложность вычислений. М.: Фактриал Пресс, 2006.
7. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972.
8. Odifreddi, Piergiorgio (1999), Classical Recursion Theory, Vol. 1. Amsterdam: North Holland, 2nd ed.
9. Arora, Sanjeev and Barak, Boaz (2009), Computational Complexity: A Modern Approach. Cambridge University Press. http://www. cs. princeton. edu/theory/index. php/Compbook/Draft
10. Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic. Springer, 3rd ed. http://page. mi. fu-berlin. de/raut/logic3/announce. pdf
