Программа дисциплины Спецкурс «Доказательства и вычисления» для направления 010100. 62 «Математика» - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Программа дисциплины Спецкурс «Теория представлений в нецелых размерностях»... 1 99.85kb.
Программа дисциплины Спецкурс «Дополнительные главы теории чисел... 1 128.84kb.
Программа дисциплины Спецкурс «Топологические векторные пространства»... 1 203.9kb.
Программа дисциплины Спецкурс «Алгебраические кривые: по направлению... 1 104.82kb.
Программа дисциплины Спецкурс «Гомологическая алгебра» для направления... 1 104.23kb.
Программа дисциплины Спецкурс для направления 010100. 62 «Математика»... 1 217.46kb.
Программа дисциплины нис «Модулярные формы» для направления 010100. 1 157.14kb.
Программа дисциплины нис для направления 010100. 62 «Математика»... 1 186.36kb.
Программа дисциплины Математические методы естественных наук для... 1 171.98kb.
Программа дисциплины «Римановы поверхности» 1 99.35kb.
Программа дисциплины «Теория чисел» 1 152.98kb.
Математическая логика 1 28.96kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Программа дисциплины Спецкурс «Доказательства и вычисления» для направления 010100. - страница №1/1




Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины Спецкурс «Доказательства и вычисления» для направления

010100.62 «Математика» подготовки бакалавра и

010100.68 «Математика» подготовки магистра





Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"

Факультет Математики

Программа дисциплины Спецкурс «Доказательства и вычисления»

для направления 010100.62 «Математика» подготовки бакалавра

и направления 010100.68 «Математика» подготовки магистра

Автор программы:

Шамканов Д.С., к.ф.-м.н., daniyar.shamkanov@gmail.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 мин

1 коллоквиум

6.1Критерии оценки знаний, навыков



Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.

Коллоквиум: устный, на 1,5 часа. Задания носят исследовательский характер и предъявляют повышенные требования к теоретической подготовке студента.

Экзамен (зачет): письменная работа, состоящая из 4 задач на 1,5 часа. Студент должен продемонстрировать хорошее умение применять знания, полученные в курсе, к несложным конкретным задачам.

6.2Порядок формирования оценок по дисциплине


Оценка за текущий, промежуточный и итоговый контроль выставляется по 10 балльной шкале.
Результирующая оценка за итоговый контроль складывается из результатов накопленной оценки, удельный вес которой составляет k1 = 0,5 и оценки за экзамен, удельный вес k2 = 0,5.

Оитоговый = 0,5 * Отекущий + 0,5 * Оэкзамен

Способ округления накопленной оценки промежуточного (итогового) контроля в форме зачета/экзамена в пользу студента.


Студент может получить возможность пересдать низкие результаты за текущий контроль.
В диплом ставится оценка за итоговый контроль, которая является результирующей оценкой по учебной дисциплине.

7Содержание дисциплины


Раздел представляется в удобной форме (список, таблица). Изложение строится по разделам и темам. Содержание темы может распределяться по лекционным и практическим занятиям.


  1. Раздел 1 Общая теория алгоритмов

Основные понятия теории вычислимых функций. Универсальная машина Тьюринга. Неразрешимость проблем остановки. Пример полугруппы, заданной порождающими и определяющими соотношениями, с неразрешимой проблемой равенства. Неразрешимость чистого исчисления предикатов в сигнатуре (1,+,=).


Универсальная вычислимая функция. Пример вычислимой функции, не имеющий всюду определенного вычислимого продолжения. Перечислимые рекурсивно неотделимые пары множеств. Существование главной универсальной вычислимой функции для класса вычислимых функций из N в N. Теорема Клини о неподвижной точке. Теорема Райса-Успенского.
Базовая литература: [1]

Дополнительная литература: [5], [7], [8]





  1. Раздел 2. Сложность вычислений



Время и зона (память) работы машины Тьюринга. Классы P и NP. Сводимость по Карпу и NP-полные задачи. Ограниченной проблемы остановки для недетерминированных машин Тьюринга. NP-полнота ограниченной проблемы замощения и проблемы выполнимости булевых формул.
Базовая литература: [2]

Дополнительная литература: [6], [9]





  1. Раздел 3. Теоремы Гёделя о неполноте

Формальная арифметика Пеано. Вычислимость и Σ-определимость в арифметике. Теорема о Σ1-полноте арифметики. Первая теорема Геделя о неполноте. Теорема Чёрча об алгоритмической неразрешимости арифметики и чистой логики предикатов. Рекурсивно неотделимые пары множеств, теорема Россера.

Формула доказуемости, лемма о неподвижной точке. Вторая теорема Гёделя о неполноте, теорема Лёба, теорема Тарского о невозможности определения истинности.
Базовая литература: [3], [4].

Дополнительная литература: [10]



8Образовательные технологии

8.1Методические рекомендации преподавателю

8.2Методические указания студентам


9Оценочные средства для текущего контроля и аттестации студента

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









9.2Вопросы для оценки качества освоения дисциплины


1.Что такое вычислимая функция? Бывают ли функции, не являющиеся вычислимыми?

2. Что такое универсальная машина Тьюринга? Разрешима ли проблема остановки?

3. Содержится ли класс P в классе NP? А NP в P? Что такое NP-полная задача? Какие примеры задач такого типа вы знаете?

4. Сформулируйте первую теорему Гёделя о неполноте. Приведите пример пары перечислимых рекурсивно неотделимых множеств. Докажите теорему Гёделя-Россера.

5. Сформулируйте лемму о неподвижной точка для формальной арифметики. Докажите теорему Лёба.


9.3Примеры заданий итогового контроля


Образец задания письменного экзамена:

1. Приведите пример универсальной вычислимой функции для класса вычислимых функций из N в N, которая не является главной.

2. Пусть языки K и L принадлежат NP. Верно ли, что их объединение принадлежит NP? А пересечение?

3. Доказать в арифметике Пено утверждение x(y+z) = xy + xz.

4. Найти арифметическую неподвижную точку формулы x^2 +1 = 0..

10Учебно-методическое и информационное обеспечение дисциплины

10.1Основная литература


1. Верещагин Н.К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. М: МЦНМО, 2002. http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf

2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

3. Сморинский К. Теоремы о неполноте. // Справочная книга по математической логике: В 4-х частях /Под ред. Дж. Барвайса. – Ч. IV. Теория доказательств и конструктивная математика: Пер. с англ.– М.: Наука, 1983. С. 9-53.

4. Мендельсона Э. Введение в математическую логику. М.: Наука, 1984.


10.2Дополнительная литература


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