МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение высшего профессионального образования
«Магнитогорский государственный университет»
-
УТВЕРЖДАЮ
| Декан факультета
_____________________
(Подпись, ФИО)
«___» ______________________ 2011 г.
| РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ
Теория алгоритмов
Уровень основной образовательной программы бакалавриат
Направление(я) подготовки (специальность) 050100.62 «Педагогическое образование»
Профиль(и) Информатика и математика
Форма обучения очная Факультет информатики Кафедра информатики
Курс ___________3________________ Семестр_________5_______________
Учебный план набора 2011 года и последующих лет.
Распределение рабочего времени:
№
| Виды учебной работы
| Семестр 1
| Семестр 2
| Семестр 3
| Семестр 4
| Семестр 5
| Семестр 6
| Семестр 7
| Семестр 8
| Всего
| Единицы
| 1
| Лекции
|
|
|
|
| 18
|
|
|
| 18
| часов
|
| Лабораторные работы
|
|
|
|
| 18
|
|
|
| 18
| часов
|
| Практические занятия
|
|
|
|
|
|
|
|
|
| часов
|
| Курсовой проект/работа (КРС) (аудиторная)
|
|
|
|
|
|
|
|
|
| часов
|
| Всего аудиторных занятий (Сумма 1-4)
|
|
|
|
| 36
|
|
|
| 36
| часов
|
| Из них в интерактивной форме
|
|
|
|
| 12
|
|
|
| 12
| часов
|
| Самостоятельная работа студентов (СРС)
|
|
|
|
| 72
|
|
|
| 72
| часов
|
| Всего (без экзамена) (Сумма 5,7)
|
|
|
|
| 108
|
|
|
| 108
| часов
|
| Самост. работа на подготовку, сдачу экзамена
|
|
|
|
| 36
|
|
|
| 36
| часов
|
| Общая трудоемкость (Сумма 8,9)
|
|
|
|
| 144
|
|
|
| 144
| часов
|
| (в зачетных единицах)
|
|
|
|
| 4
|
|
|
| 4
| ЗЕТ
| Зачет _________________семестр Диф. зачет _________________ семестр
Экзамен _______5_______семестр
Магнитогорск 2011
Лист согласований Рабочая программа составлена с учетом требований Федерального Государственного образовательного стандарта высшего профессионального образования (ФГОС ВПО) третьего поколения по направлению подготовки (специальности) 050100.62 «Педагогическое образование», утвержденного 17 января 2011 года,
(дата утверждения ФГОС ВПО) рассмотрена и утверждена на заседании кафедры «___» __________ 2011 г., протокол № ________. Разработчики: зав кафедрой информатики _____________________ В.Е. Петеляк
(должность, кафедра) (подпись) (Ф.И.О.) Зав. кафедрой информатики _____________________ В.Е.Петеляк
(должность, кафедра) (подпись) (Ф.И.О.) Эксперты:
______________________________________________ _____________ ____________________
(место работы, занимаемая должность) (подпись) (Ф.И.О.) ______________________________________________ _____________ ____________________
(место работы, занимаемая должность) (подпись) (Ф.И.О.)
1. Цели и задачи дисциплины: формирование систематизированных знаний в области теории алгоритмов. 2. Место дисциплины в структуре ООП: Дисциплина относится к вариативной части профессионального цикла (Б3.В.ОД.6). Для освоения дисциплины студенты используют знания, умения и виды деятельности, сформированные в процессе освоения дисциплин «Алгебра и геометрия», «Математическая логика», «Дискретная математика». 3. Требования к результатам освоения дисциплины:
Процесс изучения дисциплины направлен на формирование следующих компетенций:
владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей её достижения (ОК–1)
способен реализовывать учебные программы базовых и элективных курсов в различных образовательных учреждениях (ПК-1)
способен использовать возможности образовательной среды, в том числе информационной, для обеспечения качества учебно-воспитательного процесса (ПК-4)
способен реализовывать аналитические и технологические решении в области программного обеспечения и компьютерной обработки информации (СК-4);
В результате изучения дисциплины студент должен:
Знать:
основные разделы указанной предметной области;
классические факты, утверждения и методы;
Уметь:
формулировать основные положения алгоритмического подхода;
формировать представления об основных теориях и концепциях теории алгоритмов;
Владеть:
навыками применения теоретико-алгоритмического подхода к решению задач.
4. Объем дисциплины и виды учебной работы
Общая трудоемкость дисциплины составляет ____4______ зачетных единиц.
Вид учебной работы
| Всего часов
| Семестры
| 5
|
|
|
| Аудиторные занятия (всего)
| 36
| 36
|
|
|
| В том числе:
| -
| -
| -
| -
| -
| Лекции
| 18
| 18
|
|
|
| Лабораторные работы (ЛР)
| 18
| 18
|
|
|
| Практические занятия (ПЗ)
|
|
|
|
|
| Семинары (С)
|
|
|
|
|
| Коллоквиумы (К)
|
|
|
|
|
| Курсовой проект/(работа) (аудиторная нагрузка)
|
|
|
|
|
| Другие виды аудиторной работы
|
|
|
|
|
| Самостоятельная работа (всего)
| 72
| 72
|
|
|
| В том числе:
| -
| -
| -
| -
| -
| Курсовой проект (работа) (самостоятельная работа)
|
|
|
|
|
| Расчетно-графические работы
|
|
|
|
|
| Подготовка реферата
| 20
| 20
|
|
|
| Подготовка презентации
| 6
| 6
|
|
|
| Другие виды самостоятельной работы
|
|
|
|
|
| Индивидуальное задание
| 10
| 10
|
|
|
| Вид промежуточной аттестации (зачет, экзамен)
| 36
| 36
|
|
|
| Общая трудоемкость час
| 144
| 144
|
|
|
| Зачетные Единицы Трудоемкости
| 4
| 4
|
|
|
| 5. Содержание дисциплины
5.1. Разделы дисциплин и виды занятий
№ п/п
| Наименование раздела дисциплины
| Лекции
| Лаборат.
занятия
| Практич.
занятия.
| Курсовой П/Р (КРС)
| Самост. работа студента
| Всего час. (без экзам)
| Формируемые компетенции
(ОК, ПК)
| 1.
| Формальная теория вычислимости
| 12
| 12
|
|
| 48
| 72
| ОК-1, ПК-1, ПК-4, СК-4
| 2.
| Элементы теории сложности
| 6
| 6
|
|
| 24
| 36
| ОК-1, ПК-1, ПК-4, СК-4
|
5.2. Содержание разделов дисциплины (по темам)
№ п/п
| Наименование разделов
| Содержание разделов
| Трудоемкость (час.)
| Формируемые компетенции
(ОК, ПК)
| 1.
| Формальная теория вычислимости
| Алгоритм. Свойства алгоритма. Понятие вычислимой функции. Разрешимые и перечислимые множества. Теорема Поста.
Формальная теория вычислимости. Алгоритмические модели. Алгоритмическая неразрешимость.
| 72
| ОК-1, ПК-1, ПК-4, СК-4
| 2.
| Элементы теории сложности
| Понятие сложности вычисления. Сложностные классы. Полиномиальная сводимость. NP-полные задачи.
| 36
| ОК-1, ПК-1, ПК-4, СК-4
|
5.3. Разделы дисциплины и междисциплинарные связи с обеспечивающими (предыдущими) и обеспечиваемыми (последующими) дисциплинами
№ п/п
| Наименование обеспечивающих (предыдущих) и обеспечиваемых (последующих) дисциплин
| № № разделов данной дисциплины из табл.5.1, для которых необходимо изучение обеспечивающих (предыдущих) и обеспечиваемых (последующих) дисциплин
| Раздел 1
| Раздел 2
|
|
| Предшествующие дисциплины
| 1.
| Алгебра и геометрия
| +
| +
|
|
| 2.
| Математическая логика
| +
| +
|
|
| 3.
| Дискретная математика
| +
| +
|
|
| Последующие дисциплины
| 1.
| Методика обучения информатике
| +
| +
|
|
| 2
| Практикум по решению задач повышенной сложности школьного курса по информатике
| +
| +
|
|
|
5.4. Соответствие компетенций, формируемых при изучении дисциплины, и видов занятий
Перечень компетенций
| Виды занятий
| Л
| Лаб
| Пр.
| КР/КП
| СРС
| ОК-1
| +
| +
|
|
| +
| ПК-1
| +
| +
|
|
| +
| ПК-4
| +
| +
|
|
| +
| СК-4
| +
| +
|
|
| +
| Л – лекция, Пр – практические и семинарские занятия, Лаб – лабораторные работы, КР/КП – курсовая работа/проект, СРС – самостоятельная работа студента
5.5. Соответствие компетенций, формируемых при изучении дисциплины, и видов контроля
Перечень компетенций
| Формы контроля по разделам дисциплины
(примеры)
| Раздел 1
| Раздел 2
|
|
| ОК-1
| Опрос на лекции
| Тест
|
|
| ПК-1
| Тест
| Опрос на лекции
|
|
| ПК-4
| Отчет по лабораторной работе
| Индивидуальное задание
|
|
| СК-4
| Индивидуальное задание
| Отчет по лабораторной работе
|
|
|
6. Методы и формы организации обучения
Технологии интерактивного обучения при разных формах занятий в часах
Формы
Методы
| Лекции (час)
| Практические/семинарские
Занятия (час)
| Тренинг
Мастер-класс (час)
| СРС (час)
| Всего
| Проблемная лекция
| 4
|
|
|
| 4
| Решение ситуационных задач
|
| 2
|
|
| 2
| ИТ-методы (E-leaning)
|
| 4
|
|
| 4
| Презентация рефератов
| 2
|
|
|
| 2
| Итого интерактивных занятий
| 6
| 6
|
|
| 12
|
7. Лабораторный практикум
№ п/п
| № раздела дисциплины из табл. 5.1
| Наименование лабораторных работ
| Трудо-емкость
(час.)
| Компетенции ОК, ПК
| 1.
| 1
| Вычислимые функции, разрешимые и перечислимые
множества
| 4
| ОК-1, ПК-1, ПК-4, СК-4
| 2.
| 1
| Машина Тьюринга
| 4
| ОК-1, ПК-1, ПК-4, СК-4
| 3.
| 1
| Нормальные алгоритмы Маркова
| 4
| ОК-1, ПК-1, ПК-4, СК-4
| 4.
| 2
| Временная сложность алгоритмов
| 6
| ОК-1, ПК-1, ПК-4, СК-4
| 5.
| 2
| Сложностные классы
| 4
| ОК-1, ПК-1, ПК-4, СК-4
|
8. Практические занятия (семинары)
№ п/п
| № раздела дисциплины из табл. 5.1
| Тематика практических занятий (семинаров)
| Трудо-емкость
(час.)
| Компетенции ОК, ПК
| 1.
|
|
|
|
| …
|
|
|
|
|
9. Самостоятельная работа
№ п/п
| № раздела дисциплины из табл. 5.1
| Тематика самостоятельной работы
(детализация)
| Трудо-емкость
(час.)
| Компетенции ОК, ПК
| Контроль выполнения работы (Опрос, тест, дом.задание, и т.д)
| 1.
| 1, 2
| Анализ и закрепление лекционного материала
| 18
| ОК-1, ПК-1, ПК-4, СК-4
| опрос
| 2.
| 1, 2
| Выполнение лабораторных работ
| 18
| ОК-1, ПК-1, ПК-4, СК-4
| Отчет по лабораторной работе
| 3.
| 2
| Индивидуальное задание (реализация и оценка алгоритма)
| 10
| ОК-1, ПК-1, ПК-4, СК-4
| Отчет по ИДЗ
| 4.
| 1
| Анализ литературы и других источников по заданной теме
| 20
| ОК-1, ПК-1, ПК-4, СК-4
| Реферат
| 5.
| 1
| Подготовка презентации по содержимому реферата.
| 6
| ОК-1, ПК-1, ПК-4, СК-4
| Презентация реферата
|
|
| Подготовка и сдача экзамена
| 36
|
| Оценка на экзамене
|
10. Примерная тематика курсовых проектов (работ)______________________________ 11. Учебно-методическое и информационное обеспечение дисциплины:
11.1 Основная литература
Верещагин Н.К., Шень А. Лекции по математической логики и теории алгоритмов. Часть 3. Вычислимые функции. 2-е изд, исправленное. – М.:МЦНМО, 2002.
Матрос Д.Ш. Теория алгоритмов: учебник / Д.Ш.Матрос, Г.СБ. Поднебесова. – М.: Бином. Лаборатория знаний, 2008. (Гриф УМО).
Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика. – М.: Academia, 2008.(Гриф УМО).
11.2 Дополнительная литература
Верещагин Н.К., Шень А. Лекции по математической логики и теории алгоритмов. Часть 2. Языки и исчисления. 2-е изд, исправленное. – М.:МЦНМО, 2002.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982.
Колмогоров А.Н. Теория информации и теория алгоритов. – М.: Наука, 1987.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – 5-е изд., исправл. – М.: ФИЗМАТЛИТ, 2004.
Разборов А.А. О сложности вычислений, Математическое просвещение, вып.3, стр. 127-141. – М.: МЦНМО, 1999.
Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. – М.: Наука. Гл. ред. Физ.-мат.лит., 1987.—(Б-чка программиста).
11.3 Программное обеспечение MS Word, MS Excel, FreePascal.
11.4 Базы данных, информационно-справочные и поисковые системы____________________ 12. Материально-техническое обеспечение дисциплины: Учебный компьютерный класс |