Рабочая программа учебной дисциплины теория алгоритмов Уровень основной образовательной программы бакалавриат

Скачать 230.24 Kb.

Дата	08.11.2012
Размер	230.24 Kb.
Тип	Рабочая программа

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования

«Магнитогорский государственный университет»

УТВЕРЖДАЮ

Декан факультета

_____________________

(Подпись, ФИО)

«___» ______________________ 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. Материально-техническое обеспечение дисциплины: Учебный компьютерный класс

Рабочая программа учебной дисциплины теория алгоритмов Уровень основной образовательной программы бакалавриат

Похожие: