СИЛЛАБУС
______________________________________________________________
(шифр и наименование модуля)
по дисциплине ___Теория алгоритмов
(код и полное наименование дисциплины по рабочему учебному плану)
для студентов специальности (ей) _ 050704 —
«Вычислительная техника и программное обеспечение»
(шифр и наименование специальности/специализации)
Астана
Силлабус
по дисциплине «Теория алгоритмов»
для студентов специальности 050704– «Вычислительная техника и программное обеспечение»
Евразийский национальный университет им. Л.Н.Гумилева
1)Бекенов Махсут Искандерович, доцент кафедры Вычислительной техники ЕНУ им. Л.Н.Гумилева.
Контактный телефон: 37-74-23 вн. (3021);
E-mail: bekenov@enu.kz
Научные интересы:Компьютерная логика, Теория алгоритмов, Теория моделей.
Дополнительная информация:
2) «Теория алгоритмов»
Код: ТА, Количество кредитов – 3.
3) Время и место проведения: 2 семестр; согласно расписанию.
4) Пререквизиты учебной дисциплины: Дискретная математика, Алгебра и геометрия
Постреквизиты:Компьютерная логика, Системы искусственного интеллекта, Высокоскоростные вычисления и суперкомпьютеры.
5) Характеристика дисциплины
5.1 Назначение учебной дисциплины.Учебная дисциплина как базовый курс должен обеспечить целенаправленную подготовку будущего специалиста, его умение формулировать и исследовать на должном уровне общие теоретические проблемы изучаемой специальности, умение развить и реализовать свои знания в области инженерной практики.
5.2 Цель: Основная цель учебной дисциплины: формирование знаний у будущих специалистов по теории алгоритмов. А также ознакомить студентов с современными проблемами и перспективами развития формальных алгоритмических систем, исследования алгоритмической неразрешимости ряда задач, получения явных функций трудоемкости в целях сравнительного анализа сложности алгоритмов, разработки критериев сравнительной оценки качества алгоритмов.
5.3 Задачи курса. Основными задачами данной дисциплины являются:
— научить теоретическим и практическим основам теории алгоритмов как области знаний и человеческой деятельности;
— освоить технические и прикладные методы и средства теории алгоритмов;
— изучить основные направления исследований в теории алгоритмов.
5.4 Содержание учебной дисциплины
Курс посвящёнформализации понятия «алгоритм». Обсуждаются три способа формального описания алгоритма –с помощью нормальных алгоритмов Маркова и через машины Тьюринга и рекурсивных функций. Приводятся меры сложности алгоритмов, определяются легко и трудноразрешимые задачи, классы задач P и NP, алгоритмически неразрешимые проблемы.
5.5 План изучения дисциплины
| № недели | Название темы | Формы обучения, кол-во часов | Задания для СРС |
| 1 | 2 | 3 | |
| 1. | Введение в теорию алгоритмов. Исторический обзор. Цели и задачи. Практическое применение результатов теории алгоритмов. | Лекция (2 часа), СРС (2 часа) | Практическое применение результатов теории алгоритмов. |
| 2. | Формализация понятия алгоритма. Понятие алгоритма и его основные черты.Интуитивное понятие алгоритма.Происхождение слова алгоритм.Понятия, связанные с понятием алгоритма.Варианты протекания алгоритмического процесса.Основные черты алгоритма.Абстракция потенциальной осуществимости. | Лекция (2 часа), СРС (2 часа) | Понятия, связанные с понятием алгоритма. |
| 3. | Необходимость уточнения понятия алгоритмДесятая проблема ГильбертаНаправления формализации понятия алгоритм | Лекция (2 часа), СРС (2 часа) | Десятая проблема Гильберта. |
| 4. | Машина ТьюрингаОсновная гипотеза теории алгоритмов .Тезис Тьюринга.Универсальная машина Тьюринга | Лекция (2 часа), СРС (2 часа) | Примеры доказательства функций вычислимых с помощью машины Тьюринга. |
| 5. | Нормальный алгорифм МарковаТезис Маркова. Равносильность тезисов. | Лекция (2 часа), СРС (2 часа) | Примеры доказательства функций вычислимых с помощью алгоритма Маркова. |
| 6. | Рекурсивные функции.Простейшие функции Операция суперпозицииИнтуитивное понятие вычислимой функции. Тезис Черча. | Лекция (2 часа), СРС (2 часа) | Примеры доказательства примитивной рекурсивности функции |
| 7. | Меpы сложности алгоpитмов. Оценка алгоритма. | Лекция (2 часа), СРС (2 часа) | Оценка сложности алгоритма. |
| 8. | Алгоритмически неразрешимые проблемы. | Лекция (1 часа), СРС (2 часа) | Алгоритмически неразрешимые проблемы. |
| Всего | Лекций 15 часов, СРС 30 часов |
Лабораторные занятия, их наименование и объем в часах (30 часов)
Статьи к прочтению:
А.И. Соколов про квантовую механику, часть вторая
Похожие статьи:
-
Проведению лабораторного занятия
Севастопольский национальный униВЕРситЕт Ядерной энергии И промышленности Инструктивно-методические указания по проведению лабораторной работы №2 на…
-
Лабораторных и студийных занятий
№ недели Название семинарских,практических, лабораторных и студийных занятий Объем в часах Представлениеданных в памяти ЭВМ.Кодирование вещественныхчисел…