Учебно-методический комплекс по дисциплине теория алгоритмов

Скачать 410.53 Kb.

Название	Учебно-методический комплекс по дисциплине теория алгоритмов
страница	1/7
Дата публикации	01.02.2015
Размер	410.53 Kb.
Тип	Учебно-методический комплекс

top-bal.ru > Информатика > Учебно-методический комплекс

1 2 3 4 5 6 7

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

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

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

«Армавирская государственная педагогическая академия»

факультет прикладной информатики и информационных технологий

института прикладной информатики, математики и физики

кафедра информатики и информационных технологий обучения
Утверждено на заседании кафедры

информатики и ИТО АГПА

Протокол ___ от ”__”_______ 2012

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

(Бельченко В.Е.)

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС

по дисциплине
^

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

(факультет прикладной информатики и информационных технологий

института прикладной информатики, математики и физики)

для специальности

«ИНФОРМАТИКА И МАТЕМАТИКА»

Форма отчетности:

Зачет: 3 курс, 6 семестр
^

УМК подготовлен

доцентом кафедры информатики и ИТО

Нелиным В.М.

Армавир - 2012

АННОТАЦИЯ

Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать дальнейшему формированию логической и алгоритмической культуры будущих учителей информатики и информационных технологий.

Цели курса:

формирование представления о необходимости точного определения понятия алгоритм и о вариантах такого рода определений;
формирование представления о вычислимых функциях;
формирование представлений о рекурсивно-перечислимых и рекурсивных языках, их соотношении, проблеме останова;
формирование представлений о возможности существования неразрешимых и неперечислимых множеств, невычислимых функций;
формирование представлений о грамматиках, иерархиях языков по Хомскому;
формирование представлений о проблеме сложности вычислений, о теории NР- полноты.

Исходным пунктом курса служит недостаточность интуитивного определения алгоритма. Рассматривается описание вычислительного процесса, принимаемого в качестве формального определения понятия алгоритма, в терминах частично-рекурсивных функций и вычислительных устройств (машины Тьюринга и Поста).

Далее рассматриваются примеры невычислимой функции, алгоритмически неразрешимых проблем математики и информатики.

Введение в рассмотрение контекстно-свободных грамматик и языков позволяет выстроить иерархию языков по Хомскому.

В рамках знакомства с литературой внимание студентов, прежде всего, привлекается к классическим монографиям:

Хопкрофт Д.Э., Р. Мотвани, Ульман Д. Введение в теорию автоматов, языков и вычислений. М-СПб-К, “Вильямс”, 2002.

Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М-СПб-К, “Вильямс”, 2001.

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М., МЦМНО, 2001.

^

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

Курс "Теория алгоритмов" рассчитан на один семестр и призван упрочить фундамент специальной подготовки будущих педагогов, способствовать дальнейшему формированию логической и алгоритмической культуры будущих учителей информатики и информационных технологий.

Цели курса:

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

Исходным пунктом курса служит недостаточность интуитивного определения алгоритма. Далее, приводятся различные версии уточнений этого понятия, связанные с именами К. Геделя, А. Тьюринга, Э. Поста, А. Черча, Дж. фон Неймана, А. Маркова, С. Клини, А. Колмогорова, В. Успенского.

Рассматривается описание вычислительного процесса, принимаемого в качестве формального определения понятия алгоритма, в терминах частично-рекурсивных функций и вычислительных устройств (машины Тьюринга и Поста).

Далее рассматриваются примеры невычислимой функции, алгоритмически неразрешимых проблем математики и информатики.

Введение в рассмотрение контекстно-свободных грамматик и языков позволяет выстроить иерархию языков по Хомскому.

В рамках знакомства с литературой внимание студентов, прежде всего, привлекается к классическим монографиям:

Хопкрофт Д.Э., Р. Мотвани, Ульман Д. Введение в теорию автоматов, языков и вычислений. М-СПб-К, “Вильямс”, 2002.

Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М-СПб-К, “Вильямс”, 2001.

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М., МЦМНО, 2001.

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

Колмогоров А.Н. Теория информации и теория алгоритмов. - М.: Наука, 1987.

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

Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М., ЛБЗ, 2001.

Новиков Ф.А. Дискретная математика для программистов. Спб, “Питер”, 2001.

2. Тематический план учебной дисциплины

№ п/п	Раздел, тема	Всего часов	В том числе аудиторных			Самостоятельная работа, час
№ п/п	Раздел, тема	Всего часов	Всего аудиторных	Лекций	Практических	Самостоятельная работа, час
	Понятие вычислимой функции. Разрешимые и перечислимые множества.
	Введение. Интуитивное определение алгоритма. Понятие конструктивного пространства и вычислимой функции.	2	1	1		1
	Конечные и бесконечные машины. Понятие программы.
	Конечные автоматы и регулярные языки. Понятия языка и алфавита. Определение ДКА.	10	5	3	2	5
	Конечные автоматы и регулярные языки. Понятие НКА.	8	4	2	2	4
	Регулярные языки и регулярные выражения.	8	4	2	2	4
	Контрольная работа № 1	4	2		2	2
	Эффективная нумерация программ. Теорема о параметризации. Существование универсальной программы. Компьютер фон Неймана. Диагональный метод. Пример невычислимой функции. Проблема останова.
	Формализация машины Тьюринга (МТ).	8	4	2	4	4
	Упорядочение языков и программ. Классификация языков. Рекурсивно-перечислимые и рекурсивные языки. Компьютер фон Неймана и МТ.	4	2	2		2
	Многоленточная машина Тьюринга. Эмуляция работы компьютера фон Неймановской архитектуры многоленточной МТ.	2	1	1		1
	Понятия вычислимой и частично вычислимой функций. Проблема останова МТ. Примеры алгоритмически неразрешимых проблем.	4	2	2		2
	Контрольная работа № 2	4	2		2	2
	Грамматики. Языки, иерархия языков по Хомскому. Языки и машины.
	Синтаксис и семантика языка. Порождающие грамматики Хомского как способ задания языка.	8	4	2	2	4
	Иерархия грамматик Хомского: свободные, контекстно-зависимые, контекстно-свободные и регулярные грамматики.	8	4	2	2	4
	Построение деревьев вывода в контекстно-свободных грамматиках.	8	4	1	2	4
	Контрольная работа № 3	4	2		2	2
	Формальная теория вычислимости (частично рекурсивные функции, регистровые машины). Тезис Чёрча. Эффективные операции над вычислимыми функциями. Теорема о неподвижной точке. Общее понятие исчисления.
	Примитивно-рекурсивные, частично-рекурсивные и общерекурсивные функции.	8	4	2		4
	Формальная теория вычислимости. Регистровые машины.	8	4	2	2	4
	Общее понятие исчисления.	8	4	2		4
	Основные меры сложности вычисления. Основы теории NР- полноты. Применение теории NР- полноты для анализа сложности проблем.
	Основные меры сложности вычисления. Основы теории NР- полноты. Применение теории NР- полноты для анализа сложности.	4	2	2	2	2
	ИТОГО	108	54	28	26	54

^ 3. СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ
3.1. Содержание учебного материала: ЛЕКЦИИ