Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Московский государственный технический университет имени
(национальный исследовательский университет)»
Московский техникум космического приборостроения
рабочая ПРОГРАММа
общепрофессиональной дисциплины Теория алгоритмов
код, специальность 09.02.03 Программирование в компьютерных системах
Москва
2016
СОДЕРЖАНИЕ
стр. | |
| ПАСПОРТ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ | 3 |
| СТРУКТУРА и ПРИМЕРНОЕ содержание УЧЕБНОЙ ДИСЦИПЛИНЫ | 5 |
| условия реализации учебной дисциплины | 11 |
| Контроль и оценка результатов Освоения учебной дисциплины | 12 |
1 ПАСПОРТ РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ "Теория алгоритмов"
1.1 Область применения рабочей программы
Рабочая программа учебной дисциплины «Теория алгоритмов» является составной частью программы подготовки специалистов среднего звена (ППССЗ) в соответствии с ФГОС СПО по специальности 09.02.03 Программирование в компьютерных системах, входящей в состав укрупненной группы 09.00.00 Информатика и вычислительная техника.
Рабочая программа может быть использована в соответствии с ФГОС по специальностям СПО, входящим в состав укрупненной группы, а также в дополнительном профессиональном образовании (в программах повышения квалификации и переподготовки) и в профессиональной подготовке.
1.2 Место дисциплины в структуре основной профессиональной образовательной программы (ОПОП)
Дисциплина «Теория алгоритмов» входит в общепрофессиональные дисциплины профессионального цикла.
1.3 Цели и задачи дисциплины
В результате освоения дисциплины «Теория алгоритмов» обучающийся должен уметь:
У1 - разрабатывать алгоритмы для конкретных задач;
У2 - определять сложность работы алгоритмов;
В результате освоения учебной дисциплины обучающийся должен знать:
З1 - основные модели алгоритмов;
З2 - методы построения алгоритмов;
З3 - методы вычисления сложности алгоритмов.
1.4 Результаты освоения учебной дисциплины
Результатом освоения дисциплины «Теория алгоритмов» является овладение обучающимися профессиональными (ПК) и общими (ОК) компетенциями, представленными в таблице 1.1.
Таблица 1.1
Код | Наименование результата обучения |
ПК 1.1 | Выполнять разработку спецификаций отдельных компонент. |
ПК 1.2 | Осуществлять разработку кода программного продукта на основе готовых спецификаций на уровне модуля. |
ОК 1 | Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес |
ОК 2 | Организовывать собственную деятельность, определять методы и способы выполнения профессиональных задач, оценивать их эффективность и качество |
ОК 3 | Решать проблемы, оценивать риски и принимать решения в нестандартных ситуациях |
ОК 4 | Осуществлять поиск, анализ и оценку информации, необходимой для постановки и решения профессиональных задач, профессионального и личностного развития |
ОК 5 | Использовать информационно‑коммуникационные технологии для совершенствования профессиональной деятельности |
ОК 6 | Работать в коллективе и команде, обеспечивать её сплочение, эффективно общаться с коллегами, руководством, потребителями |
ОК 7 | Ставить цели, мотивировать деятельность подчинённых, организовывать и контролировать их работу с принятием на себя ответственности за результат выполнения заданий |
ОК 8 | Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации |
ОК 9 | Быть готовым к смене технологий в профессиональной деятельности |
1.5 Количество часов на освоение программы дисциплины
На освоение программы дисциплины «Теория алгоритмов» выделено следующее количество часов:
- максимальной учебной нагрузки обучающегося - 96 часов, в том числе:
- обязательной аудиторной учебной нагрузки - 64 часа; самостоятельной нагрузки обучающегося - 32 часа.
2 СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
2.1 Объём дисциплины и виды учебной работы
Объём учебной дисциплины «Теория алгоритмов» и виды учебной работы приведены в таблице 2.1.
Таблица 2.1
Вид учебной работы | Объём часов |
Максимальная учебная нагрузка (всего) | 96 |
Обязательная аудиторная учебная нагрузка (всего), | 64 |
в том числе: | |
теоретические занятия | 34 |
практические занятия | 18 |
лабораторные работы | 12 |
Самостоятельная работа студента (всего) | 32 |
в том числе: | |
выполнение домашних заданий | 20 |
изучение технической, специальной литературы | 12 |
Итоговая аттестация в форме дифференцированного зачёта |
2.2 Тематический план и содержание дисциплины
Тематический план и содержание дисциплины «Теория алгоритмов» приведены в таблице 2.2.
Таблица 2.2
Наименование разделов и тем | Содержание учебного материала, лабораторные и практические работы, самостоятельная работа обучающихся | Объём часов | Уровень освоения |
Раздел 1. Введение в теорию алгоритмов | 3 | ||
Тема 1.1. Понятие алгоритма и его основные черты | Содержание учебного материала: Интуитивное понятие алгоритма. Предмет и задачи теории алгоритмов. Основные черты и свойства алгоритма. Формализация интуитивного понятия алгоритма. Различные подходы к формализации. | 2 | 2 |
Самостоятельная работа: 1. Проработка конспектов занятий, учебной и специальной технической литературы. 2. Поиск дополнительной информации в сети Интернет. | 1 | ||
Раздел 2. Машина Тьюринга | 18 | ||
Тема 2.1. Модель вычислительного процесса как абстрактной машины и её формальное описание. Построение машины Тьюринга для заданной функции | Содержание учебного материала: Абстрактная машина Тьюринга – модель вычислительного процесса. Реализация на машине Тьюринга алгоритма вычисления функции. Понятие алгоритмически неразрешимой проблемы. Построение машины Тьюринга для заданной функции. | 4 | 2, 3 |
Практические занятия: Работа № 1 «Перемещение автомата, замена символов, анализ символов» Работа № 2 «Сравнение символов, стирание слова, удаление символа из слова» Работа № 3 «Сжатие слова, вставка символа в слово» Работа № 4 «Раздвижка слова, формирование слова на новом месте, фиксирование места на ленте» | 8 | 3 |
Продолжение таблицы 2.2
Наименование разделов и тем | Содержание учебного материала, лабораторные и практические работы, самостоятельная работа обучающихся | Объём часов | Уровень освоения |
Самостоятельная работа: 1. Проработка конспектов занятий, учебной и специальной технической литературы. 2. Поиск дополнительной информации в сети Интернет. 3. Оформление отчётов по практическим заданиям. 4. Решение примеров (приложение 1). 5. Создание реферата на тему: «Машина Тьюринга. Неразрешимые проблемы» | 6 | ||
Раздел 3. Нормальные алгоритмы Маркова | 8 | ||
Тема 3.1. Нормальные алгоритмы Маркова | Содержание учебного материала: Алгоритм как рекурсивная функция, как абстрактная машина. Нормальные алгоритмы Маркова. | 2 | 2 |
Практические занятия: Работа № 5 «Нормальные алгоритмы Маркова» | 2 | ||
Самостоятельная работа: 1. Проработка конспектов занятий, учебной и специальной технической литературы. 2. Поиск дополнительной информации в сети Интернет. 3. Оформление отчёта по практическому заданию. 4. Решение примеров (приложение 1). 5. Создание реферата на тему: «Сравнение машины Тьюринга и нормального алгоритма Маркова» | 4 | ||
Раздел 4. Машина Поста | 12 | ||
Тема 4.1. Построение машины Поста | Содержание учебного материала: Абстрактная машина Поста – модель вычислительного процесса. Построение машины Поста для заданной функции. | 2 | 2, 3 |
Продолжение таблицы 2.2
Наименование разделов и тем | Содержание учебного материала, лабораторные и практические работы, самостоятельная работа обучающихся | Объём часов | Уровень освоения |
Практические занятия: Работа № 6 «Работа с массивами» Работа № 7 «Ориентация на ленте» Работа № 8 «Действия над заданным на ленте множеством меток» | 6 | 3 | |
Самостоятельная работа: 1. Проработка конспектов занятий, учебной и специальной технической литературы. 2. Поиск дополнительной информации в сети Интернет. 3. Оформление отчётов по практическим заданиям. 4. Решение примеров (приложение 1). | 4 | ||
Раздел 5. Рекурсивные функции и алгоритмы | 14 | ||
Тема 5.1. Примитивно рекурсивные и частично-рекурсивные функции | Содержание учебного материала: Понятия конструктивных объектов, арифметических, частично определенных и повсеместно определенных функций. Понятие вычислимой функции. Примитивно рекурсивное описание функций. Операция минимизации функции. Частично рекурсивные функции. Общерекурсивные функции. Тезис Черча. | 6 | 2, 3 |
Лабораторные работы: Работа № 1 «Разработка программ с использованием рекурсивных функций» | 4 | 3 | |
Самостоятельная работа: 1. Проработка конспектов занятий, учебной и специальной технической литературы. 2. Поиск дополнительной информации в сети Интернет. 3. Оформление отчёта по лабораторной работе. 4. Создание рефератов на темы: «Рекурсивные алгоритмы», «Рекурсия в программировании» | 4 |
Продолжение таблицы 2.2
Наименование разделов и тем | Содержание учебного материала, лабораторные и практические работы, самостоятельная работа обучающихся | Объём часов | Уровень освоения |
Раздел 6. Классификация алгоритмов и оценка их сложности | 41 | ||
Тема 6.1. Трудоемкость алгоритмов: временные оценки | Содержание учебного материала: Финитные алгоритмы. Сравнительная оценка алгоритмов: длина входа, ресурсы абстрактной машины и трудоемкость. Комплексная оценка алгоритма. Классификация алгоритмов. Асимптотический анализ функции трудоемкости и сложность алгоритма. | 6 | 2, 3 |
Самостоятельная работа: 1. Проработка конспектов занятий, учебной и специальной технической литературы. 2. Поиск дополнительной информации в сети Интернет. | 2 | ||
Тема 6.2. Сложностные классы задач | Содержание учебного материала: Теория сложности вычислений. Линейные алгоритмы. Класс Р – задачи полиномиальной сложности. Класс Е – задачи экспоненциальной сложности. Класс NP – полиномиально проверяемые задачи. Класс NPC - NP-полные задачи. Соотношение классов. Пример полного анализа алгоритма решения задачи о сумме. Анализ различных алгоритмов сортировки. Анализ рекурсивных алгоритмов. | 8 | 2, 3 |
Лабораторные работы: Работа № 2 «Разработка программ с использованием алгоритмов перебора» Работа № 3 «Разработка программ с использованием алгоритмов сортировки» | 8 | 3 | |
Самостоятельная работа: 1. Проработка конспектов занятий, учебной и специальной технической литературы. 2. Поиск дополнительной информации в сети Интернет. 3. Оформление отчётов по лабораторным работам. 4. Создание рефератов на темы: «Основы оценок сложности алгоритмов», «Вычислительная сложность алгоритма» | 6 |
Продолжение таблицы 2.2
Наименование разделов и тем | Содержание учебного материала, лабораторные и практические работы, самостоятельная работа обучающихся | Объём часов | Уровень освоения |
Тема 6.3. Обзор методов разработки алгоритмов и оценка их сложности | Содержание учебного материала: Метод композиции. Метод декомпозиции. | 4 | 2, 3 |
Практические занятия: Работа № 9 «Композиция алгоритмов» | 2 | 3 | |
Самостоятельная работа: 1. Проработка конспектов занятий, учебной и специальной технической литературы. 2. Оформление отчёта по практической работе. 3. Создание рефератов на темы: «”Жадные” алгоритмы», «Динамическое программирование» | 5 | ||
Всего: | 96 |
Для характеристики уровня освоения материала используются следующие обозначения:
1 – ознакомительный уровень (узнавание ранее изученных объектов, свойств);
2 – репродуктивный уровень (выполнение деятельности по образцу, инструкции или под руководством);
3 – продуктивный уровень (планирование и самостоятельное выполнение деятельности, решение проблемных задач)
3 УСЛОВИЯ РЕАЛИЗАЦИИ ПРОГРАММЫ ДИСЦИПЛИНЫ
3.1 Требования к минимальному материально-техническому обеспечению
Оборудование учебного кабинета:
комплект учебно-методической документации (учебники, учебные пособия, методическое обеспечение практических работ, карточки заданий и тестов); наглядные пособия (плакаты, таблицы).3.2 Информационное обеспечение обучения
Литература
Основная:
Агарева, логика и теория алгоритмов: учеб. пособие / , . — М.: МАТИ, 2011. Математическая логика и теория алгоритмов. Издание: 4-е изд., стер. – М.: ИЦ Академия, 2011. , Теория алгоритмов: М, ИЦ Академия, 2013. , Основы теории алгоритмов. – СПб: СПб НИУ ИТМО, 2012.Дополнительная:
Теория алгоритмов, формальных языков, грамматик и автоматов: Учебное пособие. Улан-Удэ: Изд-во ВСГТУ, 2000. , екции по математической логике и теории алгоритмов: Вычислимые функции. – М., 2002. Задачи и упражнения по математической логике и теории алгоритмов. 3-е изд., стер. — М.: ИЦ Академия, 2007. Теория алгоритмов. Учебное пособие. – Екатеринбург, 2006. Кормен Т, Алгоритмы: построение и анализ, М., МЦНМО, 2001. , Теория алгоритмов: основные открытия и приложения. – М.: Наука, 1987.Информационные ресурсы
http://ric. uni-altai. ru/Fundamental/teor-alg , , Теория а лгоритмов (электронный учебник)3.3 Общие требования к организации образовательного процесса
Занятия проводятся в аудитории и в компьютерных классах с использованием компьютеров.
4 КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ ДИСЦИПЛИНЫ
4.1 Формы и методы контроля и оценка результатов освоения дисциплины
Контроль и оценка результатов освоения дисциплины осуществляется преподавателем в процессе проведения практических занятий, тестирования, а также выполнения студентами индивидуальных заданий. Результаты обучения, освоенные компетенции, основные показатели оценки результата и их критерии, формы и методы контроля и оценки результатов обучения приведены в таблице 4.1.
Критерии оценок уровня подготовки студента
Оценка «5» «отлично» выставляется, если студент:
- системно, глубоко и прочно усвоил программный материал курса; полно, логически стройно, четко и правильно изложил материал; тесно связал теорию с практикой; привёл примеры; свободно справился с задачей; правильно обосновал свои решения; использовал знания из смежных дисциплин; не затруднился с ответами на вопросы при их видоизменении; допустил негрубые недочеты в ответах (1 – 2).
Оценка «4» «хорошо» выставляется, если студент:
- в основном правильно, по существу изложил материал, но нарушил логику и последовательность повествования;
- допустил 1 - 2 негрубые ошибки при ответе или решении задачи; ответил не в полном объёме на вопросы, но показал связь с практической деятельностью; справился с практическим заданием при использовании наводящих вопросов; использовал знания смежных дисциплин.
Оценка «3» «удовлетворительно» выставляется, если студент:
- имеет знания по основным вопросам курса не менее 50%, но не усвоил деталей; допустил значительные неточности в ответе или дал недостаточно правильные формулировки; допустил 3 - 4 ошибки в изложении материала; нарушил логическую последовательность в изложении материала курса; испытал затруднения при выполнении практического задания, в осуществлении связи с практической деятельностью.
Оценка «2» «неудовлетворительно» выставляется, если студент:
- не знает значительной части программного материала (более 50 %); допустил грубые ошибки при ответе; не смог логически правильно изложить материал; испытал затруднения в приведении примеров; не справился самостоятельно с решением практического задания.
В целях повышения объективности оценки знаний, умений и навыков студентов, преподаватель может задать до трёх дополнительных вопросов по содержанию материала курса.
Таблица 4.1
Результаты обучения (освоенные умения, усвоенные знания) | Освоенные компетенции | Основные показатели оценки результата и их критерии | Формы и методы контроля и оценка результатов обучения |
Умения | ОК 1 – 9 ПК 1.1, ПК 1.2 | Критерием оценки результатов освоения дисциплины является: - способность выполнения конкретных профессиональных задач в ходе самостоятельного выполнения работ, решения проблемных задач; - выполнение работ по образцу, инструкции или под руководством; - узнавание ранее изученных объектов, свойств. | 1. индивидуальный опрос; 2. самостоятельные работы; 3. контрольные работы; 4. практические работы, 5. решение задач по темам; 6. тестирование; 7. комбинированный метод; 8. внеаудиторная самостоятельная работа; 9. дифференцированный зачет |
У1. Разрабатывать алгоритмы для конкретных задач | |||
У2. Определять сложность работы алгоритмов | |||
Знания | 1. индивидуальный и фронтальный опрос в ходе аудиторных занятий; 2. контроль выполнения групповых и индивидуальных заданий; 3. дифференцированный зачет | ||
З1. Основные модели алгоритмов | |||
З2. Методы построения алгоритмов | |||
З3. Методы вычисления сложности алгоритмов |
ПРИЛОЖЕНИЕ 1
САМОСТОЯТЕЛЬНАЯ РАБОТА по теме «Формализация понятия «алгоритм» в теории автоматов»
Построить МТ с внешним алфавитом А = {a0, 1}, обладающую следующим свойством: машина не применима ни к одному непустому слову, т. е. применение машины к любому непустому слову приводит к тому, что машина никогда не останавливается. Написать программу МТ, которая аннулирует все слова в алфавите {a, b}, содержащие вхождение заданного непустого слова u. Буквы слова и должны быть заданы в исходном слове, перерабатываемом программой ( х u п * ). Написать схему НА, перерабатывающего любое слово w в алфавите А = {a, b, c} в слово вида ww. Построить МТ, которая вычисляет модуль разности двух любых натуральных чисел
А = {a0, 1}. Построить МТ, которая вычисляет модуль разности двух любых натуральных чисел
А = {0, 1, 2, 3, 4, 5,6, 7, 8, 9}. Построить НА, который проверяет делимость на 3 заданного в десятичной системе натурального числа. Написать программу МТ, которая сдвигает входное слово на заданное число k ячеек вправо (или влево), а в освободившиеся k первых после маркера начала ленты ячеек записывает специальный символ $. Засчитывается только одно решение. Постройте МТ с внешним алфавитом А = {a0, 1}, обладающую следующим свойством: машина применима только к словам вида 11...1, n≥ 1, где слово состоит из 3n символов. Написать программу МТ, выполняющей умножение двух любых целых неотрицательных чисел, представленных словами в алфавите A = {0, 1} (натуральное число n записывается как слово (01...1), состоящее из n символов). Написать схему НА, который в любом исходном слове в заданном алфавите А ={a, b, c} выполняет замену всех букв b из А словами u соответственно. Построить НА, который аннулирует все слова вида x$x, где х ∈{a, b}, а $ ∉{a, b} . Построить НА, который проверяет делимость на 5 заданного в десятичной системе натурального числа. Написать программу МТ, которая выполняет умножение на цифру в десятичной системе счисления. Постройте МТ, перерабатывающую слово 01x01y0 в слово 01y01x 0, причем в начальном и конечном положении обозревается ячейка, содержащая 0 между наборами единиц. Постройте МТ с внешним алфавитом А = {a0, 1}, обладающую следующим свойством: машина применима только к словам вида 11...1а01...1, где первое слово содержит п символов, а второе т символов. Написать программу МТ, которая аннулирует любое слово вида x$x, где х ∈{a, b}, а $∉ {a, b} . Построить НА, который аннулирует все слова вида ххR, где x ∈{a, b}. Построить НА, который проверяет делимость на 9 заданного в десятичной системе натурального числа. Постройте МТ, перерабатывающую слово 01x0 в слово 01x 01x0, причем в начальном и конечном положении обозревается крайняя левая ячейка. Написать программу МТ, которая аннулирует любое слово вида x$xR, где х∈{a, b}, а $∉∉{a, b} . Построить НА, аннулирующий все палиндромы в алфавите А = {a, b}. Построить НА, который проверяет делимость на 10 заданного в десятичной системе натурального числа. Постройте МТ, перерабатывающую слово 01x01y01z0 в слово 01z01y01x0, причем в начальном положении обозревается ячейка, содержащая 0 между наборами из y и z единиц, а в конечном положении обозревается ячейка с 0 между наборами из z и х единиц. Построить НА для выполнения сложения натуральных чисел в десятичной системе счисления. Построить НА для выполнения сложения натуральных чисел в единичной системе счисления. Построить НА, который проверяет делимость на 11 заданного в десятичной системе натурального числа. Постройте МТ, перерабатывающую слово 01x01y0 в слово 01x01y01x01y0, причем в начальном положении обозревается самая левая ячейка, а в конечном – ячейка, в которой записан 0, заключенный между массивами 1x01y и 1y01x. Построить МТ, которая удваивает любое входное слово в алфавите А = {a, b}. Построить НА для выполнения умножения натуральных чисел в десятичной системе счисления. Построить НА для выполнения умножения на цифру в десятичной системе счисления. Построить НА для выполнения умножения натуральных чисел в единичной системе счисления. Построить НА, который проверяет делимость на 4 заданного в десятичной системе натурального числа. Построить НА, который выполняет вычитание натуральных чисел, заданных в десятичной системе счисления. Построить НА, вычисляющий остаток от деления на указанную цифру. В алфавите А={1}; в алфавите А={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Построить МТ, вычисляющую остаток от деления на указанную цифру. В алфавите А={1} Построить НА, отыскивающий середину данного слова в алфавите А = {a, b}. Построить МТ, отыскивающую середину данного слова в алфавите А = {a, b}.
