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

Вид материала

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

Содержание I. Рабочая программа дисциплины 2.Требования к уровню усвоения дисциплины Теория алгоритмов 3. Объем дисциплины, формы текущего и промежуточного контроля Вид учебной работы Всего часов на дисциплину Содержание и тематика Введение. Уточнение поня­тия ал­горитма II. Рекурсивные функции Машины Тьюринга IV. Нормальные алгоритмы Мар­кова V. Дополнительные главы 4. Содержание разделов дисциплины II. Рекурсивные функции. III. Машины Тьюринга IV. Нормальные алгоритмы Маркова V. Дополнительные главы 5. Темы практических занятий 6. Примерные контрольные работы 7. Тематика рефератов по теории алгоритмов ... Полное содержание

Подобный материал:

• Программа учебной дисциплины методы математической физики специальность «050201 математика, 145.93kb.
• Программа дисциплины опд. Ф. 04. 1 «Теория и методика обучения математике» Специальность, 184.43kb.
• Рабочая программа учебной дисциплины дпп. Ф. 07. Теория чисел ооп, 386.12kb.
• Программа учебной дисциплины история математики специальность 050201 математика с дополнительной, 409.11kb.
• Программа дисциплины фтд. 00 «избранные главы алгебры» Специальность 032100. 01 Математика, 95.5kb.
• Учебно-методический комплекс учебной дисциплины дпп. Р. 01. Математическое конструирование, 83.94kb.
• Учебно-методический комплекс учебной дисциплины Математическое моделирование 032100., 547.37kb.
• Программа дисциплины фтд. 00 «основания математики» Специальность 032100. 01 Математика, 62.49kb.
• Рабочая программа учебной дисциплины дпп. Ф. 08 Числовые системы ооп, 599.58kb.
• Программа учебной дисциплины теория и методика обучения физике Для специальности 050203, 597.46kb.

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

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

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

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


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

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


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


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

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

Согласовано:	Рекомендовано кафедрой:
Учебно-методическое управление	Протокол №_____
«____»__________________20__ г.	«____»__________________20__ г.
_______________________________	Зав. кафедрой __________________

Пермь

2011


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

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


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


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

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

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

СОДЕРЖАНИЕ


Стр.

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

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

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

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

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

4. 
   Содержание разделов дисциплины………………………………...…8
   
5. Темы практических занятий……...………...………….………...….....9
   
6. Примерные контрольные работы…….……………………………....11
   
7. Тематика рефератов по теории алгоритмов.……………………...….15
   
8. Учебно-методическое обеспечение дисциплины..……………..…....16
   
   1. Литература…………………………………………………….…....16
      

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

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

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

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

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

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

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

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

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

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

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

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

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


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


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

Индекс	Наименование дисциплины и ее основ­ные раз­делы	Всего часов
ДПП.Ф.11	Теория алгоритмов Введение. Алгоритмы в математике. Ос­новные черты алгоритмов. Необходи­мость уточнения понятия алгоритма. Чи­словые функции и алго­ритмы их вычис­ления. Понятие вычислимой функции, разрешимого множества. Частично рекурсивные функции и рекур­сивные предикаты. Класс частично рекурсивных функ­ций. Исходные функ­ции. Операторы подста­новки, примитив­ной рекурсии, минимизации. Ре­курсивные предикаты. Логические операции. Огра­ниченные кванторы. Подстановка функ­ций в предикат. Кусочное задание функ­ции. Машины Тьюринга. Понятие машины Тью­ринга Операции с машинами. Тезис Черча-Тью­ринга. Рекурсивные и рекурсивно-перечисли­мые мно­жества. Рекурсивно-перечисли­мые предикаты, их свойства. Рекурсивно-перечислимые множе­ства. Нумерация. Универсальная функция. Тео­рема Клини. Неразрешимые алгоритмические про­блемы. Алгоритмическая сводимость.	90

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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


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


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

Вид учебной работы	Объем часов
	Очная форма обучения
№ семестра	8
Аудиторные занятия:	44
Практические и семинарские занятия	20
Лекции	24
Самостоятельная работа:	46
Всего часов на дисциплину:	90
Вид итогового контроля	Зачет – 8 семестр