030100. 00 Информатика с дополнительной специальностью icon

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



Название030100. 00 Информатика с дополнительной специальностью
страница1/4
Дата конвертации05.07.2012
Размер382.52 Kb.
ТипРабочая программа
  1   2   3   4

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

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

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

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


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

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


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

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

ДПП.Ф.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



  1   2   3   4




Похожие:

030100. 00 Информатика с дополнительной специальностью iconМатематическая логика
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности...
030100. 00 Информатика с дополнительной специальностью iconГеометрия Специальность 030100. 00 Информатика с дополнительной специальностью математика Физико-математический факультет Форма обучения дневная
Программу разработал старший преподаватель кафедры алгебры и геометрии, кандидат физико-математических наук
030100. 00 Информатика с дополнительной специальностью iconГеометрия Специальность 030100. 00 Информатика с дополнительной специальностью математика Физико-математический факультет Форма обучения дневная
Программу разработала старший преподаватель кафедры алгебры и геометрии, кандидат физико-математических наук
030100. 00 Информатика с дополнительной специальностью icon032100. 00 Математика с дополнительной специальностью
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности...
030100. 00 Информатика с дополнительной специальностью icon032100. 00 Математика с дополнительной специальностью
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности...
030100. 00 Информатика с дополнительной специальностью iconГеометрия Специальность 032100. 00 Математика с дополнительной специальностью физика Физико-математический факультет Форма обучения дневная
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности...
030100. 00 Информатика с дополнительной специальностью iconГеометрия Специальность 032100. 00 Математика с дополнительной специальностью физика Физико-математический факультет Форма обучения дневная
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности...
030100. 00 Информатика с дополнительной специальностью iconРабочая программа учебной дисциплины
Ооп: Специальность 032100. 00 Математика с дополнительной специальностью физика (код оксо 050201)
030100. 00 Информатика с дополнительной специальностью iconУчебно-методический комплекс учебной дисциплины
Ооп: Специальность 032100. 00 Математика с дополнительной специальностью физика (код оксо 050201)
030100. 00 Информатика с дополнительной специальностью iconМатематическая логика
Рабочая программа составлена на основании Государственного образовательного стандарта высшего профессионального образования по специальности...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов