Учебно-методический комплекс по дисциплине 230100 Теория алгоритмов Направление подготовки
| Вид материала | Учебно-методический комплекс |
- Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов», 69.99kb.
- Учебно-методический комплекс по дисциплине «Ботаника» Направление подготовки, 1843.23kb.
- Учебно-методический комплекс дисциплины б дв1 Теория систем и системный анализ Направление, 568.62kb.
- Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
- Учебно-методический комплекс по дисциплине опд. Ф. 04 Теория и методика обучения литературе, 2205.11kb.
- Учебно-методический комплекс умк учебно-методический комплекс теория и методика воспитания, 1435.61kb.
- Учебно-методический комплекс по дисциплине математическая логика и теория алгоритмов, 144.09kb.
- Учебно-методический комплекс по опд. Ф. 15 «Конституционное право зарубежных стран», 1206.51kb.
- Учебно-методический комплекс по дисциплине Теория систем Направление подготовки, 684.83kb.
- Учебно-методический комплекс дисциплины «Микроэкономика» Направление подготовки, 1978.69kb.
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Армавирская государственная педагогическая академия»
Институт прикладной информатики, математики и физики
Факультет прикладной информатики и информационных технологий
Кафедра информатики и информационных технологий обучения
УТВЕРЖДАЮ
Проректор по учебной работе
ФГБОУ ВПО «АГПА»
ТкаченкоИ.В.
« » 20 г.
Учебно-методический комплекс
по дисциплине 230100 Теория алгоритмов
Направление подготовки 230100 "Информатика и вычислительная техника"
Профиль подготовки (магистерская программа)
Бакалавр педагогического образования
Составитель: Бабенко Т.А.
Утверждено на заседании кафедры
П
ротокол № от Зав. Кафедрой Бельченко В.Е.
Армавир 2012
1. Цели освоения дисциплины
Целями освоения дисциплины «Теория алгоритмов» являются: овладеть культурой мышления, способностью к обобщению, анализу, воспроизведению индивидуальной постановки цели и выбору путей её решения
2.Место дисциплины в структуре ООП бакалавриата
Данный курс предусмотрен в блоке «Математический и естественнонаучный цикл» В соответствии с учебным планом курс проводится в 2 семестре. Данный курс запланирован первым в этом блоке, следовательно, в ходе курса студент должен получить базовые знания по предмету и быть готовым к изучению других курсов этого блока.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
В результате освоения дисциплины обучающийся должен:
- Знать: теорию алгоритмов
- Уметь: разрабатывать компоненты программных комплексов и баз данных, использовать современные инструментальные средства и технологии программирования
- Владеть: навыками работы с компьютером как средством управления информацией
4. Структура и содержание дисциплины
Теория алгоритмов
| № п/п | ТЕМА | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля |
| 1 | Интуитивное представление об алгоритмах. Неформальное понятие алгоритма. | Лекции и лабораторные работы, всего 4 часов Самостоятельная работа 5 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 2 | Вычислимые функции, разрешимые и перечислимые множества | Лекции и лабораторные работы, всего 4 часа Самостоятельная работа 5 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 3 | Определение машины Тьюринга. Применение машины Тьюринга к словам. Конструирование машин Тьюринга. | Лекции и лабораторные работы, всего 4 Самостоятельная работа 5 часов | Опорный конспект Выполнить задания к лабораторным работам. |
| 4 | Вычислимые по Тьюрингу функции. Основная гипотеза теории алгоритмов. Машины Тьюринга и современные ЭВМ. | Лекции и лабораторные работы, всего 4 Самостоятельная работа 5 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 5 | Тьюрингов подход к понятию «алгоритм». Алгоритмически разрешимые и неразрешимые проблемы. | Лекции и лабораторные работы, всего 4 Самостоятельная работа 2 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 6 | Нормальные алгоритмы Маркова. Эквивалентность различных теорий алгоритмов. | Лекции и лабораторные работы, всего 4 Самостоятельная работа 2 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 7 | Рекурсивные функции. Тезис Черча | Лекции и лабораторные работы, всего 4 Самостоятельная работа 2 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 8 | Неразрешимые алгоритмические проблемы. | Лекции и лабораторные работы, всего 4 Самостоятельная работа 2 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 9 | Эффективные операции над вычислимыми функциями. | Лекции и лабораторные работы, всего 4 Самостоятельная работа 2 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 10 | Теорема о неподвижной точке. Общее понятие исчисления. Грамматики. | Лекции и лабораторные работы, всего 4 Самостоятельная работа 2 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 11 | Языки. Иерархия языков по Хомскому. Языки и машины. | Лекции и лабораторные работы, всего 4 Самостоятельная работа 2 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 12 | Основные меры сложности вычисления. | Лекции и лабораторные работы, всего 4 Самостоятельная работа 2 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 13 | Приложения теории алгоритмов в информатике. | Лекции и лабораторные работы, всего 4 Самостоятельная работа 2 часов | Опорный конспект Выполнить задания к лабораторным работам |
| 14 | Преобразование символьных данных в компьютере. Алгоритмы символьных преобразований. (числа, многочлены, выражения, дифференцирование, интегрирование). | лабораторные работы, всего 2 Самостоятельная работа 1 часов | Опорный конспект Выполнить задания к лабораторным работам |
| | Всего108 часов | Ауд.54,с.р.27 | |
| | Экзамен 2 семестр | 2 сем.Лек.26, л.р. 28, с.р.27 | |
5. Учебно-методическое и информационное обеспечение дисциплины
основная литература:
- Бауэр Ф.Л., Гооз Г.. Информатика. В 2-х тт. М., “Мир”, 1990.
- Вирт Н. Алгоритмы и структуры данных. М., “Мир”, 1989.
- Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск данных. М., “Мир”, 1978.
- Лавров И. А. , Максимов А. А.. Задачи по теории множеств, математической логике и теории алгоритмов. М., 1975.
- Мальцев А. И. Алгоритмы и рекурсивные функции. М., Наука,1965.
- Яблонский С.В.. Введение в дискретную математику. М., “Высшая школа”, 2001.
Дополнительная литература
- Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М-СПб-К, “Вильямс”, 2001.
- Горбатов В.А. Фундаментальные основы дискретной математики. М., “Наука. Физматлит”, 2000.
- Зубов В.С. Справочник программиста. М., “Филинъ”, 1999.
- Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М., ЛБЗ, 2001.
- Игошин В. И. Математическая логика и теория алгоритмов. – Саратов. Изд-во Саратовского университета, 1991 г.
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М., МЦМНО, 2001.
6. Материально-техническое обеспечение дисциплины (модуля)
Компьютерные классы, рабочее место с выходом в Интернет, комплекс лицензированного программного обеспечения
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и/ПООП ВПО по направлению и профилю подготовки:
230100 "Информатика и вычислительная техника. Профиль "Программное обеспечение средств вычислительной техники и автоматизированных систем"
Автор - Бабенко Т.А.
Рецензент (ы)________________________
Программа одобрена на заседании_____________________________________________
(Наименование уполномоченного органа вуза ( Ученый совет факультета)
от___________ года, протокол № _________ .
I. Пояснительная записка
Курс «Теория алгоритмов» предназначен для подготовки будущих учителей информатики с целью овладения ими основными понятиями, приёмами систематизации и обобщения знаний, практическими навыками решения задач. Формализованные подходы к алгоритмам в информатике обладают высокой образовательной ценностью. Абстрактные машины Тьюринга и Поста являются прекрасными средствами освоения алгоритмизации даже при безмашинном варианте преподавания информатики начиная со средних классов школы.
В результате изучения курса «Теория алгоритмов» будущий учитель должен глубоко понимать взаимосвязь этого курса с другими дисциплинами, знать основные направления в подходах к формализации понятия алгоритма, их сущность:
- первое направление связано с уточнением понятия эффективно вычислимой функции;
- второе направление связано с машинной математикой;
- третье направление связано с понятием нормальных алгоритмов;
- знать основные формулы и определения;
- иметь понятие о сложности решения задач;
- владеть практическими навыками решения задач.
Особенностью учебной программы данного курса является его связь с такими дисциплинами как «Математическая логика» и «Теоретические основы информатики».
Изучение дисциплины базируется на проведении 28 часов практических занятий и 26-часовом лекционном курсе.
Текущий контроль осуществляется при проведении практических занятий.
Итоговый контроль проводится в форме экзамена. Порядок его проведения и выносимые вопросы сообщаются студентам заблаговременно, в соответствии с требованиями нормативных документов и деканата факультета. Используется балльно-рейтинговая система.
Учебно-материальная база курса включает нормативные документы высшего профессионального образования, нормативные документы в области информации, информатизации и защиты информации, сборники лекций и другую учебно-методическую литературу, специализированные компьютерные классы и технические средства обучения.
Распределение компетенций, формируемых в ходе изучения дисциплины
| Коды компетенций | Название компетенции | Форма текущего контроля качества компетенции |
| ОК - Общекультурные компетенции профиля | | |
| ОК-1 | Владеть культурой мышления, способностью к обобщению, анализу восприятия индивидуальной постановке цели и выбору путей её достижения | Опорный конспект Выполнить задания к лабораторным работам |
| ОК-6 | Стремиться к самостоятельному повышению своей квалификации и мастерства | Опорный конспект Выполнить задания к лабораторным работам |
| ОК 10 | Использовать основные законы естественно-научных достижений в профессиональной деятельности, применять математический анализ и моделирование, теоретическое и экспериментальное исследование | Опорный конспект Выполнить задания к лабораторным работам |
| ОК-11 | Осознавать сущность и значение информации в развитии современного общества, использовать основные методы и способы получения, хранения, передачи информации | Опорный конспект Выполнить задания к лабораторным работам |
| ОК-12 | Иметь навыки работы с компьютером как средством получения информации | Опорный конспект Выполнить задания к лабораторным работам |
| ПК - профессиональные компетенции профиля | | |
| ПК–2 | Осваивать методики использования ПК для решения практических задач | Опорный конспект Выполнить задания к лабораторным работам |
| ПК-3 | Разрабатывать интерфейс «человек-ЭВМ» | Опорный конспект Выполнить задания к лабораторным работам |
| ПК-5 | Разрабатывать компоненты программных комплексов и баз данных, использовать современные инструментальные средства и технические программы | Опорный конспект Выполнить задания к лабораторным работам |
| ПК-6 | Обосновывать принимаемые проектные решения, осуществлять постановку и выполнение эксперимента по проверке их корректности и эффективности | Опорный конспект Выполнить задания к лабораторным работам |
| ПСК - профессионально-специализированные компетенции в рамках профиля | | |
| | | |
II. ТЕМАТИЧЕСКИЙ ПЛАН