Рабочая программа дисциплины "Теория алгоритмов" для подготовки специалиста по специальности 030100 "



Скачать 64.26 Kb.
Дата15.01.2013
Размер64.26 Kb.
ТипРабочая программа
ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

РАБОЧАЯ ПРОГРАММА

дисциплины "Теория алгоритмов"

для подготовки специалиста по специальности 030100 "Информатика"

с дополнительной cпециальностью 032100 "Математика"

Всего: 90 час

52 час - ауд

Из них: 26 – лекции

26 – семинары

38 СРС

Форма отчетности – экзамен, 8 сем.

по уч. плану 2000-2001 уч. г.

Составитель: доц. В.В.Кравец

Программа утверждена на заседании

кафедры информатики и МПМ 10 мая

2001 г. протокол № 9

Заведующий кафедрой, профессор

______________________А.С. Потапов

Воронеж – 2001

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



Дисциплина "Теория алгоритмов" рассматривает основополагающие вопросы теоретической информатики.

Подробно рассматриваются понятие алгоритма, свойства и классификация алгоритмов, способы их формального описания и исполнения. Основные черты алгоритмических процессов. Определение конечных автоматов. Их графическое изображение. Языки, распознаваемые конечными автоматами. Эквивалентность конечных автоматов и недетерминированных конечных автоматов. Определение и примеры формальных грамматик. Контекстно–свободные и регулярные грамматики. Определение машин Шенфилда и функций, вычислимых на ней. Макросы. Тезис Черча. Теорема о параметризации (s-m-n-теорема). Машины Тьюринга. Определение. Простейшие машины Тьюринга. Операции на машинах Тьюринга и их свойства.

2. ТЕМАТИЧЕСКИЙ ПЛАН






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

Всего часов

Всего

Лекций

Лабор.

СРС

1.

Множества, их основные свойства и операции над ними. Понятие вычислимой функции. Разрешимые и перечислимые множества. График вычислимой функции. Формальная теория вычислимости.

34

24

12

12

10

2.

Общее понятие исчисления

16

8

4

4

8

3.

Формальные грамматики. Контекстно–свободные и регулярные грамматики.


16

8

4

4

8

4.

Основы теории NР- полноты

24

12

6

6

12


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





  1. Множества, их основные свойства и операции над ними. Некоторые основные понятия в теории множеств.

  2. Алфавиты и языки, длина слова, конкатенация слов, степени с натуральным показателем, звездочка Клини.

  3. Конечные автоматы и их основные свойства. Основные черты алгоритмических процессов. Определение конечных автоматов. Их графическое изображение.

  4. Языки, распознаваемые конечными автоматами. Эквивалентность конечных автоматов и недетерминированных конечных автоматов. Замкнутость языков, распознаваемых конечными автоматами, относительно объединения, пересечения, дополнения, конкатенации и звездочки Клини.

  5. Определение и примеры формальных грамматик. Контекстно–свободные и регулярные грамматики.

  6. Совпадение класса регулярных языков и языков, распознаваемых конечными автоматами. Алгоритмическая разрешимость множества слов контекстно–свободных языков.

  7. Замкнутость регулярных языков относительно объединения, пересечения, дополнения, конкатенации и звездочки Клини.

  8. Определение машин Шенфилда и функций, вычислимых на ней. Макросы.

  9. Теорема об элиминации макросов. Определение частично рекурсивных функций. Простейшие функции. Операторы суперпозиции, примитивной рекурсии, минимизации. Общерекурсивные функции. Примеры вычислимых функций. Вычислимые (рекурсивные предикаты).

  10. Кодирование последовательностей. Теорема о совпадении классов функций, вычислимых на машинах Шенфилда и класса частично рекурсивных функций. Тезис Черча. Теорема о параметризации (s-m-n-теорема). Теорема Клини о нормальной форме. Универсальные вычислимые функции.

  11. Машины Тьюринга. Определение. Простейшие машины Тьюринга. Операции на машинах Тьюринга и их свойства. Нормальные алгоритмы Маркова. Определение. Примеры.

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

  13. Понятие абстрактной сложности. Общее свойство функций сложности вычислений. Теорема Блюм об ускорении.


4. РЕКОМЕНДАЦИИ ПО ОРГАНИЗАЦИИ РАБОТЫ СТУДЕНТОВ.
Практические занятия по всем разделам с последующей проверкой домашней работы. Самостоятельное изучение отдельных вопросов и задач, предлагаемых на лекциях.

5. ЛИТЕРАТУРА


Основная литература

  1. М.Брой. Информатика. В 4 частях. М. Диалог МИМИ. 1998

  2. Ф.Бауэр, Г. Гооз. Информатика. М. Мир, 1976.

  3. Н. Катленд. Вычислимость.

  4. А.И. Мальцев. Алгоритмы и рекурсивные функции.

  5. Х. Роджерс. Теория рекурсивных функций и эффективная вычислимость.

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

  1. Р. Соар. Вычислимо перечислимые множества и степени.

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

  3. Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986.


6. РЕКОМЕНДАЦИИ ДЛЯ СРС
На самостоятельную работу выносятся следующие вопросы:

1. Теоретико-множественные упражнения (1).
2. Конечные автоматы (1).
3. Формальные грамматики (1)
4. Построение простейших алгоритмов для машин Шенфилда (1).
5. Частично рекурсивные функции (1).
6. Машины Тьюринга (2).
7. Нормальные алгоритмы Маркова (1).
8. Дальнейшие вопросы теории вычислимости (1).
7. ВОПРОСЫ К ЭКЗАМЕНУ
1. Понятие рекурсивной (вычислимой) функции. Машина с неограниченными регистрами, формализация Клини.

2. Канторовская нумерационная функция, ее значение. Нумерация пар, n-ок и конечных последовательностей натуральных чисел. Нумерация машин с неограниченными регистрами.

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

4. s-m-n-теорема и ее следствия.

5. Неразрешимость проблемы остановки. Другие неразрешимые проблемы.

6. Рекурсивные и рекурсивно перечислимые множества, их простейшие свойства. Теорема Поста о рекурсивно перечислимых множествах.

7. Основная теорема о рекурсивно перечислимых множествах.

8. Теорема о проекции. Теорема о графике рекурсивной функции.

9. Рекурсивно перечислимые и рекурсивные индексы множеств. Кано- нические индексы конечных множеств. Переходы от одних типов индексов к другим.

10. Теорема о неподвижной точке и ее следствия. Теорема об отсутствии алгоритма, оптимизирующего любую машину.

11. 1- и m-сводимости и степени, их простейшие свойства. 1- и m-полные множества. Устройство рекурсивных 1- и m- степеней.

12. Машины с оракулом. Принцип релятивизации.

13. Сводимость по Тьюрингу и Тьюринговы степени, их простейшие свойства. Операция скачка.

14. Арифметическая иерархия. Представление арифметических отношений в виде предикатной формы от рекурсивных.

15. Арифметическая иерархия. Теорема о нормальной форме.

16. Теорема Поста об арифметической иерархии.

Похожие:

Рабочая программа дисциплины \"Теория алгоритмов\" для подготовки специалиста по специальности 030100 \" iconУчебно-методический комплекс учебной дисциплины дпп. Ф. 10 Теория алгоритмов 030100. 00 Информатика с дополнительной специальностью
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности...
Рабочая программа дисциплины \"Теория алгоритмов\" для подготовки специалиста по специальности 030100 \" iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...
Рабочая программа дисциплины \"Теория алгоритмов\" для подготовки специалиста по специальности 030100 \" iconПрограмма дисциплины Социальные сети как средство коммуникаций  для специальности 032401. 65 «Реклама» подготовки специалиста
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов специальности 032401. 65 «Реклама»...
Рабочая программа дисциплины \"Теория алгоритмов\" для подготовки специалиста по специальности 030100 \" iconПрограмма дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки/ специальности...
Рабочая программа дисциплины \"Теория алгоритмов\" для подготовки специалиста по специальности 030100 \" iconРабочая программа дисциплины «основы теории цепей» Направление подготовки специалиста
Дисциплина относится к базовой (общепрофессиональной) части подготовки профессионального цикла С. 3 основной образовательной программы...
Рабочая программа дисциплины \"Теория алгоритмов\" для подготовки специалиста по специальности 030100 \" iconПрограмма дисциплины для направления/ специальности подготовки бакалавра/ магистра/ специалиста
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 040100. 62 «Социология»...
Рабочая программа дисциплины \"Теория алгоритмов\" для подготовки специалиста по специальности 030100 \" iconПрограмма дисциплины Социология науки и научного знания для направления 040200. 62 "Социология" подготовки бакалавра и специальности 040201. 65 "Социология" подготовки специалиста
Социология" подготовки бакалавра и специальности 040201. 65 "Социология" подготовки специалиста
Рабочая программа дисциплины \"Теория алгоритмов\" для подготовки специалиста по специальности 030100 \" iconПрограмма дисциплины «Письменная речь юриста»  для направления 030900. 62 «Юриспруденция» подготовки бакалавра Автор программы
Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления...
Рабочая программа дисциплины \"Теория алгоритмов\" для подготовки специалиста по специальности 030100 \" iconПрограмма дисциплины дпп. Ф. 02. «Дискретная математика» Специальность 030100 (050202. 65) информатика
Цель курса – дать студентам первоначальные знания по основам дискретной математики, заложить основы, необходимые для восприятия таких...
Рабочая программа дисциплины \"Теория алгоритмов\" для подготовки специалиста по специальности 030100 \" iconРабочая программа дисциплины «Теория функций комплексного переменного» предназначена для студентов 2 курса по специальности
Требования к уровню подготовки студента, завершившего изучение дисциплины «Теория функций комплексного переменного»
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org