Рабочая учебная программа по дисциплине «Теория алгоритмов»




Скачать 101.52 Kb.
НазваниеРабочая учебная программа по дисциплине «Теория алгоритмов»
Дата17.02.2013
Размер101.52 Kb.
ТипРабочая учебная программа


Рабочая учебная программа по дисциплине
«Теория алгоритмов»


ГОУ ВПО «Уральский государственный педагогический университет»

Екатеринбург, 2007. 8 с.


Составитель

Ильиных А.П., зав. кафедрой алгебры и теории чисел


Рабочая учебная программа обсуждена на заседании кафедры алгебры и теории чисел УрГПУ

Протокол от 07.04.2006 № 8.

И. о. зав. кафедрой С.С. Коробков


  1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА


Понятия алгоритма и вычислимой функции являются фундаментальными понятиями математики, логики и информатики. Многие теоретические и практические задачи требуют указать алгоритм - такой набор инструкций, выполняя которые конечное число раз, мы решим поставленную задачу. Выработка точного понятия алгоритма является одним из наиболее значительных достижений науки XX столетия. Такое определение было получено в работах выдающихся специалистов по математической логике К.Геделя, А.Черча, Э.Поста, Э.Тьюринга, А.А.Маркова. Систематическое изучение алгоритмов и различных моделей вычислений привело к созданию ряда прикладных дисциплин, развитию средств вычислительной техники и современных коммуникаций. Тем самым развитие теории алгоритмов в 30-е годы XX столетия, явилось стимулом для появления в 40-х годах первых компьютеров.

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


2. УЧЕБНО-ТЕМАТИЧЕСКОЕ ПЛАНИРОВАНИЕ



    1. . Учебно-тематический план очной формы обучения






п/п

Наименование раздела, темы

Всего трудоемкость

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

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

Всего

Лекции

Практические

1.

Алгоритмы в математике. Числовые функции и алгоритмы их вычисления

16

8

4

4

8

2.

Частично рекурсивные функции. Тезис Черч

16

8

4

4

8

3.

Машины Тьюринга и машины с неограниченными регистрами

28

14

6

8

14

4.

Нумерации и универсальные функции

16

8

4

4

8

5.

Нормальные алгорифмы

8

4

2

2

4

6.

Неразрешимые алгоритмические проблемы

16

8

4

4

8

7.

Разрешимые и перечислимые множества и предикаты

8

4

2

2

4




Итого:

108

54

26

28

54



2.2 Учебно-тематический план заочной формы обучения





п/п

Наименование раздела, темы

Всего трудоемкость

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

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

Всего

Лекции

Практические

1.

Алгоритмы в математике Числовые функции и алгоритмы их вычисления

12

2

1

1

10

2.

Частично рекурсивные функции. Тезис Черча

12

2

1

1

10

3.

Машины Тьюринга и машины с неограниченными регистрами

22

2

1

1

20

4.

Нумерации и универсальные функции

12

2

1

1

10

5.

Нормальные алгорифмы

11

1

1




10

6.

Неразрешимые алгоритмические проблемы

11

1

1




10

7.

Разрешимые и перечислимые множества и предикаты

28










28




Итого:

108

10

6

4

98



3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ




  1. Алгоритмы в математике Числовые функции и алгоритмы их вычисления

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

  1. Частично рекурсивные функции. Тезис Черча

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

  1. Машины Тьюринга и машины с неограниченными регистрами

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

  1. Нумерации и универсальные функции

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

  1. Нормальные алгорифмы

  2. Неразрешимые алгоритмические проблемы

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

Алгоритмическая сводимость.

4. САМОСТОЯТЕЛЬНАЯ РАБОТА И ОРГАНИЗАЦИЯ
КОНТРОЛЬНО-ОЦЕНОЧНОЙ ДЕЯТЕЛЬНОСТИ




    1. . Темы, вынесенные на самостоятельное изучение

Рекурсивные предикаты. Логические операции. Ограниченные кванторы. Подстановка функций в предикат. Кусочное задание функции.


    1. Примерные темы курсовых работ

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

  2. Частично рекурсивные функции и тезис Черча.

  3. Машина Тьюринга.

  4. Машина с неограниченными регистрами.

  5. Нормальные алгорифмы.

  6. Алгоритмические проблемы в логике и математике.

  7. Разрешимые и перечислимые множества и предикаты.


4.3. Вопросы для экзамена

  1. Основные черты алгоритмов.

  2. Числовые функции и алгоритмы их вычисления.

  3. Примитивно рекурсивные функции.

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

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

  6. Машины с неограниченными регистрами.

  7. Рекурсивные и рекурсивно-перечислимые множества.

  8. Рекурсивно-перечислимые предикаты.

  9. Нумерации.

  10. Универсальная функция.

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


5. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ


Студент, изучивший дисциплину, должен знать основные факты и теоремы из теории алгоритмов.

Студент, изучивший дисциплину, должен уметь:

– доказывать рекурсивность функций;

– составлять программы для машины Тьюринга и для МНР;

– составлять схему нормального алгоритма.

6. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ


6.1.Рекомендуемая литература


Основная


  1. Игошин, В.И. Задачник-практикум по математической логике [Текст]: учеб. пособие для студентов-заочников физ.-мат. фак. пед. ин-тов / В.И. Игошин. – Подольск: Академия, 2005. – 156 с.

  2. Ильиных, А.П. Теория алгоритмов [Текст]: учебное пособие / А.П. Ильиных; Урал. гос. пед. ун-т. – Екатеринбург: УрГПУ, 2006. – 148 c.

  3. Лавров, Н.Я. Задачи по теории множеств, математической логике и теории алгоритмов [Текст] / Н.Я. Лавров, Л.Л. Максимова. – 5-е изд. – М.: Физмалит, 2004. – 256 с.

  4. Мальцев, А. И. Алгоритмы и рекурсивные функции [Текст] / А.И. Мальцев. – М.: Наука, 1986. – 386 с.



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


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

  2. Верещагин, Н.К. Вычислимые функции. [Текст] / Н.К. Верещагин, А. Шень. – М.: МЦНМО, 1999. – 321 с.

  3. Вялый, М.Н. Сложность вычислительных задач [Текст] / М.Н. Вялый // Математическое просвещение. – М.: МЦНМО, 2000. – Вып.4. – С. 81-114.

  4. Гэри М. Вычислительные машины и труднорешаемые задачи [Текст] / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 117 с.

  5. Ершов, Ю.Л. Математическая логика [Текст]: учеб. пособие для вузов / Ю.Л. Ершов, Е.А. Палютин. – 4-е изд. стер. – СПб.: Лань, 2005. – 336 с.

  6. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций [Текст] / Н. Катленд. – М.: Мир, 1983. – 214 с.

  7. Разборов, А.А. О сложности вычислений [Текст] / А.А. Разборов // Математическое просвещение. – М.: МЦНМО, 1999. – Вып.3. – С. 127-141.

  8. Шенфилд, Д.Р. Математическая логика [Текст] / Д.Р. Шенфилд. – М.: Наука, 1975. – 527 с.



6.2. Информационное обеспечение дисциплины


Локальная сеть математического факультета УрГПУ, сайт кафедры алгебры и теории чисел, «Информационная обучающая среда».


7. СВЕДЕНИЯ ОБ АВТОРЕ ПРОГРАММЫ


Составитель:

Ильиных Анатолий Петрович, доктор физико-математических наук, доцент, заведующий кафедрой алгебры и теории чисел



Похожие:

Рабочая учебная программа по дисциплине «Теория алгоритмов» iconРабочая учебная программа по дисциплине «теория судебной экспертизы»
Рабочая учебная программа дисциплины «Теория судебной экспертизы» подготовлена в соответствии с Государственным образовательным стандартом...
Рабочая учебная программа по дисциплине «Теория алгоритмов» iconРабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов
Математическая логика и теория алгоритмов в соответствии требованиями фгос впо, утвержденного приказом Министра образования и науки...
Рабочая учебная программа по дисциплине «Теория алгоритмов» iconРабочая учебная программа по дисциплине теория и механизмы современного государственного управления
Рабочая учебная программа для магистров, обучающихся по направлению 081100. 68 «Государственное и муниципальное управление». М.:...
Рабочая учебная программа по дисциплине «Теория алгоритмов» iconРабочая учебная программа дисциплины «Теория информации»
Рабочая учебная программа дисциплины «Теория информации» составлена на основе госо по специальности «Вычислительная техника и программное...
Рабочая учебная программа по дисциплине «Теория алгоритмов» iconРабочая учебная программа по дисциплине Теория информации и кодирования
«Теория информации и кодирования». Теория информации исследует общие закономерности информационных процессов, позволяет оценить качество...
Рабочая учебная программа по дисциплине «Теория алгоритмов» iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...
Рабочая учебная программа по дисциплине «Теория алгоритмов» iconПрограмма дисциплины математическая логика и теория алгоритмов
Рабочая программа дисциплины "Математическая логика и теория алгоритмов" предназначена для студентов 3 курса
Рабочая учебная программа по дисциплине «Теория алгоритмов» iconУчебно-методический комплекс по дисциплине теория алгоритмов
Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать...
Рабочая учебная программа по дисциплине «Теория алгоритмов» iconРабочая учебная программа по дисциплине опд. Ф. 03 “
Теория и методика преподавания иностранных языков и культур, 031202. 65 – Перевод и переводоведение
Рабочая учебная программа по дисциплине «Теория алгоритмов» iconРабочая учебная программа по дисциплине «Теория социальных конфликтов»
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница