Geum.ru

Рабочая программа дисциплины: Теория алгоритмов для специальности 050202 «Информатика» (гр. 55, база основного общего образования)

Вид материалаРабочая программа

Содержание


Пояснительная записка
Тематический план
3. Сложность алгоритма
Итоговая контрольная работа
3. Содержание учебной дисциплины
Тема 1.7. Машина Тьюринга (4 ч.)
Тема 1.8. Нормальные алгоритмы Маркова (3 ч.)
Тема 1.9. Рекурсивные функции (4 ч.)
Тема 2.2. Вычислимые функции (1 ч.)
Тема 2.3. Множества (2 ч.)
Тема 2.6. Примеры алгоритмически неразрешимых проблем в математике и информатике (2 ч.)
Самостоятельная работа
Литература и средства обучения
Подобный материал:

Ульяновский педагогический колледж №4


РАБОЧАЯ ПРОГРАММА


дисциплины: Теория алгоритмов


для специальности 050202 «Информатика»

(гр.55, база основного общего образования)


г. Ульяновск

2009 г.

ОДОБРЕНА предметной (цикловой)

комиссией

Председатель ____________

Составлена в соответствии

Государственными требованиями

к минимуму содержания и уровню подготовки выпускника

по специальности

Заместитель директора

по учебной работе _____________

Автор: Бурдина М.И., преподаватель информатики высшей квалификационной категории

Рецензенты: Соснина Е.П., доцент УлГТУ, кандидат технических наук

Фомичева Н.М., преподаватель информатики УПК №4, высшая квалификационная категория

  1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Рабочая программа по дисциплине «Теория алгоритмов» разработана в соответст­вии с требованиями государственного образовательного стандарта по специальности 050202 «Информатика», утвержденного Министерством образования и науки Российской Федерации 30 мая 2006 года (регистрационный № 03-050202-П).

Данная дисциплина входит в блок предметной подготовки и в соответствии с учебным пла­ном по специальности рассчитана на 48 часов аудиторных занятий (30 часов – лекционные заня­тия, 18 часов – практические и лабораторные занятия).

Рабочая программа включает четыре раздела: пояснительную записку, тематическое плани­рование дисциплины, основное содержание дисциплины, перечень литературы и средств обу­чения.

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

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

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


Дисциплина «Теория алгоритмов» занимает важное место в теоретической ин­форматике. В информатике выделяются два направления – теоретическое и прикладное. При­кладная информатика обеспечивает непосредственное создание информационных систем и про­грамм­ного обеспечения для них, а также их применение для решения практических задач. Теоретическая информатика - дисциплина, ис­пользующая методы математики. Понятие алгоритма является центральным понятием теории алгоритмов и одним из главных понятий математики. Зарождение и развитие теории алгоритмов связано с фундаментальными достижениями выдающихся математиков: А.Тьюринга, А.Чёрча, Э.Поста, А.А.Маркова, А.Н.Колмогорова, Ю.В.Матиясевича. Объектами ее изучения явля­ются: вопросы формализации понятия алгоритма, вопросы алгоритмически неразрешимых проблем в математике и информатике, вопросы сложности алгоритма.

Курс основ теории алгоритмов связан с такими дисцип­линами предметной подготовки, как «Основы теории информации», «Дискретная математика», «Математическая логика», «Программирование».

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

Содержание дисциплины реализуется в общем курсе лекций, в процессе практических занятий и самостоятельной работы студентов.

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

Практическая часть курса направлена на применение полученных теоретических знаний в решении следующих задач:
  • построение машины Поста;
  • построение машины Тьюринга;
  • создание нормальных алгоритмов Маркова;
  • определение сложности различных алгоритмов.

В результате освоения учебной дисциплины «Теория алгоритмов» студенты должны знать:
    • элементы теории алгоритмов;
    • основные этапы решения задач с помощью ЭВМ.

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


  1. ТЕМАТИЧЕСКИЙ ПЛАН

Наименование разделов и тем

Макс.

Учебная

на­грузка

сту­дента

(час.)

Количество аудиторных часов

при очной форме обучения

Самост.

работа

сту­дента (час.)

Всего

Лекции

Практ. и

лаборат.

занятия

1

2

3

4

5

6

Введение

2

2

2

1. Формализация понятия алгоритма компьютерные модели

29

22

13

9

7

1.1. Подходы к уточнению понятия алгоритма

3

2

2

2

1.2. Понятие исполнителя алгоритма

1

1

1

1.3. Графическое представление алгоритмов

4

2

1

1

2

1.4. Свойства алгоритмов

1

1

1

1.5. Понятие алгоритмического языка

3

2

1

1

1.6. Машина Поста

4

3

1

2

1

1.7. Машина Тьюринга

5

4

2

2

1

1.8. Нормальные алгоритмы Маркова

4

3

1

2

1

1.9. Рекурсивные функции

4

4

3

1


2. Вычислимые функции и разрешимые множества

14

10

10

4

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

1

1

1


2.2. Вычислимые функции

1

1

1


2.3. Множества

2

1

1

2

2.4. Нумерация алгоритмов

3

2

2


2.5. Разрешимые множества и перечислимые множества

2

2

2


2.6. Примеры алгоритмически неразрешимых проблем в математике и информатике

4

2

2

2

2.7. Проблема универсального алгоритма

1

1

1


3. Сложность алгоритма

11

11

3

8


3.1. Понятие сложности алгоритма

3

3

1

2


3.2. Анализ алгоритмов поиска

4

4

1

3


3.3. Анализ алгоритмов сортировки

4

4

1

3


Повторение

2

2

2


Итоговая контрольная работа

1

1

1


ИТОГО

59

48

30

18

11




3. СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ

Введение (2 ч.)

Студенты должны

знать:
  • два направления в информатике;
  • место дисциплины «Теория алгоритмов» в теоретической информатике;
  • содержание курса теории алгоритмов.

Информатика – фундаментальная наука. Два направления в информатике. История развития понятия «алгоритм». Теория алгоритмов как одна из составляющих теоре­тической информатики. Алгоритм как фундаментальное научное понятие.


Раздел 1. Формализация понятия алгоритма (22 ч.)

Студенты должны

знать:
  • подходы к формализации понятия «алгоритм»;
  • понятие исполнителя и формальность его действий для решения поставленных задач;
  • различные способы представления алгоритмов;
  • основные алгоритмические конструкции: композиция, альтернатива, итерация;
  • свойства неформального толкования понятия алгоритма;
  • понятие алгоритмического языка и вспомогательного алгоритма;
  • понятие рекурсивного алгоритма;
  • понятие прямой и косвенной рекурсии;
  • понятие машины Поста;
  • команды машины Поста;
  • понятие машины Тьюринга;
  • команды машины Тьюринга;
  • понятие ассоциативного исчисления;
  • понятие нормального алгоритма Маркова;
  • способы композиции нормальных алгоритмов;
  • понятия частичной функции, вычислимой частичной функции, полувычислимой функции, невычислимой функции;
  • понятия частично-рекурсивной функции, примитивно-рекурсивной функции;
  • формулировку тезис Чёрча.

уметь:
  • применять основные алгоритмические конструкции для изображения блок-схем алгоритмов;
  • применять вспомогательные алгоритмы для решения задач в среде алгоритмического языка;
  • составлять программы для машины Поста;
  • составлять программы для машины Тьюринга;
  • создавать алгоритмы Маркова для решения прикладных задач.


Тема 1.1. Подходы к уточнению понятия алгоритма (2 ч.)

Интуитивное (неформальное) понятие алгоритма. Необходимость в формализации понятия «алгоритм». Подходы к формализации понятия «алгоритм».

Самостоятельная работа

Составить хронологическую таблицу фундаментальных достижений (с указанием фамилий авторов и дат их жизни) в области теории алгоритмов.

Тема 1.2. Понятие исполнителя алгоритма (1 ч.)

Исполнитель. Система команд исполнителя. Среда исполнителя. Исполнитель – робот. Формальные действия исполнителя. Формальное решение задачи.

Тема 1.3. Графическое представление алгоритмов (2 ч.)

Различные способы представления алгоритмов. Конструкции для изображения блок-схем алгоритмов. Блок-схема как ориентированный граф. Три типа вершин графа. Основные алгоритмические конструкции: композиция, альтернатива, итерация.

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

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

Самостоятельная работа

Познакомиться с правилами оформления блок-схем алгоритмов в соответствии с ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД.


Тема 1.4. Свойства алгоритмов (1 ч.)

Свойства неформального толкования понятия алгоритма: дискретность, понятность, определенность (детерминированность), результативность, массовость.

Тема 1.5. Понятие алгоритмического языка (3 ч.)

Алгоритмический язык. Требования к записи алгоритма на алгоритмическом языке. Вспомогательный алгоритм. Встроенные (стандартные) вспомогательные алгоритмы. Рекурсивный алгоритм. Прямая и косвенная рекурсия. Алгоритмический язык исполнителя робот.

Практическое занятие 2. Составление алгоритмов решения задач на алгоритмическом языке.

Создание алгоритмов, содержащих алгоритмические конструкции: композиция, альтернатива, итерация.


Тема 1.6. Машина Поста (3 ч.)

Формализация понятия алгоритма в теории автоматов на примере машин Поста. Понятие машины Поста. Команды машины Поста. Программа для машины Поста. Примеры программ.

Практическое занятие 3. Составление программ для машины Поста.

Создание программ, содержащих алгоритмические конструкции: композиция, альтернатива, итерация.

Самостоятельная работа

Познакомиться с принципом работы программы-эмулятора машины Поста.


Тема 1.7. Машина Тьюринга (4 ч.)

Формализация понятия алгоритма в теории автоматов на примере машин Тьюринга. Понятие машины Тьюринга. Команды машины Тьюринга. Программа для машины Тьюринга. Примеры программ.

Практическое занятие 4. Составление программ для машины Тьюринга.

Создание программ, содержащих алгоритмические конструкции: композиция, альтернатива, итерация.

Самостоятельная работа

Познакомиться с принципом работы программы-эмулятора машины Тьюринга.


Тема 1.8. Нормальные алгоритмы Маркова (3 ч.)

Формализация понятия алгоритма в теории автоматов на примере нормальных алгоритмов Маркова. Понятие ассоциативного исчисления. Алфавит, буква, слово. Смежные слова. Эквивалентные слова. Понятие нормального алгоритма. Нормализуемый алгоритм. Способы композиции нормальных алгоритмов. Примеры нормальных алгоритмов.

Практическое занятие 5. Составление нормальных алгоритмов Маркова.

Создание нормальных алгоритмов для решения задач на использование подстановок.

Самостоятельная работа

Познакомиться с принципом работы программы-эмулятора нормальных алгоритмов Маркова.


Тема 1.9. Рекурсивные функции (4 ч.)

Формализация понятия алгоритма на основе теории рекурсивных функций. Простейшие функции. Частичная функция, вычислимая частичная функция, полувычислимая функция, невычислимая функция. Элементарные операции над частичными функциями: композиция, соединение, рекурсия. Частично-рекурсивная функция, примитивно-рекурсивная функция. Тезис Чёрча.

Практическое занятие 6. Решение задач по вычислению значений функций.

Использование элементарных операций над частичными функциями: композиция, соединение, рекурсия для определения значений функций.


Раздел 2. Вычислимые функции и разрешимые множества (10 ч.)

Студенты должны

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

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

Тема 2.1. Эквивалентность различных теорий алгоритмов (1 ч.)

Равносильность теории машин Тьюринга, теории машин Поста, нормальных алгоритмов Маркова и рекурсивных функций. Теорема о совпадении классов функций.

Тема 2.2. Вычислимые функции (1 ч.)

Понятие вычислимой функции. Теория вычислимых функций. Эффективная вычислимость. Эквивалентность утверждений «функция вычислима» и «существует алгоритм, вычисляющий функцию».


Тема 2.3. Множества (2 ч.)

Понятие множества, подмножества. Пустое множество, конечное множество, бесконечное множество. Способы задания множеств. Отношения между множествами. Операции над множествами.

Самостоятельная работа

Подготовить сообщение на тему «Теория множеств».


Тема 2.4. Нумерация алгоритмов (2 ч.)

Нумерация множества. Нумерация программ. Эффективно-счетное множество. Нумерация вычислимых функций.

Тема 2.5. Разрешимые множества и перечислимые множества (2 ч.)

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

Тема 2.6. Примеры алгоритмически неразрешимых проблем в математике и информатике (2 ч.)

Математические проблемы Д.Гильберта. Проблема «самоприменимости» алгоритма. Проблема распознавания выводимости. Тезис Черча. Проблема «остановки». Метод сведения как метод доказательства алгоритмической неразрешимости.

Самостоятельная работа

Подготовить компьютерную презентацию по теме «Алгоритмически неразрешимые проблемы в информатике».


Тема 2.7. Проблема универсального алгоритма (1 ч.)

Понятие универсальной функции. Вычислимость универсальной функции. Теорема о существовании универсального алгоритма.

Раздел 3. Сложность алгоритма (11 ч.)

Студенты должны

знать:
  • понятие сложности алгоритма;
  • понятие временной сложности;
  • понятие теоретической сложности;
  • понятие эффективности алгоритма;
  • зависимость сложности алгоритма от размерности задачи.

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

Тема 3.1. Понятие сложности алгоритма (3 ч.)

Понятие сложности алгоритма. Временная сложность. Теоретическая сложность: линейная, квадратичная, кубическая. Эффективность алгоритма.

Практическое занятие 7. Решение задач на определение сложности алгоритма.

Вычисление сложности алгоритмов, имеющих линейную структуру.


Тема 3.2. Анализ алгоритмов поиска (4 ч.)

Последовательный поиск в неупорядоченном массиве: алгоритм последовательного поиска в неупорядоченном массиве, алгоритм поиска минимального элемента в неупорядоченном массиве, эффективный алгоритм поиска в неупорядоченном массиве максимального и минимального элементов одновременно. Алгоритм бинарного поиска в упорядоченном массиве.

Практическое занятие 8. Составление эффективного алгоритма поиска.

Составление алгоритма поиска в неупорядоченном массиве максимального и минимального элементов одновременно.


Тема 3.3. Анализ алгоритмов сортировки (4 ч.)

Алгоритм обменной сортировки методом «пузырька». Сортировка выбором. Сортировка вставками. Сортировка слиянием.

Практическое занятие 9. Определение сложности алгоритмов сортировки.

Определение сложности алгоритма сортировки выбором. Определение сложности алгоритма сортировки вставками. Определение сложности алгоритма сортировки слиянием.


  1. ЛИТЕРАТУРА И СРЕДСТВА ОБУЧЕНИЯ



Основная учебная литература
  1. Андреева Е.В. Математические основы информатики. Элективный курс: Учебное пособие / Е.В. Андреева, Л.Л. Босова, И.Н. Фалина – М.: БИНОМ. Лаборатория знаний, 2005 – 328 с.: ил.
  2. Стариченко Б.Е. Теоретические основы информатики: Учебное пособие для вузов. – 2-е изд. перераб. и доп. – М.: Горячая линия – Телеком, 2004. – 312 с.; ил.
  3. Теория алгоритмов: учебник / Д.Ш. Матрос, Г.Б. Поднебесова. – М. : БИНОМ. Лаборатория знаний, 2008. – 202 с. : ил. – (Педагогическое образование).



Дополнительная учебная литература
  1. Информатика: базовый курс: Учебник для студентов вузов, бакалавров, магистров, обу­чающихся по направлениям «Информатика и вычислительная техника»/ О.А. Акулов, Н.В. Медведев. – М.: Омега-Л, 2004. – 552 с.
  2. Информатика: Учеб. пособие для студ. пед. вузов/ А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – 2-е изд., стер. – М.: Изд. центр «Академия», 2001. – 816 с.
  3. Практикум по информатике: Учеб. пособие для студ. высш. учеб. заведений/ А.В. Моги­лев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – 2-е изд., стер. – М.: Изд. центр «Академия», 2002. – 608 с.



Средства обучения

Аппаратные средства: IBM-компьютеры, принтер, сканер, звуковые колонки, микрофон, мультимедийный проектор.

Программные средства: операционная система Windows XP, программа-эмулятор машины Поста, программа-эмулятор машины Тьюринга, программа-эмулятор нормальных алгоритмов Маркова, программная среда объектно-ориентированного программирования.