032100. 00 Математика с дополнительной специальностью icon

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



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

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

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

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

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


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

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


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

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

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

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

(код ОКСО 050201)


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

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

4 курс: 8 семестр


Псков

2006


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

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

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

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


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

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

«Утверждаю»

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

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

«_____»______________200___г.


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

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

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

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

(код ОКСО 050201)


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

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

4 курс: 8 семестр

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

Лекции: 30

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

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

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

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

Псков

2007

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


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

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

31» января 2005 г.


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


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


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

«____»____________ 200 __ г.


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


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


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

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


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



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

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

Частично рекурсивные функции и рекурсивные предикаты. Класс частично рекурсивных функций. Исходные функции. Операторы подстановки, примитивной рекурсии, минимизации. Рекурсивные предикаты.

Логические операции. Ограниченные кванторы. Подстановка функций в предикат. Кусочное задание функции.

Машины Тьюринга. Понятие машины Тьюринга Операции с машинами. Тезис Черча-Тьюринга.

Рекурсивные и рекурсивно-перечислимые множества. Рекурсивно-перечислимые предикаты, их свойства. Рекурсивно-перечислимые множества. Нумерация. Универсальная функция. Теорема Клини. Неразрешимые алгоритмические проблемы. Алгоритмическая сводимость.

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


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

Всего часов

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

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

Лекции

Практики




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

16

6

2

8

Тема 2. Частично рекурсивные функции и предикаты

30

10

6

14

Тема 3. Машина Тьюринга

24

8

4

12

Тема 4. Рекурсивные и рекурсивно перечислимые множества и предикаты

20

6

4

10

ИТОГО:

90

30

16

44



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


Тема 1. Формальные системы и вычислимые функции.

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

Тема 2. Частично рекурсивные функции и предикаты.

Частично рекурсивные функции и рекурсивные предикаты. Класс частично рекурсивных функций. Исходные функции. Операторы подстановки, примитивной рекурсии, минимизации. Рекурсивные предикаты. Логические операции. Ограниченные кванторы. Подстановка функций в предикат. Кусочное задание функции.

Тема 3. Машина Тьюринга.

Машины Тьюринга. Понятие машины Тьюринга Операции с машинами. Тезис Черча-Тьюринга.

Тема 4. Рекурсивные и рекурсивно перечислимые множества и предикаты.

Рекурсивные и рекурсивно-перечислимые множества. Рекурсивно-перечислимые предикаты, их свойства. Рекурсивно-перечислимые множества. Нумерация. Универсальная функция. Теорема Клини. Неразрешимые алгоритмические проблемы. Алгоритмическая сводимость.


^ 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

  1   2   3   4




Похожие:

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


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

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