Учебно-методический комплекс учебной дисциплины дпп. Ф. 10 Теория алгоритмов 030100. 00 Информатика с дополнительной специальностью icon

Учебно-методический комплекс учебной дисциплины дпп. Ф. 10 Теория алгоритмов 030100. 00 Информатика с дополнительной специальностью


Смотрите также:
Учебно-методический комплекс учебной дисциплины дпп. Ф. 10 Теория алгоритмов 032100...
Учебно-методический комплекс учебной дисциплины Математическая логика и теория алгоритмов...
Государственный образовательный стандарт высшего профессионального образования специальность...
Учебно-методический комплекс учебной дисциплины дпп. Р. 01. Математическое конструирование ооп...
Учебно-методический комплекс учебной дисциплины Математическое моделирование 032100...
Учебно-методический комплекс дисциплины «Исследование операций» Специальность 050202...
Учебно-методический комплекс дисциплины для студентов по специальности История с дополнительной...
Учебно-методический комплекс дисциплины для преподавателей по специальности История с...
Учебно-методический комплекс дисциплины для студентов по специальности История с дополнительной...
Учебно-методический комплекс дисциплины «Компьютерное моделирование» Специальность 050202...
Учебно-методический комплекс дисциплины «Теоретические основы информатики» Специальность 050202...
Учебно-методический комплекс по дисциплине теория чисел для специальности...



Загрузка...
страницы:   1   2   3
скачать
Министерство образования и науки Российской Федерации

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

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

имени С.М. Кирова


Физико-математический факультет

Кафедра алгебры и геометрии


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

учебной дисциплины

ДПП.Ф.10 Теория алгоритмов

030100.00 Информатика с дополнительной специальностью

(код ОКСО 050202)


Физико-математический факультет

Форма обучения дневная

3 курс: 6 семестр


Псков

2006

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

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

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

имени С.М. Кирова


Физико-математический факультет

Кафедра алгебры и геометрии



«Утверждаю»

Декан физико-математического факультета

_______________И.Н. Медведева

«_____»________________200___г.


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

учебной дисциплины

ДПП.Ф.10 Теория алгоритмов

030100.00 Информатика с дополнительной специальностью

(код ОКСО 050202)


Физико-математический факультет

Форма обучения дневная

3 курс: 6 семестр

Всего часов: 90

Лекции: 34

Практические занятия: 14

Лабораторные работы: 0

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

Экзамен: 6 семестр


Псков

2007

Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности 030100.00 Информатика с дополнительной специальностью.


Номер государственной регистрации

№ 662 пед/сп (новый)

31» января 2005 г.


ДПП.Ф.10 Теория алгоритмов


Рабочая программа принята на заседании кафедры алгебры и геометрии.


Протокол № ____ заседания кафедры

«____»____________ 200 __ г.


Программа разработана доцентом кафедры информатики


__________________________ В.Н. Мельник


Заведующий кафедрой алгебры и геометрии

________________________ И.Н. Медведева


^ 1. Пояснительная записка


1.1 Требования к содержанию учебной дисциплины из Государственного образовательного стандарта.

Понятие вычислимой функции. Разрешимые и перечислимые множества. График вычислимой функции. Формальная теория вычислимости (частично рекурсивные функции, регистровые машины, машины Тьюринга). Тезис Чёрча. Конечные и бесконечные машины. Понятие программы. Эффективная нумерация программ. Теорема о параметризации. Существование универсальной программы.

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

Грамматики. Языки, иерархия языков по Хомскому. Языки и машины. Основные меры сложности вычисления. Основы теории NР-полноты. Применение теории NР-полноты для анализа сложности проблем. Приложения теории алгоритмов в информатике.


^ 1.2 Цели и задачи дисциплины.

Цель дисциплины:

Овладение основными понятиями, идеями и методами теории алгоритмов, который представляет собой важный раздел математического аппарата информатики.

Задачи дисциплины:

Изучение центральных понятий и методов теории формальных грамматик.

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

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

Теория алгоритмов являются существенной частью математического аппарата информатики и вычислительной техники. Идеи и понятия теории алгоритмов лежат в основе современной теории и практики программирования. Теория формальных грамматик является основным средством описания языков программирования и построения трансляторов.

^ Требования к уровню подготовки по предмету

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

  • основные понятия теории формальных грамматик: классификацию Хомского, деревья вывода, принципы использования формальных грамматик для описания языков программирования;

  • требования к алгоритмам; определение и принцип функционирования машины Тьюринга;

  • понятие рекурсии, рекурсивной функции, оператора минимизации;

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

  • определения разрешимого и перечислимого множества;

  • определение конечного автомата и способы его задания; определение алгебры регулярных выражений; понятие эквивалентности состояний и автоматов.

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

  • строить дерево вывода для цепочек, выводимых в контекстно-свободных грамматиках;

  • строить простые машины Тьюринга и описывать протоколы их работы для конкретных данных;

  • строить разрешающие и перечисляющие процедуры для множеств, заданных словесными описаниями;

  • переходить от табличного задания конечного автомата к его графу переходов;

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

  • строить минимальный автомат, эквивалентный данному.

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

  • о прикладных логических исчислениях - исчислении с равенством, формальной арифметике и теореме Геделя о ее неполноте;

  • об алгоритмических проблемах теории грамматик;

  • об операциях над машинами Тьюринга;

  • о существовании перечислимого множества, которое не является разрешимым;

  • о мерах сложности вычислений, полиномиальной сводимости, классах P и NP и о понятии NP-полной задачи.

^ 1.3 Особенности построения дисциплины.

Теория алгоритмов является сравнительно новым разделом математики. Разработка её содержания требуют высокой квалификации, поскольку данная наука основана на серьезном теоретическом фундаменте.

   Курс «Теории алгоритмов» изучается в 6-м семестре, по курсу предусмотрен  экзамен. В целом на изучение курса отведено 96 часов, из которых   48  часов аудиторных.

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

Основные требования основаны на требованиях к уровню подготовки специалиста по дисциплинам предметной подготовки, определенных ГОС и Основной образовательной программой.

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

^ 2. Структура учебной дисциплины.


Наименование тем

^ Всего часов

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

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

Лекции

Практики




Тема 1. Формальные системы

16

6

2

8

Тема 2. Конечные автоматы

16

6

2

8

Тема 3. Вычислимые функции

22

8

4

10

Тема 4. Грамматики

18

6

4

8

Тема 5. Теория сложности вычислений

18

8

2

8

ИТОГО:

90

34

14

42


^ 3. Содержание учебной дисциплины


Тема 1. Формальные системы.

Общее понятие формальной системы. Алгоритмы в математике. Основные черты алгоритмов. Необходимость уточнения понятия алгоритма. Разрешимые и перечислимые множества. График вычислимой функции. Формальная теория вычислимости (частично рекурсивные функции, регистровые машины, машины Тьюринга). Тезис Чёрча.

Тема 2. Конечные автоматы.

Конечные и бесконечные машины. Понятие программы. Эффективная нумерация программ. Теорема о параметризации. Существование универсальной программы.

Компьютер фон Неймана. Диагональный метод.

Тема 3. Вычислимые функции.

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

Тема 4. Грамматики.

Общее понятие исчисления. Грамматики. Языки, иерархия языков по Хомскому. Языки и машины.

^ Тема 4.Теория сложности вычислений.

Основные меры сложности вычисления. Основы теории NР-полноты. Применение теории NР-полноты для анализа сложности проблем. Приложения теории алгоритмов в информатике.


^ 4. Методические материалы и рекомендации для преподавателя


4.1. Примерный перечень контрольных вопросов и заданий для самостоятельной работы.

    1. Является ли разрешимым множество всех булевых формул, эквивалентных данной?

    2. Всякое ли разрешимое множество является перечислимым?

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

    4. Можно ли построить машину Тьюринга, которая для произвольной функции, заданной своим описанием, отвечает на вопрос "принимает ли эта функция на некоторых данных значение 0"?

    5. Может ли конечный автомат распознавать палиндромы произвольной длины?

    6. Может ли конечный автомат распознавать язык {0n1n}?

    7. Принадлежит ли данное слово a языку, заданному регулярным выражением А?

    8. Построить грамматику, порождающую язык {anbmambn}.

    9. Для данного арифметического выражения построить его дерево вывода в грамматике арифметических выражений.

    10. Построить машину Тьюринга, вычисляющую предикат "слово a в алфавите {0, 1} - палиндром" (т.е. справа налево читается так же, как и слева направо).

    11. a - слово в алфавите {a, b, c}. Построить одноленточную машину Тьюринга, которая сохраняет в a в том же порядке буквы a, b и удаляет c, не оставляя пробелов. Например, T(acbbca)=abba.

    12. Построить конечный автомат, который для произвольного слова a в алфавите {a, b, c} отвечает на вопрос: содержится ли в a фиксированное слово b?

    13. Построить конечный автомат, реализующий заданное регулярное выражение.


^ 4.2. Примерный перечень тем рефератов.

  1. Формальные грамматики. Классификация Хомского. Грамматики типа 2 и их использование при построении трансляторов.

  2. Понятие неоднозначности в теории грамматик. Привести примеры неоднозначных грамматик и неоднозначного вывода в них.

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

  4. Основная идея доказательства существования универсальной машины Тьюринга и блок-схема ее построения.

  5. Общая схема доказательства эквивалентности машин Тьюринга и рекурсивных функций.

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

  7. Связь формальных грамматик и конечных автоматов.

  8. Сравнение сложности вычислений на одноленточной и многоленточной машинах Тьюринга на примере распознавания палиндромов в двухбуквенном алфавите.


^ 4.3. Примерный перечень вопросов к экзамену по всей дисциплине.

  1. Интерпретации и модели.

  2. Семантическая и формальная непротиворечивость.

  3. Полнота. Непротиворечивость и семантическая полнота исчисления высказываний.

  4. Теорема Геделя о полноте исчисления предикатов.

  5. Общее понятие формальной системы. Примеры.

  6. Формальная арифметика. Теорема Геделя о неполноте формальной арифметики (формулировка).

  7. Формальные языки и формальные грамматики и классификация Хомского.

  8. Контекстно-свободные грамматики и деревья вывода.

  9. Интуитивное понятие алгоритма. Требования к алгоритмам.

  10. Формализация понятия алгоритма и универсальные алгоритмические модели.

  11. Машина Тьюринга - основные определения. Понятие вычислимости на машине Тьюринга.

  12. Операции над машинами Тьюринга. Универсальная машина Тьюринга.

  13. Понятие алгоритмической неразрешимости. Теорема Райса.

  14. Проблема остановки - формулировка теоремы и ее доказательство.

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

  16. Неограниченный оператор минимизации. Примеры. Определение частично-рекурсивной функции.

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

  18. Конечные автоматы. Основные определения. Способы задания автоматов.

  19. Алгоритмические возможности: что могут и что не могут вычислять автоматы. Примеры.

  20. Эквивалентность автоматов. Алгоритм минимизации автоматов.

  21. Автоматы и логические схемы. Программная реализация автоматов.



^ 5. Формы и методы самостоятельной работы.


Реферат по указанной преподавателем теме согласно перечня 4.2.


6. Формы текущего, промежуточного и итогового контроля.


Контрольные работы, тестирование, экзамен.


7. Список литературы

Основная

  1. Вагин В.Н. и др. Теория алгоритмов и дедуктивный вывод: Учеб. пособие. – М., 1999.

  2. Гладкий А.В. Математическая логика. - М.: Российск. гос. гуманит. ун-т, 1998.

  3. Иванищев В.В. Введение в теорию алгоритмических сетей. – СПб, 2000.

  4. Информатика: Учебник /Под ред. Н.В. Макаровой. – М.: Финансы и статистика, 2002.

  5. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Физматлит, 2001.

  6. Лексаченко В. А. Логика. Множества. Вероятность. - М.: Вузовская книга, 2001.

  7. Лихтарников Л.М. Математическая логика: Учеб. для вузов. – СПб.: Лань, 1999.

  8. Мальцев Г.Н. Конспект лекций по курсу "Теория алгоритмов".– СПб., 1999.

  9. Мальцев Г.Н. Конспект лекций по курсу “Теория алгоритмов”. – СПб, 1999.

  10. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. – 2. изд./ Пер.с англ. - М.: Вильямс, 2002.


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

  1. Булос Дж., Джеффри Р. Вычислимость и логика. - М.: Мир, 1994.

  2. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. - М.: Наука, 1977.

  3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ/ Пер. с английского под ред. А.Шеня. - М.: МЦМНО, 2002.

  4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988.

  5. Мендельсон Э. Введение в математическую логику. - М.: Наука, 1984

  6. Роберт Р. Столл. Множества. Логика. Аксиоматические теории. - М.: Просвещение, 1968.



Методические указания студентам по подготовке к практическим занятиям.


Контролирующие материалы для аттестации студентов по дисциплине.


  1. Дополнение к области определения некоторой вычислимой функции _________ рекурсивно перечислимым

    1. может не быть

    2. разъединено с

    3. не может быть

    4. должно быть

  2. В системе Пеано единственным неопределимым отношением является









  3. Множество ________ тогда и только тогда, когда оно является _______ некоторой вычислимой функции

    1. перечислимо, множеством значений

    2. разрешимо, множеством значений

    3. разрешимо, областью определения

    4. перечислимо, областью определения

  4. Фразы, соединяемые функтором, называются

    1. аргументами

    2. формульными

    3. предложениями

    4. регулярными

  5. Если и рекурсия проводится по , то функция равна

    1. 0



    2. x+z



  6. Любая непротиворечивая система арифметики с рекурсивной системой аксиом

    1. совпадает с системой Пеано

    2. является замкнутой

    3. должна быть полной

    4. не может быть полной

  7. Утверждение арифметики Пеано называется неразрешенным, если оно

    1. противоречит системе аксиом

    2. и его отрицание опровержимы

    3. истинно, но недоказуемо

    4. и его отрицание -противоречивы

  8. Если , то функция в рекуррентной формуле равна

    1. m+1

    2. m(n+1)

    3. m!

    4. m+n+1

  9. Если и рекурсия проводится по , то функция равна



    1. t+x

    2. t+y



  10. Функция, полученная из вычислимой с помощью рекурсии, является

    1. вычислимой

    2. примитивно рекурсивной

    3. дифференцируемой

    4. частично рекурсивной

  11. Если , то функция в рекуррентной формуле равна





    1. 1



  12. Если , то функция (n,m) в рекуррентной формуле равна

    1. m+n-1

    2. 2m

    3. (m+n)/2

    4. m+n+1

  13. Множество номеров несамоприменимых машин Тью­ринга

    1. неразрешимо

    2. рекурсивно перечислимо

    3. неперечислимо

    4. рекурсивно

  14. Геделевский номер, равный , имеет функция









  15. Множество истинных утверждений

    1. носит название системы аксиом

    2. перечисляет все системы аксиом

    3. выводится из системы аксиом

    4. не выводится из системы аксиом

  16. Если и рекурсия проводится по переменной , то функция равна

    1. m+x

    2. 1

    3. m+y



  17. Показал возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру

    1. А. Тьюринг

    2. Д. Гильберт

    3. А. Марков

    4. К. Гёдель

  18. Машина Тьюринга есть совокупность компонент

    1. пяти

    2. двух

    3. четырех

    4. трех

  19. Множество натуральных чисел является

    1. только рекурсивным

    2. только перечислимым

    3. рекурсивным и перечислимым

    4. простейшим

  20. Полнота – это условие, что для любого утверждения  одно из утверждений  и 

    1. ложно

    2. доказуемо

    3. опровержимо

    4. истинно

  21. Если и рекурсия проводится по , то функция равна



    1. zy





  22. Существуют три основных класса фраз: имена, предложения и

    1. дизъюнкты

    2. функторы

    3. предикаты

    4. кванторы

  23. Система Пеано содержит аксиом

    1. 2

    2. 3

    3. 4

    4. 5

  24. Формализованный язык для однозначной записи алгоритмов называется

    1. автоматным языком

    2. регулярным языком

    3. метаязыком языком

    4. алгоритмическим языком

  25. Если множество не является множеством значений никакой функции, то оно

    1. нерекурсивно, но рекурсивно перечислимо

    2. рекурсивно, но не перечислимо

    3. нерекурсивно и неперечислимо

    4. рекурсивно, но не перечислимо

  26. Выражение является

    1. командой

    2. элементом алфавита

    3. исходной ситуацией

    4. машиной Тьюринга

  27. Если и рекурсия проводится по переменной , то функция равна

    1. m+y

    2. 2+m

    3. m+1

    4. m+x

  28. Усеченная разность равна

    1. 3

    2. 0

    3. -3

    4. 5

  29. Функция является

    1. частично вычислимой

    2. общерекурсивной

    3. вычислимой

    4. рекурсивной

  30. Формальная грамматика, позволяющая построить любую правильную цепочку символов, называется грамматикой

    1. нормальной

    2. автоматной

    3. регулярной

    4. порождающей

  31. Идея использования рекурсии для решения задач, связанных с основаниями математики, предложена

    1. Гильбертом

    2. Пеано

    3. Аль Хорезми

    4. Тьюрингом





  32. Скачать 391,19 Kb.
    оставить комментарий
    страница1/3
    Дата29.09.2011
    Размер391,19 Kb.
    ТипУчебно-методический комплекс, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3
Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

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

Рейтинг@Mail.ru
наверх