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




Скачать 410.53 Kb.
НазваниеУчебно-методический комплекс по дисциплине теория алгоритмов
страница1/7
Дата19.01.2013
Размер410.53 Kb.
ТипУчебно-методический комплекс
  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. Содержание учебного материала: ЛЕКЦИИ
  1   2   3   4   5   6   7

Похожие:

Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине математическая логика и теория алгоритмов
Сперанский Д. В., доктор технических наук, профессор кафедры «Высшая и прикладная математика»
Учебно-методический комплекс по дисциплине теория алгоритмов iconТеория и методика преподавания биологии учебно-методический комплекс по дисциплине
Теория и методика преподавания биологии: Учебно-методический комплекс по дисциплине для специальности 050102 Биология / Составитель...
Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине: опд. Ф. 01. Теория государства и права для специальности 030501. 65 «Юриспруденция» (заочная форма обучения)
Теория государства и права: учебно-методический комплекс / сост. А. В. Баранов. – Прокопьевск, 2010
Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине «Управленческие решения (теория и практика принятия управленческих решений)»
Учебно-методический комплекс обсужден и утвержден на заседании кафедры Экономики и менеджмента сервиса (протокол №9 от «19» марта...
Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине Б2 «Теория алгоритмов»
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального...
Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс умк учебно-методический комплекс теория и методика воспитания
...
Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине «Теория и методика обучения иностранному языку»
...
Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методическое пособие по дисциплине «Теория обучения»
Лукьянченко Т. Н. Теория обучения: учебно-методический комплекс по дисциплине «Теория обучения» для студентов, обучающихся по специальности...
Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс математические понятия
Информатика. Основной целью ее изучения является расширение и углубление знаний студентов по профессиональным дисциплинам «Теоретические...
Учебно-методический комплекс по дисциплине теория алгоритмов iconУчебно-методический комплекс по дисциплине дс. 02. 1
Учебно-методический комплекс по дисциплине дс. 02 “Экологическая анатомия растений” составлен в соответствии с требованиями Государственного...
Разместите кнопку на своём сайте:
Библиотека


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