Партнерка на США и Канаду по недвижимости, выплаты в крипто

  • 30% recurring commission
  • Выплаты в USDT
  • Вывод каждую неделю
  • Комиссия до 5 лет за каждого referral

Министерство образования и науки Российской Федерации

Государственное образовательное бюджетное учреждение высшего профессионального образования

«Пермский государственный педагогический университет»

Кафедра высшей математики

Учебно-методический комплекс дисциплины

ТЕОРИЯ АЛГОРИТМОВ

Специальность 050201.65 «Математика» с дополнительной специальностью «Информатика»

Согласовано:

Рекомендовано кафедрой:

Учебно-методическое управление

Протокол № 1

«____»__________________2012 г.

«____» сентября 2012 г.

_______________________________

Зав. кафедрой __________________

Пермь

2012

Автор-составитель:

, старший преподаватель кафедры алгебры

Учебно-методический комплекс по дисциплине «Теория алгоритмов» со­ставлен в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования по специальности «Ма­тематика» с дополнительной специальностью «Информатика». Дисциплина входит в федеральный компонент цикла специальных дисциплин и является обязательной для изучения.

Согласовано с деканом математического факультета

Декан _______________________________

Директор библиотеки_________

СОДЕРЖАНИЕ

Стр.

I. Рабочая программа дисциплины …………………………………………4

1.Цели и задачи изучения дисциплины……………….…..………….….4

2.Требования к уровню усвоения дисциплины.......................... …….4

3.Объем дисциплины, формы текущего и промежуточного кон­троля…………………………………………………………………….....6

3.1.Объем дисциплины и виды учебной работы.................... ……...6

НЕ нашли? Не то? Что вы ищете?

3.2.Распределение часов по темам и видам учебной работы………….6

4.  Содержание разделов дисциплины………………………………...…8

5.  Темы практических занятий……...………...………….………...….....9

6.  Примерные контрольные работы…….……………………………....11

7.  Тематика рефератов по теории алгоритмов.……………………...….15

8.  Учебно-методическое обеспечение дисциплины..……………..…....16

8.1.  Литература…………………………………………………….…....16

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

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

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

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

I. Рабочая программа дисциплины

1. Цели и задачи изучения дисциплины

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

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

Второй раздел из­ло­же­н в тер­ми­нах чис­ло­вых вы­чис­ли­мых фун­кций, за­дан­ных на на­ту­ра­ль­ных чис­лах, где зна­чи­те­ль­ная часть по­свя­ще­на фун­к­циям, клас­си­че­с­кая точ­ная ма­те­ма­ти­че­с­кая мо­дель ко­то­рых - ре­кур­сив­ные фун­кции является одним из способов уточнения понятия алго­ритма. Изу­че­ние ре­кур­сив­ных фун­кций, на­при­мер, по­мо­га­ет ес­те­ст­вен­но по­дой­ти к по­ни­ма­нию до­ка­за­те­ль­ст­ва зна­ме­ни­той те­оре­мы Гё­де­ля о не­пол­но­те ариф­ме­ти­ки - ве­ли­чай­шей вер­ши­не сре­ди до­сти­же­ний ло­ги­ки XX ве­ка, ока­зав­шей гро­мад­ное вли­яние на умы фи­ло­со­фов, ло­ги­ков и ма­те­ма­ти­ков (ми­ро­воз­зрен­че­с­ко­му зна­че­нию дан­ной те­оре­мы и её до­ка­за­те­ль­ст­ву в кур­се мо­жет быть уде­ле­но осо­бое вни­ма­ние).

Следующие подходы объединяет идея создания механических ма­шин того или иного типа для решения алгоритмических задач. Это ма­шины Тью­ринга, Поста, с неограниченными регистрами (МНР). Изуче­ния устройств и способов работы вышеперечисленных машин, а также рассмотрение возни­кающих алгоритмически неразрешимых проблем в данном контексте исчер­пывают основное содержание третьего раздела и пятого разделов.

Четвертый раздел посвящен еще одному способу уточнения поня­тия алгоритма – нормальные алгоритмы (в авторском варианте - алго­рифмы) Маркова.

В пятый раздел помимо машин Поста и МНД попали вопросы об эк­ви­ва­ле­нт­ности ма­те­ма­ти­че­с­ких мо­де­лей по­ня­тия "ал­го­ритм". Те­зи­сы те­ории ал­го­рит­мов: те­зис Чёр­ча-Кли­ни, при­нцип нор­ма­ли­за­ции Мар­ко­ва, те­зис Тью­рин­га. Задеты вопросы уни­вер­са­ль­ных ал­го­рит­мов и алгорит­мической сводимости.

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

2.Требования к уровню усвоения дисциплины

Выписка из ГОС ВПО по специальности – «Математика» с дополни­тельной специальностью «Информатика», содержащая требования к обяза­тельному минимуму содержания дисциплины и общее количество часов:

Индекс

Наименование дисциплины и ее основ­ные раз­делы

Всего часов

ДПП. Ф.11

Теория алгоритмов

Введение. Алгоритмы в математике. Ос­новные черты алгоритмов. Необходи­мость уточнения понятия алгоритма. Чи­словые функции и алго­ритмы их вычис­ления. Понятие вычислимой функции, разрешимого множества.

Частично рекурсивные функции и рекур­сивные предикаты. Класс частично рекурсивных функ­ций. Исходные функ­ции. Операторы подста­новки, примитив­ной рекурсии, минимизации. Ре­курсивные предикаты. Логические операции. Огра­ниченные кванторы. Подстановка функ­ций в предикат. Кусочное задание функ­ции.

Машины Тьюринга. Понятие машины Тью­ринга Операции с машинами. Тезис Черча-Тью­ринга.

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

90

Предметом изучения данной дисциплины являются следующие объ­екты:

- различные виды уточнения понятия алгоритма:

- рекурсивные функции;

- частично рекурсивные функции;

- общерекурсивные функции;

- машина Тьюринга;

- машины неограниченного доступа;

- нормальные алгоритмы Маркова;

- машины Поста.

- фундаментальные утверждения, связывающие различные подходы теории алгоритмов:

- тезис Черча;

- тезис Тьюринга;

- теорема Поста;

- теорема Клини.

В результате изучения дисциплины студент должен:

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

освоить различные подходы к понятию алгоритма и действия над ним;

приобрести навыки формулировать алгоритмическую сводимость той или иной задачи на различные языки;

уметь вычислять рекурсивности некоторой функции; строить ма­шины Тьюринга, машины Поста, МНР; составлять алгоритмы Маркова.

3. Объем дисциплины, формы текущего и промежуточного контроля

3.1 Объем дисциплины и виды учебной работы

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

Объем часов

Заочная форма обучения

№ семестра

9

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

16

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

4

Лекции

12

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

92

Всего часов на дисциплину:

108

Вид итогового контроля

Зачет – 9 семестр

3.2 Распределение часов по видам и темам деятельности

Содержание и тематика

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

Самостоятель­ная работа (часы)

Всего часов по плану

Лекции

(часы)

Практика

(часы)

I. Введение. Уточнение поня­тия ал­горитма

2

-

16

18

1.  Интуитивное понятие алго­ритма.

2.  Свойства алгоритмов.

3.  Различные подходы к уточне­нию понятия алго­ритма.

1

1

-

-

-

-

5

5

6

6

6

6

II. Рекурсивные функции

2

1

18

21

1.  Основные функции и опе­рации.

2.  Рекурсивность различ­ных функ­ций.

3.  Тезис Черча.

4. Ре­кур­сив­но-пе­ре­чис­ли­мое мно­же­ст­во. Кри­те­рий ре­кур­сив­но­сти мно­же­ст­ва.

1

1

-

-

1

-

-

-

4

6

4

4

6

7

4

4

III. Машины Тьюринга

3

1

20

24

1.  Опе­ра­ции над ма­ши­на­ми Тью­рин­га. Ба­зис эле­мен­тар­ных ма­шин Тью­рин­га. Гё­де­ле­ва ну­ме­ра­ция ма­шин Тью­рин­га

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

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

1

1

1

1

-

-

8

8

4

10

9

5

IV. Нормальные алгоритмы Мар­кова

2

1

18

21

1.  Нор­ма­ль­ный ал­го­ритм Мар­ко­ва в ал­фа­ви­те и над ал­фа­ви­том.

2.  Нор­ма­ль­но-вы­чис­ли­мые фун­к­ции. При­ме­ры нор­ма­ль­ных ал­го­ритмов

1

1

1

-

9

9

11

10

V. Дополнительные главы

3

1

20

24

1. "Ма­ши­на" По­ста. Ма­ши­на По­ста-Успен­ско­го. Ма­ши­на с не­огра­ни­чен­ны­ми ре­ги­стра­ми (МНР).

2. Эк­ви­ва­ле­нт­ность ма­те­ма­ти­че­с­ких мо­де­лей по­ня­тия "ал­го­ритм".

Сов­па­де­ние клас­са фун­к­ций, пра­ви­ль­но-вы­чис­ли­мых по Тью­рин­гу, и клас­са час­тич­но ре­кур­сив­ных фун­кций.

3. Те­зи­сы те­ории ал­го­рит­мов. Те­зис Чёр­ча-Кли­ни. При­нцип нор­ма­ли­за­ции Мар­ко­ва. Те­зис Тью­рин­га.

4. Уни­вер­са­ль­ные ал­го­рит­мы. Уни­вер­са­ль­ная ма­ши­на Тью­рин­га. Уни­вер­са­ль­ные фун­кции.

5. Ал­го­рит­ми­че­с­кая сво­ди­мость. 1-сво­ди­мость. m-сво­ди­мость. Сте­пе­ни не­раз­ре­ши­мо­сти. m-пол­ные. Про­дук­тив­ные и кре­а­тив­ные мно­же­ст­ва. Те­оре­ма Кли­ни о не­под­виж­ной точ­ке. Те­оре­ма Май­хил­ла. Таб­лич­ная сво­ди­мость. Сво­ди­мость по Тью­рин­гу.

1

1

1

-

-

-

1

-

-

-

4

4

4

4

4

5

6

5

4

4

Итого

12

4

92

108

4. Содержание разделов дисциплины

I. Введение. Уточнение понятия алгоритма.

1. Интуитивное опре­де­ле­ние по­ня­тия "ал­го­ритм".

2. Свой­ст­ва ал­го­рит­ма.

II. Рекурсивные функции.

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

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

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

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

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

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

III. Машины Тьюринга

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

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

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

IV. Нормальные алгоритмы Маркова

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

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

V. Дополнительные главы

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

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

3. Эк­ви­ва­ле­нт­ность ма­те­ма­ти­че­с­ких мо­де­лей по­ня­тия "ал­го­ритм".

Сов­па­де­ние клас­са фун­кций, пра­ви­ль­но-вы­чис­ли­мых по Тью­рин­гу, и клас­са час­тич­но ре­кур­сив­ных фун­кций.

4. Те­зи­сы те­ории ал­го­рит­мов. Те­зис Чёр­ча-Кли­ни. При­нцип нор­ма­ли­за­ции Мар­ко­ва. Те­зис Тью­рин­га. Уни­вер­са­ль­ные ал­го­рит­мы. Уни­вер­са­ль­ная ма­ши­на Тью­рин­га. Уни­вер­са­ль­ные фун­кции.

5. Ал­го­рит­ми­че­с­кая сво­ди­мость. 1-сво­ди­мость. m-сво­ди­мость. Сте­пе­ни не­раз­ре­ши­мо­сти. m-пол­ные. Про­дук­тив­ные и кре­атив­ные мно­же­ст­ва. Те­о­ре­ма Кли­ни о не­под­виж­ной точ­ке. Те­оре­ма Май­хил­ла. Таб­лич­ная сво­ди­мость. Сво­ди­мость по Тью­рин­гу.

5. Темы практических занятий

№

Темы практических занятий

Содержание занятий

Контроль усвоения

1

Интуитивное понятие алго­ритма.

Приметы алгоритмов в ма­тематике, некор­ректность интуитив­ного понятия.

К/р №1

2

Свойства алгоритмов.

Определение алго­ритма через его ос­новные свой­ства, не­зависимость свойств при различных под­ходах.

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

3

Различные подходы к уточнению понятия алгоритма.

Краткое перечисле­ние раз­личных под­ходок к уточ­нению понятия алгорит­мов, взаимосвязь

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

4

Основные функции и операции.

Нуль функция, функ­ция выбора аргу­мента, функ­ция сле­дования. Операция рекурсии, минимиза­ции, суперпозиции.

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

5

Рекурсивность различных функций.

Доказательство ре­курсив­ности основ­ных функций ариф­метики. Иные функ­ции, их рекурсив­ность

К/р №2

6

Тезис Черча.

Связь интуитивного поня­тия вычислимой функции и рекурсив­ной функции.

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

7

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

Определение и при­меры перечислимых множеств. Рекурсив­ность перечисли­мого множества.

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

8

Опе­ра­ции над ма­ши­на­ми Тью­рин­га. Гё­де­ле­ва ну­ме­ра­ция ма­шин Тью­рин­га.

Устройство машины Тью­ринга. Примеры построе­ния и реше­ния задач на их со­ставление. Нумера­ция Кантора и Ге­деля.

К/р №3

9

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

Примеры функций, вычис­лимых по Тью­рингу и со­ответст­вующие программы этих машин. Беско­нечно и конечные машины Тью­ринга. Невычислимые по Тьюрингу функции.

К/р №4

К/р №5

10

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

Проблема останова.

Проблема самопри­мени­мости.

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

11

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

Определение и при­меры алгоритмов Маркова. По­нятие алфавита. Нормаль­ные алфавиты и функции, нормально вычислимые по Мар­кову.

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

12

Ма­ши­на По­ста. Ма­ши­на По­ста-Ус­пен­ско­го. Ма­ши­на с не­огра­ни­чен­ны­ми ре­ги­стра­ми (МНР).

Устройство и при­меры машины Поста, различия с машиной Тьюринга. МНР-уст­ройство и примеры.

К/р №6

13

Эк­ви­ва­ле­нт­ность ма­те­ма­ти­че­с­ких мо­де­лей по­ня­тия "ал­го­ритм". Сов­па­де­ние клас­са фун­кций, пра­ви­ль­но-вы­чис­ли­мых по Тью­рин­гу и клас­са час­тич­но ре­кур­сив­ных фун­кций.

Совпадение классов четко определенных и интуи­тивно опре­деленных, от­сутствие контрпримеров.

К/р №7

14

Те­зи­сы те­ории ал­го­рит­мов. Те­зис Чёр­ча-Кли­ни. При­нцип нор­ма­ли­за­ции Мар­ко­ва. Те­зис Тью­рин­га. Уни­вер­са­ль­ные ал­го­рит­мы. Уни­вер­са­ль­ная ма­ши­на Тью­рин­га. Уни­вер­са­ль­ные фун­кции.

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

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

15

Ал­го­рит­ми­че­с­кая сво­ди­мость. 1-сво­ди­мость. M-сво­ди­мость. Сте­пе­ни не­раз­ре­ши­мо­сти. M-пол­ные. Про­дук­тив­ные и кре­атив­ные мно­же­ст­ва. Те­оре­ма Кли­ни о не­под­виж­ной точ­ке. Те­оре­ма Май­хил­ла. Таб­лич­ная сво­ди­мость. Сво­ди­мость по Тью­рин­гу.

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

Самостоя­тельная ра­бота, итого­вое тесто­вое задание

6. Примерные контрольные работы

№1. Алгоритмы в математике.

1. Составьте алгоритм сложения столбиком двух натуральных чисел.

2. Опишите правила перехода улицы для случаев:

а) перекресток регулируемый;

б) перекресток нерегулируемый (т. е. без светофора).

3. Опишите способ измерения длинной рейки с помощью линейки.

4. Укажите метод отыскания слова в орфографическом словаре.

5. Укажите алгоритм проведения перпендикуляра к прямой , в заданной точке D.

6. Опишите несколько алгоритмов решения задач на следующие темы:

а) рецепты приготовления пищи (один из способов получения таких рецеп­тов - воспользуйтесь поваренной книгой);

б) правила этикета (например, правило знакомства, алгоритм приветствия и т. п.);

в) правила дорожного движения;

г) правила поведения в бытовых ситуациях (алгоритм пользования газовой пли­той, правило пользования телефоном-автоматом и т. п.).

8. Составьте алгоритм нахождения цепной дроби рационального числа.

9. Составьте алгоритм нахождения цепной дроби для квадратичной ирра­циональ­ности.

10. Составьте алгоритм нахождения п-ой подходящей дроби некоторого рацио­нального числа.

№2. Исследование на рекурсивность функций.

1.  f(x, y,z) = 2;

2.  f(x, y) = x - y = ;

3.  f(x) = ;

4.  f(x, y) = x + y + 2;

5.  f(x, y) = 3;

6.  f(x, y,z) = x + y + z;

7.  f(x, y) = x + 2;

9. f(x, y) = остатку от деления (x + y) на 2;

10. f(x, y) = остатку от деления х на 3;

№3. Операции над машинами Тьюринга.

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

2. На ленте машины Тьюринга записано слово, состоящее из букв латин­ского алфавита {a, b, c, d }. Подсчитать число вхождений буквы a в за­данное слово. Полученное значение записать на ленту левее заданного слова через пробел. Каретка обозревает крайнюю левую букву.

3. На ленте машины Тьюринга записано десятичное число. Определить, делится ли это число не 5 без остатка. Если делится, то справа от числа записать слово «да», если не делится, то записать «нет». Каретка нахо­дится где-то над числом.

4. На ленте машины Тьюринга записано число в десятичной системе счис­ления. Каретка находится над правой цифрой. Запишите цифры этого числа в обратном порядке.

5. На ленте машины Тьюринга находится массив, состоящий только из символов А и В. Сожмите массив, удавив из него все элементы В.

6. Число n записано на ленте машины Тьюринга массивом меток.

Преобразуйте это значение n по формуле:

n – 2, если n > 5,

j (n) = 1, если n = 5,

2n, если n < 5.

Каретка обозревает крайнюю левую метку.

7. На ленте машины Тьюринга массив из 2n меток. Уменьшите этот мас­сив в 2 раза.

8. Даны два натуральных числа m и n, записанные в унарной системе счисле­ния. Между этими числами стоит знак «?». Выясните отношение между задан­ными числами и замените знак «?» на один из подходящих знаков «<», «>» или «=».

9. Найдите произведение двух натуральных чисел m и n, записанных в унар­ной системе счисления. Соответствующие наборы символов « | » раз­делены зна­ком «*», а справа от последнего символа стоит знак «=». По­местите результат умножение этих чисел вслед за знаком «=».

№4. Составление машин Тьюринга.

1. Дано число n в восьмеричной системе счисления. Постройте машину Тьюринга, которая бы увеличивала данное число на единицу.

2. Дана десятичная запись натурального числа n>1. Постройте машину Тью­ринга, которая уменьшала бы данное число на 1. При этом запись числа n – 1 не должна содержать левый нуль. Например, 100 – 1 = 99, а не 099. Начальное по­ложение головки – правое.

3. Дан массив из открывающихся и закрывающихся скобок. Построить ма - шину Тьюринга, которая удаляла бы пары взаимных скобок.

4. Дана строка из букв a и b. Построить машину Тьюринга, которая пе­ремес­тит все буквы a в левую часть строки, а все буквы b – в правую. Ка­ретка нахо­дится на крайнем левом символом строки.

5. Даны два целых положительных числа в десятичной системе счисления.

Построить машину Тьюринга, которая будет находить разность этих чи­сел, если известно, что первое число больше второго, а между ними стоит знак

« - ». Каретка находится над левой крайней цифрой левого числа.

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

7. Построите машину Тьюринга, которая преобразует запись числа в дво­ичной системе счисления в восьмеричную.

8. Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Построить машину Тьюринга, которая будет запи­сывать в деся­тичной системе счисления число этих меток.

9.  На ленте машины Тьюринга в трёх клетках записаны три различные бу­квы: А, В, С. Каретка в начальном состоянии обозревает букву, располо­женную справа. Построить машину Тьюринга, которая поменяет местами крайние буквы.

10. На ленте машины Тьюринга записано число в десятичной системе счис­ления. Построить машину Тьюринга, которая бы умножала данное число на 2. В начале работы каретка находится над крайней левой цифрой числа.

№5. Функции, вычислимые по Тьюрингу.

1. Построить машину Тьюринга, вычисляющую функцию .

2. Построить машину Тьюринга, вычисляющую функцию .

3. Построить машину Тьюринга, вычисляющую функцию .

4. Построить машину Тьюринга, вычисляющую функцию .

5. Построить машину Тьюринга, вычисляющую функцию .

6. Построить машину Тьюринга, вычисляющую функцию .

7. Построить машину Тьюринга, вычисляющую функцию .

8. Построить машину Тьюринга, вычисляющую функцию .

9. Построить машину Тьюринга, вычисляющую функцию .

10. Построить машину Тьюринга, вычисляющую функцию .

11. Построить машину Тьюринга, вычисляющую функцию .

12. Построить машину Тьюринга, вычисляющую функцию

13. Построить машину Тьюринга, вычисляющую функцию , равную остатку от деления х на 2.

№6. Составление машины Поста.

1. На ленте машины Поста расположен массив в N отмеченных секциях. Необхо­димо справа от данного массива через одну пустую секцию раз­местить массив вдвое больший (он должен состоять из 2N меток). При этом исходный массив может быть стерт.

2. На ленте машины Поста расположен массив из N меток (метки распо­ложены через пробел). Надо сжать массив так, чтобы все N меток зани­мали N располо­женных подряд секций.

3. На информационной ленте машины Поста расположено N массивов ме­ток, от­деленных друг от друга свободной ячейкой. Каретка находится над крайней ле­вой меткой первого массива. Определите число массивов.

4. Игра Баше. В игре участвуют двое (человек и машина Поста). Напи­шите про­грамму, по которой всегда будет выигрывать машина Поста. Суть игры заключа­ется в следующем: имеется 21 предмет. Первым ходит человек. Каждый из иг­рающих может брать 1, 2, 3 или 4 предмета. Проиг­рывает тот, кто берет послед­ний предмет.

5. Число k представляется на ленте машины Поста k+1 идущими подряд мет­ками. Одна метка соответствует нулю. Составьте программу прибав­ления 1 к произвольному числу k. Каретка расположена над одной из ме­ток, принадлежа­щих заданному числу k.

6. Составьте программу сложения двух целых неотрицательных чисел а и b, рас­положенных на ленте машины Поста. Каретка расположена над од­ной из меток, принадлежащих числу а. Число b находится правее числа а через несколько пус­тых секций.

7. Составьте программу сложения произвольного количества целых неот­рица­тельных чисел, записанных на ленте машины Поста на расстоянии одной пустой секции друг от друга. Каретка находится над крайней левой меткой левого числа.

8. На ленте машины Поста расположен массив из N меток. Составьте про­грамму, действуя по которой машина выяснит, делится ли число на 3. Если да, то после массива через одну пустую секцию поставьте метку V.

9. Число k представлено на ленте машины Поста k+1 идущими подряд метками. Найдите остаток от деления целого неотрицательного числа k на 3, если из­вестно, что каретка находится справа от заданного числа.

10. Составьте программу нахождения разности двух неотрицательных це­лых чи­сел а и b, находящихся на ленте машины Поста. Каретка находится над левой меткой левого числа. Неизвестно, какое число больше: а или b.

№ 7. Фун­кции, пра­ви­ль­но-вы­чис­ли­мые по Тью­рин­гу.

1. Построить машину Тьюринга, вычисляющую функцию .

2. Построить машину Тьюринга, вычисляющую функцию .

3. Построить машину Тьюринга, вычисляющую функцию .

4. Построить машину Тьюринга, вычисляющую функцию .

5. Построить машину Тьюринга, вычисляющую функцию .

6. Построить машину Тьюринга, вычисляющую функцию .

7. Построить машину Тьюринга, вычисляющую функцию .

8. Построить машину Тьюринга, вычисляющую функцию .

9. Построить машину Тьюринга, вычисляющую функцию .

10. Построить машину Тьюринга, вычисляющую функцию .

11. Построить машину Тьюринга, вычисляющую функцию .

12. Построить машину Тьюринга, вычисляющую функцию .

13. Построить машину Тьюринга, вычисляющую функцию , рав­ную ос­татку от деления х на 3.

7. Тематика рефератов по теории алгоритмов

1. Эк­ви­ва­ле­нт­ность ма­те­ма­ти­че­с­ких мо­де­лей по­ня­тия "ал­го­ритм".

2. Те­зи­сы те­ории ал­го­рит­мов. Те­зис Чёр­ча-Кли­ни. При­нцип нор­ма­ли­за­ции Мар­ко­ва. Те­зис Тью­рин­га.

3. Уни­вер­са­ль­ные ал­го­рит­мы. Уни­вер­са­ль­ная ма­ши­на Тью­рин­га. Уни­вер­са­ль­ные фун­кции.

4. Ал­го­рит­ми­че­с­кая сво­ди­мость: 1-сво­ди­мость, m-сво­ди­мость. Сте­пе­ни не­раз­ре­ши­мо­сти. m-пол­ные. Про­дук­тив­ные и кре­атив­ные мно­же­ст­ва.

5. Те­оре­ма Кли­ни о не­под­виж­ной точ­ке.

6. Те­оре­ма Май­хил­ла.

7. Таб­лич­ная сво­ди­мость. Сво­ди­мость по Тью­рин­гу.

8. Нор­ма­ль­ный ал­го­ритм Мар­ко­ва в ал­фа­ви­те и над ал­фа­ви­том. История возник­новения.

9. Десятая проблема Гильберта.

10. Примеры разрешимых и перечислимых множеств. Взаимосвязь поня­тий.

11. Примеры неразрешимых алгоритмических проблем.

12. Теорема Геделя о неполноте.

13. Рекурсивные функции.

14. Класс частично рекурсивных функций.

15. Класс рекурсивных функций.

16. Класс общерекурсивных функций.

17. Сов­па­де­ние клас­са фун­кций, вы­чис­ли­мых по Тью­рин­гу и клас­са час­тич­но ре­кур­сив­ных фун­кций.

18. Примеры функций невычислимых по Тьюрингу.

19. Нормальные алгоритмы.

20. Тьюринга.

21. Черча.

22. Поста.

23. Маркова.

24. История возникновения термина «алгоритм».

25. Машинная арифметика.

26. Современное состояние теории алгоритмов.

8. Учебно-методическое обеспечение дисциплины

8.1. Литература

Основная:

1.  Г. Теория алгоритмов, учеб. пособие /. – Пермь, ПГПУ, 2011. – 89с.

2.  , Ф. Математическая логика и теория алгоритмов. Учебно-практическое пособие. – М.: Евразийский открытый институт (базовая коллекция), 2009. – 189с.

Дополнительная:

1. Мар­ков А. А., На­гор­ный Н. М. Те­ория ал­го­риф­мов. - М.: ФАЗИС, 19с.

2. Мат­ро­сов В. Л. Те­ория ал­го­рит­мов. - М.: Про­ме­тей, 1989.

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

4. Ми­хай­лов А. Б., Ры­жо­ва Н. И., Швец­кий М. В. Упраж­не­ния по ос­но­вам ма­те­ма­ти­че­с­кой ло­ги­ки. Вве­де­ние в те­орию ал­го­риф­мов. - СПб.: РГПУ им. А.И. Герцена, 1997.

5. Ми­хай­лов А. Б., Ры­жо­ва Н. И., Швец­кий М. В. Лек­ции по ос­но­вам ма­те­ма­ти­че­с­кой ло­ги­ки. Эле­мен­ты те­ории ал­го­риф­мов. - СПб.: РГПУ им. , 1997.

6. Род­жерс Х. Те­ория ре­кур­сив­ных фун­кций и эф­фе­к­тив­ная вы­чис­ли­мость. - М.: Мир, 1972.

7. Трах­те­нб­рот Б. А. Ал­го­рит­мы и вы­чис­ли­те­ль­ные ав­то­ма­ты. - М.: Сов.

радио, 1974.

8. Успен­ский В. А. Ма­ши­на По­ста. - М.: На­ука, 1979.

9. Успен­ский В. А. Се­мё­нов А. Л. Те­ория ал­го­рит­мов: осно­вные от­кры­тия и при­ло­же­ния. - М.: На­ука, 1987.

Электронные материалы

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

http://lpcs. math. msu. su/~pentus/problems. htm

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

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

www. /files/special/protection/  

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

rrc. *****/res/intsys. *****/staff/vnosov/theoralg. htm

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

www. /contentview. php? content

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

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

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

Всего

ча­сов

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

108

 

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

16

 

Лекции

12

 

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

4

 

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

92

 

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

48

 

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

48*1/3

=16

 

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

48*2/3

=32

 

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

14

 

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

10

 

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

8

 

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

8

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

2

 

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

§  Понятие алгоритмической неразрешимости.

§  Теорема Геделя о неполноте.

§  Анонс алгоритмически неразрешимых проблем.

§  Оценки сложности алгоритмов.

§  Алгоритмы Маркова.

§  Игра «Домино».

§  Специальные системы Шмульяна.

§  Проблема перечислимости и разрешимости.

§  Неразрешимые множества.

§  Невычислимые функции.

§  Проблемы формальных языков.

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

Студентам сообщаются следующие критерии оценки отчета о вы­полнении проекта:

-  Полнота, последовательность и логика изложения;

-  Связь теоретических положений с данными реальных наблюдений;

-  Обоснованность упрощающих предположений при построении моде­лей;

-  Наличие результатов качественного и количественного анализа пока­зате­лей состояния изучаемого объекта;

-  Уровень культуры речи;

-  Искусство презентации.

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

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/, с.

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. Ма­ши­на с не­огра­ни­чен­ны­ми ре­ги­стра­ми (МНР).