Учебно-методический комплекс по дисциплине Б2 «Теория алгоритмов» Направление подготовки 230100 «Информатика и вычислительная техника»

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Армавирская государственная педагогическая академия»
Институт прикладной информатики, математики и физики

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

Кафедра информатики и информационных технологий обучения

УТВЕРЖДАЮ

Проректор по учебной работе

ФГБОУ ВПО «АГПА»

ТкаченкоИ.В.

« » 20 г.

Учебно-методический комплекс

по дисциплине Б2 «Теория алгоритмов»

Направление подготовки 230100 «Информатика и вычислительная техника»

Профиль подготовки «Программное обеспечение средств вычислительной техники и автоматизированных систем»

Квалификация выпускника - Бакалавр техники и технологии

(очная форма обучения)

Составитель: Бабенко Т.А.

Утверждено на заседании кафедры

Протокол № от

Зав. Кафедрой Бельченко В.Е.

Армавир 2012

Обоснование УМК

Учебно-методический комплекс по курсу «Теория алгоритмов» разработан в соответствии с требованиями ФГОС ВПО (федеральный или региональный компонент) к обязательному минимуму содержания и уровню подготовки дипломированного выпускника и предназначен для студентов, обучающихся по направлению «Информатика и вычислительная техника».

Учебно-методический комплекс дисциплины рекомендован к утверждению учебно-методической комиссией на заседании кафедры информатики и информационных технологий обучения от «_____» ___________ 20__ г., протокол № __.

Авторы (составители): Бабенко Т.А.

Рецензенты: ______________________________________
------------------------------------------------------------------------------------------------------------------
Учебно-методический комплекс дисциплины утвержден

на заседании Учебно-методической комиссии кафедры информатики и информационных технологий обучения

«____»_________________ 20___ г. протокол № ____

Председатель УМК __________________/ _________________________

(подпись) Ф.И.О.
Учебно-методический комплекс дисциплины утвержден на заседании УМС факультета прикладной информатики и информационных технологий

«____»_________________ 20___ г. протокол № ____

Председатель УМС ____________/ _______________

(подпись) Ф.И.О.

Учебно-методический комплекс дисциплины согласован с руководителем программы «Программное обеспечение средств вычислительной техники и автоматизированных систем»

«____»_________________ 20___ г.

Руководитель программы

_________________/ Бельченко В.Е./

(подпись) Ф.И.О.

СОДЕРЖАНИЕ

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

II. Распределение часов и учебно-тематический план дисциплины …………

III. Список рекомендуемой литературы ……………………………………….

IV. Рабочая программа дисциплины по выбору-11 «Программирование» «Программирование» (очная форма обучения) ……….

V. Рабочая учебная программа дисциплины «__» (заочная форма обучения).

VI. Материалы по используемым инновационным методам обучения …..

VII. Материалы, устанавливающие содержание и порядок проведения контрольных мероприятий ……………………………………………………..

VIII. Методические рекомендации по реализации дисциплины в учебно-воспитательном процессе …..................................................................................

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

X. Практикум

XI. Глоссарий

XII. Тестовые задания

XIII Дидактические материалы

XIV. Дополнительные материалы

I. Пояснительная записка
Краткая характеристика предмета изучения. В настоящее время постоянно растёт потребность страны в специалистах – профессионалах в области информационно- коммуникационных технологий, а не только в грамотных пользователях. Поэтому учебный курс «Теория алгоритмов» занимает одно из центральных мест в системе подготовки бакалавра техники и технологии и имеет как мировоззренческое, так и прикладное значение. В нем объединено фундаментальное теоретическое знание в области информатики, в частности, умение проектировать, строить алгоритмы, со знанием технологии их реализации в современных системах программирования.

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

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

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

Особенностью учебной программы данного курса является его связь с такими дисциплинами как «Математическая логика» и «Теоретические основы информатики».

Изучение дисциплины базируется на проведении 28 часов практических занятий и 26-часовом лекционном курсе.

Текущий контроль осуществляется при проведении практических занятий.

Итоговый контроль проводится в форме экзамена. Порядок его проведения и выносимые вопросы сообщаются студентам заблаговременно, в соответствии с требованиями нормативных документов и деканата факультета. Используется балльно-рейтинговая система.

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

Цель дисциплины. Главная цель - формирование системы понятий, знаний, умений и навыков в области современной теории алгоритмов. Дисциплина “Теория алгоритмов” призвана обеспечить высокую профессиональную подготовку в области изучения теоретических основ теории алгоритмов, дать студентам представление о возможностях языка алгоритмизации.

Задачи дисциплины:

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

Дисциплина “«Теория алгоритмов» ” входит в базовую часть профессионального цикла в соответствии с ФГОС ВПО бакалавриата по направлению 230100 «Информатика и вычислительная техника»

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

В результате изучения дисциплины «Теория алгоритмов» студент должен:

знать / понимать

классификацию и возможности современных инструментальных средств разработки программного обеспечения;
этапы решения задачи на компьютере;
основные алгоритмические конструкции: ветвление, цикл, вспомогательный алгоритм;
принципы структурного и модульного программирования;
базовые конструкции, основные типы и структуры данных языка программирования Паскаль;
способы постановки и спецификации задач для решения на ПЭВМ;
способы записи и документирования алгоритмов и программ;
способы испытания и отладки программ.

уметь

грамотно формулировать задачи, возникающие в практической деятельности для их решения с помощью ЭВМ;
формализовано описывать поставленные задачи;
разрабатывать оптимальные алгоритмы для решения поставленных задач;
реализовывать стандартные алгоритмы, поддерживающие работу с простыми данными и табличными данными в среде Turbo Pascal;
осуществлять постановку и спецификацию задачи для решения на ПЭВМ;
анализировать полученные результаты.

владеть

основными современными методами и средствами разработки корректных структурированных алгоритмов и программ;
технологией работы на персональной ЭВМ (ПЭВМ), правилами и приемами диалоговой работы на ПЭВМ при программировании типовых задач;
методами отладки и тестирования программ на ЭВМ в различных режимах.

Данный курс предусмотрен в блоке профессиональных дисциплин. В соответствии с учебным планом дисциплина изучается в 1 семестре.

Итоговый контроль проводится в 2 семестре в виде экзамена.

Текущий контроль осуществляется при проведении лабораторных работ, тестирования и выполнения контрольной работы.

Содержание курса определено требованиями Федерального государственного образовательного стандарта по направлению 230100 Информатика и вычислительная техника

II. Распределение часов и учебно-тематический план дисциплины

Таблица 1. Распределение трудоемкости (в часах) дисциплины

Форма обучения	Семестр, курс изучения	Объем часов	Часы аудиторных занятий:				Часы самост. работы	Форма текущего контроля	Формы рубежного и промежуточного контроля
			Всего	Из них:
				лекций	Практич. занятий	Лабораторн занятий
Очная	2	108	81	26	–	28	27	тестирование, контрольная работа, коллоквиум	Экзамен

В соответствии с требованиями ФГОС ВПО в результате освоения дисциплин обучающийся должен овладеть комплексом компетенций. Выполнение этого требования проверяется при аттестации образовательной программы, в том числе путём контроля остаточных знаний обучающихся.

Таблица 2.Распределение компетенций, формируемых в ходе изучения дисциплины

Коды компетенций	Название компетенции	Форма текущего контроля качества компетенции
ОК - Общекультурные компетенции профиля
ОК-1	Владеть культурой мышления, способностью к обобщению, анализу восприятия индивидуальной постановке цели и выбору путей её достижения	Опорный конспект Выполнить задания к лабораторным работам
ОК-6	Стремиться к самостоятельному повышению своей квалификации и мастерства	Опорный конспект Выполнить задания к лабораторным работам
ОК 10	Использовать основные законы естественно-научных достижений в профессиональной деятельности, применять математический анализ и моделирование, теоретическое и экспериментальное исследование	Опорный конспект Выполнить задания к лабораторным работам
ОК-11	Осознавать сущность и значение информации в развитии современного общества, использовать основные методы и способы получения, хранения, передачи информации	Опорный конспект Выполнить задания к лабораторным работам
ОК-12	Иметь навыки работы с компьютером как средством получения информации	Опорный конспект Выполнить задания к лабораторным работам
ПК - профессиональные компетенции профиля
ПК–2	Осваивать методики использования ПК для решения практических задач	Опорный конспект Выполнить задания к лабораторным работам
ПК-3	Разрабатывать интерфейс «человек-ЭВМ»	Опорный конспект Выполнить задания к лабораторным работам
ПК-5	Разрабатывать компоненты программных комплексов и баз данных, использовать современные инструментальные средства и технические программы	Опорный конспект Выполнить задания к лабораторным работам
ПК-6	Обосновывать принимаемые проектные решения, осуществлять постановку и выполнение эксперимента по проверке их корректности и эффективности	Опорный конспект Выполнить задания к лабораторным работам
ПСК - профессионально-специализированные компетенции в рамках профиля

III. Список рекомендуемой литературы

Основная литература

	Брой М., Румпе Б. Введение в информатику: сборник задач. Структурированное собрание упражнений с образцами решений./Пер. с нем. – М.: Научный мир, Диалог-МИФИ, 2000 – 374с.
	Брой М. Информатика. Основополагающее введение. Ч.4./Пер. с нем. – М.: Диалог – МИФИ, 1998 – 224с.
	Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
	Зюзьков В.М., Шелупанов А.А. Математическая логика и теория алгоритмов. Учебное пособие для вузов. – 2-е изд. – М.: Горячая линия – Телеком, 2007. – 176с.
	Игошин В.И. Математическая логика и теория алгоритмов. – Саратов: Издательство Саратовского университета, 1991.
	Козлов К.П. Алгоритмы: Учеб. пособие. – Л., ЛГПИ, 1989. – 39с.
	Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – 4-е изд. – М.: ФИЗМАТЛИТ, 2001. – 256с.
	Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. Серия «Учебники для вузов. Специальная литература». – Спбю: Издательство «Лань», 1999. – 288с.
	Мальцев А.И. Алгоритмы и рекурсивные функции. – 2-е изд. – М.: Наука, 1986.
	Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М.: Мир, 1972.
	Кейслер Г., Чен Ч. Теория моделей. - М.: Мир, 1977.
	Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – 2-е изд., перераб. и доп. – М.: Энергоатомиздат, 1988.-480с.
	Алферова З.А. Теория алгоритмов. – М.: Статистика, 1973.
	Манин Ю.И. Вычислимая и невычислимое, - М.: Сов. радио, 1980.
	Машины Тьюринга и вычислимые функции: Пер. с нем., - М.: МИР, 1972.
	Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. – М.: Сов. радио, 1974.
	Успенский В.А. Машина Поста. – М.: Наука, 1988.
	Языки и автоматы. Сборник переводов./Под ред. Маслова А.К. - М.: Мир.
	Могилев А.В. и др. Практикум по информатике: Учеб. пособие для студ. всш. учеб. заведений/ А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – М.: Издательский центр «Академия», 2001. – 608с.
	Могилев А.В. и др. Информатика: Учеб. пособие для студ. всш. учеб. заведений/ А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – М.: Издательский центр «Академия», 1999. – 608с.

Дополнительная литература

Бауэр Ф.Л., Гооз Г.. Информатика. В 2-х тт. М., “Мир”, 1990.
Вирт Н. Алгоритмы и структуры данных. М., “Мир”, 1989.
Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск данных. М., “Мир”, 1978.
Лавров И. А. , Максимов А. А.. Задачи по теории множеств, математической логике и теории алгоритмов. М., 1975.
Мальцев А. И. Алгоритмы и рекурсивные функции. М., Наука,1965.
Яблонский С.В.. Введение в дискретную математику. М., “Высшая школа”, 2001.
Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М-СПб-К, “Вильямс”, 2001.
Горбатов В.А. Фундаментальные основы дискретной математики. М., “Наука. Физматлит”, 2000.
Зубов В.С. Справочник программиста. М., “Филинъ”, 1999.
Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М., ЛБЗ, 2001.
Игошин В. И. Математическая логика и теория алгоритмов. – Саратов. Изд-во Саратовского университета, 1991 г.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М., МЦМНО, 2001.

Периодические издания

Журнал "КомпьютерПресс"
Журнал "Мир ПК"
Газета «Информатика» (приложение к газете «Первое сентября»)

Интернет-ресурсы

http://pas1.ru/pascaltextbook
http://www.pascal7.ru/
http://alfa47.narod.ru/pascale.htm
http://www.intuit.ru/department/pl/prinpas/1/
http://www.intuit.ru/department/pl/plpascal/
http://forcoder.ru/pascal/

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

ФГБОУ ВПО «Армавирская государственная педагогическая академия»

Институт прикладной информатики, математики и физики

Факультет прикладной информатики и информационных технологий

Кафедра информатики и информационных технологий обучения

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

« Б.2» «Теория алгоритмов»

Направление подготовки 230100 «Информатика и вычислительная техника»

Профиль "Программное обеспечение средств вычислительной техники и автоматизированных систем"

Степень выпускника бакалавр

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

Армавир – 2012 г.

Лист согласования
Составитель: Бабенко Татьяна Арутюновна,
кандидат педагогических наук, доцент

Рабочая программа дисциплины (модуля) утверждена

на заседании кафедры информатики и информационных технологий обучения

«____»_________________ 20___ г. протокол № ____

Заведующий кафедрой __________________/ Бельченко В.Е./

Рабочая программа дисциплины (модуля) утверждена

на заседании Учебно-методической комиссии кафедры информатики и информационных технологий обучения

«____»_________________ 20___ г. протокол № ____

Председатель УМК __________________/ ___________________________________

(подпись) Ф.И.О.

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

«____»_________________ 20___ г. протокол № ____

Председатель УМС ____________/ _______________

(подпись) Ф.И.О.
4.1. Цели освоения дисциплины

Краткая характеристика предмета изучения. В настоящее время постоянно растёт потребность страны в специалистах – профессионалах в области информационно- коммуникационных технологий, а не только в грамотных пользователях. Поэтому учебный курс «Теория алгоритмов» занимает одно из центральных мест в системе подготовки бакалавра техники и технологии и имеет как мировоззренческое, так и прикладное значение. В нем объединено фундаментальное теоретическое знание в области информатики, в частности, умение проектировать, строить алгоритмы, со знанием технологии их реализации в современных системах программирования.

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

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

4.2.Место учебной дисциплины в структуре ООП ВПО

Дисциплина “Теория алгоритмов” входит в базовую часть профессионального цикла в соответствии с ФГОС ВПО бакалавриата по направлению 230100 «Информатика и вычислительная техника»

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

4.3.Место дисциплины в структуре ООП
Таблица 4. Выписка из учебного плана

Форма обучения	Семестр	Трудоемкость		Лекции, час	Практич., час	Лаб.раб., час	СРС, час	Форма аттестации
		зач.ед.	час
очная	2	12	108	26	–	28	27	экзамен

Таблица 5. Содержательно-логические связи дисциплины (модуля)

Код дисциплины

Название дисциплины

Дидактический минимум содержания дисциплины

Содержательно-логические связи

Коды учебных дисциплин, практик

Коды формируемых компетенций

на которые опирается содержание учебной дисциплины

для которой содержание учебной дисциплины выступает опорой

Б.2

Теория алгоритмов

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

Нормальные алгоритмы Маркова. Эквивалентность различных теорий алгоритмов.

–

Б.3. Базы данных

Б.3. Инженерная и компьютерна

я графика

ОК1

ОК6

ОК10

ОК11

ОК-12

ПК-2

ПК-3

ПК5

ПК6

4.4. Требования к результатам освоения содержания дисциплины

Процесс изучения дисциплины направлен на формирование элементов следующих компетенций в соответствии с ФГОС ВПО бакалавриата по направлению 230100 «Информатика и вычислительная техника»

общекультурных (ОК):

Ок-1: Владеть культурой мышления, способностью к обобщению, анализу восприятия индивидуальной постановке цели и выбору путей её достижения

ОК-6: Стремиться к самостоятельному повышению своей квалификации и мастерства

ОК-10: Использовать основные законы естественно-научных достижений в профессиональной деятельности, применять математический анализ и моделирование, теоретическое и экспериментальное исследование

ОК-11: Осознавать сущность и значение информации в развитии современного общества, использовать основные методы и способы получения, хранения, передачи информации

ОК-12:имеет навыки работы с компьютером как средством управления информацией

Профессиональных (ПК):

ПК-2: осваивать методики использования программных средств для решения практических задач

ПК-3: разрабатывать интерфейсы "человек - электронно-вычислительная машина"

ПК-5: Разрабатывать компоненты программных комплексов и баз данных, использовать современные инструментальные средства и технические программы

ПК-6: Обосновывать принимаемые проектные решения, осуществлять постановку и выполнение эксперимента по проверке их корректности и эффективности

В результате изучения дисциплины «Теория алгоритмов» студент должен:

знать / понимать

классификацию и возможности современных инструментальных средств разработки программного обеспечения;
сущность и значение информации в развитии современного общества,;
использовать основные методы и способы получения, хранения, передачи информации
принципы структурного и модульного программирования;
базовые конструкции, основные типы и структуры данных языка программирования Паскаль;
способы постановки и спецификации задач для решения на ПЭВМ;
способы записи алгоритмов и программ;
способы испытания и отладки программ.

уметь

Разрабатывать интерфейс «человек-ЭВМ»
формализовано описывать поставленные задачи;
разрабатывать оптимальные алгоритмы для решения поставленных задач;
Разрабатывать компоненты программных комплексов и баз данных
осуществлять постановку и спецификацию задачи для решения на ПЭВМ;
использовать современные инструментальные средства и технические программы

владеть

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

Обосновывать принимаемые проектные решения,
4.5. Структура и содержание дисциплины «Теория алгоритмов»
Таблица 6. Содержание дисциплины

№ раздела	Наименование раздела	Содержание раздела	Форма текущего контроля
	Интуитивное представление об алгоритмах. Неформальное понятие алгоритма.	Понятие алгоритма и его характерные черты. Уточнение понятия алгоритма. Алгоритм как формальная математическая система. Свойства алгоритма и его характерные черты. Формы представления алгоритмов.	защита лабораторных работ, тестирование
	Вычислимые функции, разрешимые и перечислимые множества	Разрешимые и перечислимые множества. Диагональный метод. Вычислимые функции. Частично рекурсивные и общерекурсивные функции. Тезис Черча.	защита лабораторных работ, тестирование, контрольные работы, реферат
	Определение машины Тьюринга. Применение машины Тьюринга к словам. Конструирование машин Тьюринга.	Абстрактные машины. Система команд.Примеры схем машины Тьюринга. . Вычислимые по Тьюрингу функции. Основная гипотеза теории алгоритмов.Машины Тьюринга и современные ЭВМ.	защита лабораторных работ, тестирование, контрольная работа.

следующая страница >>