Министерство образования и науки РФ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Нижегородский государственный педагогический университет»
Факультет среднего профессионального образования
УТВЕРЖДАЮ Проректор
по учебно-методической деятельности
___________________________
«___» _________________20___г.
Рабочая ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ
ОП.06.9 Теория алгоритмов
Специальность 051001 Профессиональное обучение (по отраслям),
Специализация Программирование в компьютерных системах
Форма обучения: очная
Нижний Новгород
2011 г.
Рабочая программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта по специальности среднего профессионального образования 051001 «Профессиональное обучение» (по отраслям), утвержденный Министерством образования и науки РФ от 01.01.01 г. № 000.
Разработчик:
кандидат технических наук, доцент
Рекомендована кафедрой математики и информатики, протокол № 13 от 01.01.01 г.
Экспертным советом _________________________________________
____________________________________________________________________________________________________________________________________
Заключение Экспертного совета №_________ от «______» ___________20___ г.
СОДЕРЖАНИЕ
стр. | |
1. ПАСПОРТ Рабочей ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ | 4 |
| СТРУКТУРА и содержание УЧЕБНОЙ ДИСЦИПЛИНЫ | 5 |
| условия реализации Рабочей программы учебной дисциплины | 7 |
| Контроль и оценка результатов Освоения учебной дисциплины | 10 |
Паспорт рабочей программы учебной дисциплины
Теория алгоритмов
Область применения программы
Программа учебной дисциплины является частью основной профессиональной образовательной программы по специальности СПО 051001 «Профессиональное обучение » (по отраслям), специализации 230115 «Программирование в компьютерных системах».
Рабочая программа учебной дисциплины может быть использована при реализации программ дополнительного профессионального образования по соответствующему направлению подготовки.
1.2. Место учебной дисциплины в структуре основной профессиональной образовательной программы:
Дисциплина «Теория алгоритмов» относится к отраслевым общепрофессиональным дисциплинам обязательной части профессионального цикла ОПОП.
1.3. Цели и задачи учебной дисциплины - требования к результатам освоения учебной дисциплины:
В результате освоения учебной дисциплины обучающийся должен
уметь:
- разрабатывать алгоритмы для конкретных задач;
- определять сложность работы алгоритма.
знать:
- основные модели алгоритмов;
- методы построения алгоритмов;
- методы вычисления сложности алгоритмов.
1.4. Рекомендуемое количество часов на освоение программы учебной дисциплины:
максимальной учебной нагрузки студента 70 часов, в том числе:
обязательной аудиторной учебной нагрузки обучающегося 40 часов;
самостоятельной работы обучающегося 30 часов.
2. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ
2.1. Объем учебной дисциплины и виды учебной работы
Вид учебной работы | Объем часов |
Максимальная учебная нагрузка (всего) | 70 |
Обязательная аудиторная учебная нагрузка (всего) | 40 |
в том числе: | |
лабораторные работы | - |
практические занятия | 20 |
- | |
курсовая работа (проект) (если предусмотрено) | - |
консультации | - |
другие формы и методы организации образовательного процесса в соответствии с требованиями современных производственных и образовательных технологий | - |
Самостоятельная работа студента (всего) | 40 |
в том числе: | |
самостоятельная работа над курсовой работой (проектом) (если предусмотрено) | - |
Итоговая аттестация в форме зачета |
2.2. Тематический план и содержание учебной дисциплины ТЕОРИЯ АЛГОРИТМОВ
Наименование разделов и тем | Содержание учебного материала, лабораторные работы и практические занятия, самостоятельная работа обучающихся | Объем часов /зачетных единиц | Уровень освоения |
1 | 2 | 3 | 4 |
Тема 1. Алгоритмы в математике. Числовые функции и алгоритмы их вычисления | Содержание учебного материала | 2 | |
1 | Алгоритмы в математике. Основные черты алгоритмов. Необходимость уточнения понятия алгоритма. Числовые функции и алгоритмы их вычисления. Понятие вычислимой функции, разрешимого множества. | 2 | |
Практические занятия Особенности и свойства интуитивного понятия алгоритма | 2 | ||
Самостоятельная работа студента История возникновения и развития понятия алгоритма | 4 | ||
Тема 2. Частично рекурсивные функции. ТезисЧерч | Содержание учебного материала | 4 | |
1 | Частично рекурсивные функции и рекурсивные предикаты. Класс частично рекурсивных функций. Исходные функции. Операторы подстановки, примитивной рекурсии, минимизации. Рекурсивные предикаты. Логические операции. Ограниченные кванторы. Подстановка функций в предикат. Кусочное задание функции. | 2 | |
Практические занятия: Несчетность множества частичных арифметических функций. Вычислимые частичные арифметические функции и их эффективное перечисление. Невычислимые частичные функции | 4 | ||
Самостоятельная работа студента: Теорема Черча (невозможность эффективного распознавания точек неопределенности вычислимой частичной функции). | 4 | ||
Тема 3. Машины Тьюринга и машины с неограниченными регистрами | Содержание учебного материала | 2 | |
1 | Машины Тьюринга. Понятие машины Тьюринга. Операции с машинами. Тезис Черча-Тьюринга. . | 2 | |
Практические занятия: Универсальные машины | 2 | ||
Самостоятельная работа студента: Машина Тьюринга: принцип действия, описание работы | 4 | ||
Тема 4. Нумерации и универсальные функции | Содержание учебного материала | 4 | |
1 | Рекурсивные и рекурсивно-перечислимые множества. Рекурсивно-перечислимые предикаты, их свойства. Нумерация. Универсальная функция. Теорема Клини. | 2 | |
Практические занятия: Примитивно-рекурсивные функции и базис Клини. | 4 | ||
Самостоятельная работа студента: Примитивная рекурсивность суммы и факториала. | 4 | ||
Тема 5. Нормальные алгоритмы Маркова | Содержание учебного материала | 2 | |
1 | Подстановки Маркова, понятие НАМ | 2 | |
Практические занятия: Принцип действия НАМ. | 2 | ||
Самостоятельная работа студента: Принцип нормализации Маркова. | 4 | ||
Тема 6. Неразрешимые алгоритмические проблемы | Содержание учебного материала | 4 | 2 |
1 | Несчетность множества арифметических функций. Вычислимые арифметические функции. Невычислимые функции. | ||
Практические занятия: Невозможность эффективного перечисления и сравнения вычислимых функций | 4 | ||
Самостоятельная работа студента: Алгоритмически неразрешимые проблемы. Примеры. | 4 | ||
Тема 7. Разрешимые и перечислимые множества и предикаты | Содержание учебного материала | 2 | 2 |
1 | Алгоритмическая сводимость. | ||
Практические занятия: Эквивалентность классов функций, вычисляемых по Тьюрингу, Маркову и рекурсивных функций. | 2 | ||
Самостоятельная работа студента: Алгоритмически разрешимость. | 6 | ||
Всего: | 70 |
Для характеристики уровня освоения учебного материала используются следующие обозначения:
1. – ознакомительный (узнавание ранее изученных объектов, свойств);
2. – репродуктивный (выполнение деятельности по образцу, инструкции или под руководством)
3. – продуктивный (планирование и самостоятельное выполнение деятельности, решение проблемных задач)
3. условия реализации Рабочей программы УЧЕБНОЙ дисциплины
3.1. Требования к минимальному материально-техническому обеспечению
Реализация учебной дисциплины требует наличия учебного кабинета.
Оборудование учебного кабинета: доска, раздаточный учебно-методический материал, таблицы, справочники, методические пособия.
3.2. Информационное обеспечение обучения
Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы
Основные источники:
Игошин, -практикум по математической логике [Текст]: учеб. пособие для студентов-заочников физ.-мат. фак. пед. ин-тов / . – Подольск: Академия, 2005. – 156 с. Ильиных, алгоритмов [Текст]: учебное пособие / ; Урал. гос. пед. ун-т. – Екатеринбург: УрГПУ, 2006. – 148 c. Лавров, по теории множеств, математической логике и теории алгоритмов [Текст] / , . – 5-е изд. – М.: Физмалит, 2007. – 256 с. Мальцев, и рекурсивные функции [Текст] / . – М.: Наука, 2006. – 386 с. Булос Дж. Вычислимость и логика [Текст] / Дж. Булос, , Р. Джеффри – М.: Мир, 2008. – 248 с.Дополнительные источники:
Верещагин, функции. [Текст] / , А. Шень. – М.: МЦНМО, 2009. – 321 с. Вялый, вычислительных задач [Текст] / // Математическое просвещение. – М.: МЦНМО, 2010. – Вып.4. – С. 81-114. ычислительные машины и труднорешаемые задачи [Текст] / М. Гэри, Д. Джонсон. – М.: Мир, 2008. – 117 с. Ершов, логика [Текст]: учеб. пособие для вузов / , . – 4-е изд. стер. – СПб.: Лань, 2005. – 336 с. ычислимость. Введение в теорию рекурсивных функций [Текст] / Н. Катленд. – М.: Мир, 2009. – 214 с. Разборов, А. А. О сложности вычислений [Текст] / // Математическое просвещение. – М.: МЦНМО, 2009. – Вып.3. – С. 127-141. Шенфилд, логика [Текст] / . – М.: Наука, 2010. – 527 с.4. Контроль и оценка результатов освоения УЧЕБНОЙ Дисциплины
Контроль и оценка результатов освоения учебной дисциплины осуществляется преподавателем в процессе проведения практических занятий и лабораторных работ, тестирования, а также выполнения обучающимися индивидуальных заданий, проектов, исследований.
Результаты обучения (освоенные умения, усвоенные знания) | Формы и методы контроля и оценки результатов обучения |
умения: - разрабатывать алгоритмы для конкретных задач; - определять сложность работы алгоритма. знания: - основные модели алгоритмов; - методы построения алгоритмов; - методы вычисления сложности алгоритмов. . | Текущий контроль: оценка выполнения оценка выполнения самостоятельной работы Промежуточный контроль: тестирование Итоговый контроль: зачет |
