Лабораторные занятия, их наименование и объем в часах (30 часов)
СИЛЛАБУС
______________________________________________________________
(шифр и наименование модуля)
по дисциплине ___Теория алгоритмов
(код и полное наименование дисциплины по рабочему учебному плану)
для студентов специальности (ей) _ 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 часов)