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


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

высшего профессионального образования

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


Кафедра алгебры

Пастухова Г.В.


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


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

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



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

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

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

Протокол №_____

«____»__________________20__ г.

«____»__________________20__ г.

_______________________________

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



Пермь

2011


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

Пастухова Г.В., ст. преподаватель кафедры алгебра


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


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

Декан _______________________________ Власова И.Н.

Директор библиотеки Подгорных Г.М.

СОДЕРЖАНИЕ


Стр.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


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



Индекс

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

Всего часов

ДПП.Ф.11

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

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

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

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

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

90


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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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


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


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


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

Объем часов

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

№ семестра

8

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

44

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

20

Лекции

24

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

46

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

90

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

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



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

^ Содержание и тематика
Аудиторные занятия

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

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

Лекции

(часы)

Практика

(часы)

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

6

3

4

13

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

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

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

1


2

3


1


1

1


1


2

1


3


5

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

5

9

20

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

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

Тезис Черча.

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

2

2


1


1

2

1


1


1

2

2


3


2


6

5


5


4


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

5

5

9

19

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

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

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

1


2


2



1


2


2

3


3


3

5


7


7


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

2

6

10

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

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

1


1

1


1

3


3

5


5


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

5

18

28

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

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

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

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

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

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

1


1


1


1


1

1


1


1


1


1



4


6


4


2


2

6


8


6


4


4



Итого

24

20

46

90



^ 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. Исследование на рекурсивность функций.

f(x,y,z) = 2;

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

f(x) = ;

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

f(x,y) = 3;

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

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. Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Построить машину Тьюринга, которая будет запи­сывать в деся­тичной системе счисления число этих меток.

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

На ленте машины Тьюринга записано число в десятичной системе счис­ления. Построить машину Тьюринга, которая бы умножала данное число на 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. Литература

Основная:

Кат­ленд Н. Вы­чис­ли­мость. Вве­де­ние в те­орию ре­кур­сив­ных фун­кций. - М.: Мир, 1983.

Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математиче­ской логике и теории алгоритмов. – М.: Наука, 1984.

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

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

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.neva.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. Методические указания студентам


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




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

Всего

ча­сов

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

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/, § 71.

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

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

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

2.
еще рефераты
Еще работы по разное