Geum.ru

Программа дисциплины теория алгоритмов специальность 050201. 65 «Математика» с дополнительной специальностью «Информатика» Согласовано

Вид материалаПрограмма дисциплины

Содержание


1. Сайт профессора кафедры математической логики и теории алгоритмов МГУ им. Ломоносова Пентуса М.Р.
Виды учебной работы
1. Творцы теории алгоритмов.
2. Алгоритмы поиска.
3. Неразрешимость логики первого порядка.
4. Нестандартные модели арифметики.
5. Метод диагонализации в математической логике.
6. Машины Тьюринга и невычислимые функции.
7. Вычислимость на абаке и рекурсивные функции.
8. Представимость рекурсивных функций и отрицательные резуль­таты ма­тематической логики.
10. Разрешимость арифметики сложения.
11. Теорема Геделя о неполноте формальной арифметики.
12. Разрешимые и неразрешимые аксиоматические теории.
II. Материалы, устанавливающие содержание и порядок проведения про­межуточных и итоговых аттестаций
Подобный материал:
1   2   3

1. Сайт профессора кафедры математической логики и теории алгоритмов МГУ им. Ломоносова Пентуса М.Р.:


.msu.su/~pentus/problems.htm

2. Сайт Кафедры «Прикладной математики» Физико-механического фа­культета Санкт-Петербургского государственного технического универ­ситета: eva.ru/education/prog71.htm

3. Сайт УГАТУ (рефераты и лекции):

www.twirpx.com/files/special/protection/  

4. Электронный вариант книги Носова В.А. «Алгоритмы и оценки их сложности»:

rrc.dgu.ru/res/intsys.msu.ru/staff/vnosov/theoralg.htm

5. Электронный вариант книги Мальцева А.И. «Алгоритмы и рекурсив­ные функ­ции»:

www.proklondike.com/contentview.php?content


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


  1. Распределение самостоятельной работы студента:




Виды учебной работы
Всего

ча­сов

Общая трудоемкость
90

Аудиторные занятия
44

Лекции
24

Практические занятия
10

Самостоятельная работа:
46

1. Изучение программы курса
24

1.1. Проработка материалов по конспекту лек­ций
24*1/3

=8

1.2. Изучение материалов, изложенных в лек­ции, по учебникам и разбор са­мостоятельных доказа­тельств, решение практических задач

24*2/3

=16

2. Подготовка рефератов по теории алгоритмов

12

3. Подготовка к аудиторной контрольной работе

2*2

=4

4. Выполнение домашней индивидуальной работы
2

5. Выполнение индивиду­ального проекта по теории графов (написание эссе, подготовка доклада, оформ­ле­ние презентации) / курсовой работы
2

6. Вид итогового контроля – зачет
2


2. Список тем индивидуальных проектов по теории алгоритмов для само­стоятельной разработки (написание эссе, подготовка доклада, оформление пре­зентации):
  • Понятие алгоритмической неразрешимости.
  • Теорема Геделя о неполноте.
  • Анонс алгоритмически неразрешимых проблем.
  • Оценки сложности алгоритмов.
  • Алгоритмы Маркова.
  • Игра «Домино».
  • Специальные системы Шмульяна.
  • Проблема перечислимости и разрешимости.
  • Неразрешимые множества.
  • Невычислимые функции.
  • Проблемы формальных языков.


Установленный срок подготовки презентации и защиты проекта на науч­ной конференции студенческой группы в конце семестра – 3 недели.

Студентам сообщаются следующие критерии оценки отчета о вы­полнении проекта:
  • Полнота, последовательность и логика изложения;
  • Связь теоретических положений с данными реальных наблюдений;
  • Обоснованность упрощающих предположений при построении моде­лей;
  • Наличие результатов качественного и количественного анализа пока­зате­лей состояния изучаемого объекта;
  • Уровень культуры речи;
  • Искусство презентации.




  1. Тематика курсовых работ по теории алгоритмов и методиче­ские указания по их выполнению

1. Творцы теории алгоритмов.

Цель данной курсовой работы – исследовать причины возникновения тео-рии алгоритмов, ее необходимость для обоснования иных математи­ческих наук.

Рекомендуется следующий план изложения материала:

1. Проблемы отсутствия алгоритма для решения класса математичес­ких задач (проблема тождества для полугрупп и групп, нахождение общего способа решения диофантовых уравнений и др.)./1/, § 71.

2. Неразрешимые задачи в теории алгоритмов. /2/,с. 279-282.

Литература, рекомендуемая для изучения темы:

1. Клини С.К. Введение в математику.- М.: ИЛ, 1957.

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

2. Алгоритмы поиска.

Цель данной курсовой работы - рассмотреть основные алгоритмы на

графах, которые находят применение при сжатии информации, распозна­вании

образов и синтезе баз данных.

Рекомендуется следующий план изложения материала:

1. Необходимые понятия теории графов (/2/, с. 9-43, /1/, с. 57-64).

2. Бинарный поиск (/1/, с. 64-65).

3. Быстрая сортировка (/1/, с. 65-69).

4. Алгоритм Дикстры (/1/, с. 69-72).

Литература, рекомендуемая для изучения темы:

1. Гоппа В.Д. Введение в алгебраическую теорию информации. – М.:

Наука, 1995.

2. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.

3. Неразрешимость логики первого порядка.

Одним из принципиально важных результатов математической логики и теории алгоритмов является доказательство неразрешимости в логике первого порядка проблем распознавания как общезначимости, так и вы­полнимости ее предложений. Цель данной курсовой работы - изучить до­казательства неразре­шимости логики первого порядка.

Рекомендуется следующий план работы:

1. Изучить основные понятия логики первого порядка (/1/, с. 130-151).

2. Рассмотреть понятие машины Тьюринга и доказать неразрешимость про­блемы остановки (/1/, с. 36-54).

3. Вывести неразрешимость логики первого порядка из неразрешимо­сти

проблемы остановки (/1/, с. 152-160).

4. Разобрать доказательство неразрешимости логики первого порядка

методом Геделя (/1/, с. 160-166).

5. Решить задачи 3.6, 3.10 из упражнения на стр. 46-48 и задачи 10.1, 10.3

из упражнения на стр. 164-165 в книге /1/.

Литература, рекомендуемая для изучения темы:

1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

4. Нестандартные модели арифметики.

В любой математической теории принципиально важным является вопрос о существовании и единственности модели формализации этой теории. Цель дан­ной курсовой работы - проанализировать этот вопрос для элементарной теории арифметики.

Рекомендуется следующий план работы:

1. Рассмотреть язык логики узкого исчисления предикатов арифме­тики

и его стандартную интерпретацию в алгебре натуральных чисел(/1/, с. 131-151; /2/, с. 115-131).

2. Доказать теорему о существовании нестандартных моделей

элементарной теории арифметики (/1/, с. 252-260).

3. Изучить метод построения моделей элементарной теории арифме­тики с помощью принципов нестандартного анализа (/1/, с. 25-32; /3/, с. 57- 79).

4. Разобрать все примеры из указанных выше литературных источ­ников и решить задачи 17.1, 17.2 в /1/, а также задачи 1-3 стр.131 в книге /2/.

Литература, рекомендуемая для изучения темы:

1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

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

5. Метод диагонализации в математической логике.

В теории алгоритмов, математической логике, теории множеств и других разделах математики широко применяется метод диагонализации, в основе кото­рого лежит возможность построения антидиагонального счетного множества для любой последовательности счетных множеств. Цель данной курсовой работы - изучить метод диагонализации и с его помощью построить примеры невычисли­мых функций. Рекомендуется следующий план работы:

1. Рассмотреть понятие счетного множества и изучить метод диаго­нализа­ции (/1/, с. 12-30).

2. Рассмотреть понятие машины Тьюринга и методом диагонализации по­строить пример невычислимой функции (/1/, с. 36-45, 66-74).

3. Рассмотреть проблему остановки машины Тьюринга и с помощью тезиса Черча доказать ее неразрешимость (/1/, с. 47-48, 74-76).

4. Рассмотреть понятие диагонализации выражения и доказать лемму о диа­гонализации и теорему Черча о неразрешимости (/1/, с. 228-235).

5. Разобрать решения всех примеров из цитированных разделов /1/ и решить задачи 3.9, 3.10 из упражнения на стр. 45-48 и задачи 5.1-5.4 из упражнения на стр. 76-77 в книге /1/.

Литература, рекомендуемая для изучения темы:

1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

6. Машины Тьюринга и невычислимые функции.

Машина Тьюринга и вычислимость являются фундаментальными по­нятиями теории алгоритмов. Цель данной курсовой работы - изучить ос­новные свойства машины Тьюринга и с ее помощью построить невычис­лимую функцию.

Рекомендуется следующий план работы:

1. Разобрать такие основополагающие понятия теории алгоритмов,

как машина Тьюринга, вычислимая функция и тезис Черча (/1/, с. 36-54; /2/, с.228-229, 249-255).

2. Рассмотреть понятие продуктивности машины Тьюринга и дока­зать ее основные свойства (/1/, с. 46, 55-60; /2/, с. 12-25).

3.Доказать невычислимость функции - самоприменимость машины Тьюринга (/1/, с. 60-64).

4. Рассмотреть проблему останова машины Тьюринга и доказать ее нераз­решимость (/1/, с. 47-48, 53-54, 64-65).

5. Разобрать решения всех примеров из литературных источников /1/,/2/ и решить задачи 3.1-3.10 из упражнения на стр. 45-48 в книге /1/.

Литература, рекомендуемая для изучения темы:

1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

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

7. Вычислимость на абаке и рекурсивные функции.

Рекурсивная функция и вычислимость являются фундаментальными поня­тиями теории алгоритмов. Цель данной курсовой работы - изучить вычисли­мость на абаке, вычислимость машиной Тьюринга и доказать их эквивалент­ность понятию рекурсивной функции.

Рекомендуется следующий план работы:

1. Разобрать такие основополагающие понятия теории алгоритмов, как мА шина Тьюринга, рекурсивная функция и тезис Черча (/1/, с. 36-54).

2. Рассмотреть понятие «обычного» компьютера, введенное Иоахи­мом Ламбеком и названное им абаком, доказать, что вычислимость функ­ции абаком сводится к вычислимости ее машиной Тьюринга (/1/, с. 78-95).

3. Доказать, что рекурсивные функции вычислимы на абаках (/1/, с. 100-122).

4. Доказать, что вычислимые функции рекурсивны (/1/, с. 100-122).

5. Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 6.1-6.4 из упражнения на стр. 96 в книге /1/.

Литература, рекомендуемая для изучения темы:

1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

8. Представимость рекурсивных функций и отрицательные резуль­таты ма­тематической логики.

Главными отрицательными результатами теории алгоритмов являются тео­рема Черча о неразрешимости, теорема Тарского о неопределимости истинности и первая теорема Геделя о неполноте систем арифметики. Цель данной курсовой работы - изучить доказательства этих теорем с по­мощью представления рекур­сивных функций в специальном расширении арифмети-ки.

Рекомендуется следующий план работы:

1. Разобрать такие основополагающие понятия теории алгоритмов,

как язык арифметики и рекурсивная функция (/1/, с. 103-108, 141-145).

2. Рассмотреть понятие представимости функций в теории и доказать

представимость рекурсивных функций в специальном непро­тиворечивом расширении Q арифметики (/1/, с. 212-226).

3. Рассмотреть понятие геделевой нумерации и доказать главные

отрицательные результаты теории алгоритмов (/1/, с. 228-240).

4. Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 14.1-14.2 из упражнения на стр. 226-227 и задачи 15.1-15.4 из упражнения на стр. 240 в книге /1/.

Литература, рекомендуемая для изучения темы:

1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

10. Разрешимость арифметики сложения.

Проблема разрешимости теорий имеет принципиальное значение для эле­ментарно аксиоматизируемых математических теорий и, в частности, для ариф­метики. Цель данной курсовой работы - проанализировать эту проблему для арифметики с различными основными операциями.

Рекомендуется следующий план работы:

1. Разобрать такие основополагающие понятия математической ло­гики, как геделева нумерация и разрешимое множество (/1/, с. 228-233, /2/, с.151-152).

2. Доказать неразрешимость арифметики со сложением и умноже­нием (/1/, с. 234-236).

3. Доказать разрешимость арифметики со сложением, без умноже­ния (/1/, с. 290-299).

4. Разобрать решения всех примеров из цитированных разделов книг /1/,/2/ и решить задачи 1-3 из упражнения на стр. 152 в книге /2/.

Литература, рекомендуемая для изучения темы:

1. Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

11. Теорема Геделя о неполноте формальной арифметики.

Теорема Геделя о неполноте формальной арифметики по праву счи­тается одним из наиболее замечательных достижений математической ло­гики и теории алгоритмов, поскольку в своей семантической формули­ровке устанавливает не­возможность доказательства любого истинного ут­верждения этих формальной теории. Цель данной курсовой работы - изу­чить основы формальной арифме­тики и разобрать доказательство семан­тической формулировки теоремы Геделя о ее неполноте.

Рекомендуется следующий план работы:

1. Изучить постановку задачи о неполноте формальной арифметики (/1/,с. 7-11).

2. Рассмотреть начальные понятия теории алгоритмов и примеры их

применения (/1/, с. 12-21).

3. Доказать простейшие критерии неполноты (/1/, с. 21-25).

4. Изучить основы формальной арифметики и доказать семантиче­скую формулировку теоремы Геделя о ее неполноте (/1/, с. 25-42).

5. Разобрать все примеры и восстановить все пропущенные доказа­тельства в брошюре /1/.

Литература, рекомендуемая для изучения темы:

1. Успенский В.А. Теорема Геделя о неполноте. – М.: Наука, 1982.

12. Разрешимые и неразрешимые аксиоматические теории.

Проблема разрешимости теорий имеет принципиальное значение для элемен­тарно аксиоматизируемых математических теорий. Цель данной курсовой ра­боты - изучить методы доказательства разрешимости и не­разрешимости теорий, проиллюстрировав их применение на известных важных примерах.

Рекомендуется следующий план работы:

1. Разобрать такие основополагающие понятия теории моделей, как

язык узкого исчисления предикатов (УИП) и его интерпретация в моделях, рассмотреть известные конструкции над алгебраическими системами (/1/, с.103-118; /2/, с. 12-25).

2. Изучить методы доказательства разрешимости и неразрешимости

теорий (/2/, с. 265-275).

3. Рассмотреть известные примеры доказательства разрешимости и

неразрешимости аксиоматических теорий (/2/, с. 275-292; /3/).

4. Разобрать решения всех примеров из литературных источников /1/, /2/.

Литература, рекомендуемая для изучения темы:

1. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1979.

2. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. –

М.: Наука, 1980.

3. Рабин М.О. Разрешимые теории. В кн.: Справочная книга по

математической логике, ч.3. Теория рекурсии. – М.: Наука, 1982. – с. 77-111.

4. Ершов Ю.Л., Лавров И.А., Тайманов А.Д., Тайцлин М.А.

Элементарные теории // УМН, 1965, 20, № 4, с. 37-108.


II. Материалы, устанавливающие содержание и порядок проведения про­межуточных и итоговых аттестаций

 1. Вопросы для зачета


1. Интуитивное опре­де­ле­ние по­ня­тия «ал­го­ритм». Свой­ст­ва ал­го­рит­ма

2. Про­стей­шие фун­кции. Опе­ра­ция под­ста­но­вки. Свой­ст­ва опе­ра­ции под­ста­но­вки. Опе­ра­ция при­ми­тив­ной ре­кур­сии. Свой­ст­ва опе­ра­ции при­ми­тив­ной ре­кур­сии. При­ми­тив­но-ре­кур­сивное опи­са­ние фун­кции.

3. При­ми­тив­но-ре­кур­сив­ная фун­кция. Свой­ст­ва при­ми­тив­но-ре­кур­сив­ных фун­кций. При­ме­ры при­ми­тив­но-ре­кур­сив­ных фун­кций. От­но­си­те­ль­ная при­ми­тив­ная ре­кур­сив­ность. Свой­ст­ва от­но­си­те­ль­ной при­ми­тив­ной ре­кур­сив­но­сти.

4. При­ми­тив­но-ре­кур­сив­ные опе­ра­ции (опе­ра­ция вве­де­ния фик­тив­ных пе­ре­мен­ных, опе­ра­ция под­ста­но­вки кон­стант, опе­ра­ция про­из­во­ль­ной под­ста­но­вки). Опе­ра­ции ко­неч­но­го сум­ми­ро­ва­ния и ко­неч­но­го про­из­ве­де­ния. При­мер ис­по­ль­зо­ва­ния опе­ра­ции ко­неч­но­го сум­ми­ро­ва­ния для до­ка­за­те­ль­ст­ва при­ми­тив­ной ре­кур­сив­но­сти фун­кции [x/y].

5. Пред­став­ля­ющая фун­кция пре­ди­ка­та. При­ми­тив­но-ре­кур­сив­ный пре­ди­кат. При­ми­тив­но-ре­кур­сив­ный пре­ди­кат от­но­си­те­ль­но со­во­куп­но­сти фун­кций и пре­ди­ка­тов. Ло­ги­че­с­кие опе­ра­ции. Опе­ра­ции на­ве­ши­ва­ния огра­ни­чен­ных кван­то­ров. Ку­со­чное за­да­ние фун­кции.

6. m-опе­ра­ция (опе­ра­ция ми­ни­ми­за­ции). Час­тич­но ре­кур­сив­ное опи­са­ние фун­к­ции. Час­тич­но ре­кур­сив­ная фун­кция. При­ме­ры час­тич­но ре­кур­сив­ных фун­кций. Об­ще­ре­кур­сив­ная фун­кция. При­ме­ры об­ще­ре­кур­сив­ных фун­кций.

Фор­ма­ль­ная сис­те­ма ре­кур­сив­ных фун­кций Эр­бра­на-Гё­де­ля. Фун­кция, вы­чис­ли­мая по Эр­бра­ну-Гё­де­лю.

7. Ре­кур­сив­но-пе­ре­чис­ли­мое мно­же­ст­во. Кри­те­рий ре­кур­сив­ной пе­ре­чис­ли­мо­сти мно­же­ст­ва. Ре­кур­сивные мно­же­ст­во. Кри­те­рий ре­кур­сив­но­сти мно­же­ст­ва (те­оре­ма По­ста).

8. Нор­ма­ль­ный ал­го­ритм Мар­ко­ва в ал­фа­ви­те и над ал­фа­ви­том. Нор­ма­ль­но-вы­чис­ли­мые фун­кции.

9. При­ме­ры нор­ма­ль­ных ал­го­рит­мов (тож­де­ст­вен­ный нор­ма­ль­ный ал­го­ритм, нор­ма­ль­ный ал­го­ритм ле­во­го при­со­еди­не­ния, нор­ма­ль­ный ал­го­ритм пра­во­го при­со­еди­не­ния, нор­ма­ль­ный ал­го­ритм уд­во­ения, не­ко­то­рые ариф­ме­ти­че­с­кие ал­го­ритмы).

10. Ма­ши­на Тью­рин­га. Опе­ра­ции над ма­ши­на­ми Тью­рин­га (опе­ра­ция ком­по­зи­ции, опе­ра­ция вет­вле­ния, опе­ра­ция за­цик­ли­ва­ния). Гё­де­ле­ва ну­ме­ра­ция ма­шин Тью­рин­га.

11. Фун­кция, вы­чис­ли­мая по Тью­рин­гу. До­ка­за­те­ль­ст­во су­ще­ст­во­ва­ния фун­к­ций, не­вы­чис­ли­мых по Тью­рин­гу. При­мер не­вы­чис­ли­мой по Тью­рин­гу фун­кции.

12. При­ме­ры ал­го­рит­ми­че­с­ки не­раз­ре­ши­мых проблем (про­бле­ма рас­по­зна­ва­ния са­мо­при­ме­ни­мо­сти, про­бле­ма при­ме­ни­мо­сти).

13. Ма­ши­на По­ста. Ма­ши­на По­ста-Успен­ско­го.

14. Ма­ши­на с не­огра­ни­чен­ны­ми ре­ги­стра­ми (МНР).

Copyright © 2023. All rights Reserved.