Geum.ru

Аннотация программы учебной дисциплины «Интеллектуальные системы»

Вид материалаДокументы

Содержание


Аннотация программы учебной дисциплины
Задачами дисциплины
Профессиональные компетенции
Тематический план курса
Подобный материал:
1   2   3   4   5   6   7   8   9   ...   12
^

Аннотация программы учебной дисциплины


«Анализ алгоритмов»

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

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

Дисциплина входит в вариативную часть общенаучного цикла М1 (дисциплины по выбору студента) образовательной магистерской программы «Компьютерное моделирование» направления подготовки магистров 230100 «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»


Изучение данной дисциплины требует следующих компетенций студентов:
  • использует основные законы естественно-научных дисциплин в профессиональной деятельности, применяет методы математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10);


Дисциплины, последующие по учебному плану:
  • Итоговая государственная аттестация


Изучение дисциплины направлено на формирование следующих компетенций:

Общекультурные компетенции (ОК)
  • Способность совершенствовать и развивать свой интеллектуальный и общекультурный уровень (ОК-1);
  • Способность к самостоятельному обучению новым методам исследования, к изменению научного и научно-производственного профиля своей профессиональной деятельности (ОК-2);


^ Профессиональные компетенции:
  • применять перспективные методы исследования и решения профессиональных задач на основе знания мировых тенденций развития вычислительной техники и информационных технологий (ПК-1);
  • способен разрабатывать концептуальные и теоретические модели решаемых научных проблем и прикладных задач (ПК-2);
  • Способность формировать технические задания и участвовать в разработке аппаратных и/или программных средств вычислительной техники (ПК-4);


В результате освоения дисциплины студент должен:

знать

-основные алгоритмы работы со стандартными структурами данных,
-основные методы дизайна алгоритмов,
-основы теории оценки сложности алгоритмов;

-общую концепцию эффективности, документированности и корректности алгоритма

уметь

-оценивать эффективность проектируемых алгоритмов,
-обосновывать корректность проектируемых алгоритмов,

владеть
-основами теории доказательства корректности алгоритмов,
- основными методами дизайна алгоритмов к конкретным задачам,
-навыком документирования разработанных алгоритмов.
^

Тематический план курса


а)Теоретические занятия

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

Методы доказательства корректности и завершаемости алгоритмов.

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

Машина с произвольным доступом к памяти – базовая модель для описания и анализа алгоритмов.

Понятие асимптотической (временной) сложности алгоритмов. Примеры оценки асимптотической сложности.


Тема 2. Методы проектирования алгоритмов.

Вспомогательные алгоритмы: алгоритмы поиска, сортировки (сравнениями, выбором, вставкой, слиянием), умножение матриц (алгоритм Штрассена) .

Метод отката: общее понятие, итеративная форма (ее обоснование), рекурсивная форма, примеры применения.

Метод ветвей и границ: общее понятие, общая форма (ее обоснование), примеры применения.

Динамическое программирование: общее понятие, общая форма (ее обоснование) и примеры применения.

Другие методы проектирования алгоритмов (сведения к задаче меньшей размерности, разделяй и властвуй, жадные алгоритмы).


Тема 3. Недетерминированные и альтернирующие вычисления.

Понятие недетерминированного/альтернирующего алгоритма, временной сложности недетерминированных/альтернирующих вычислений.

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

Понятия класса сложности по времени, определение классов P и NP, проблема P=NP.

NP-полнота проблемы булевской выполнимости.

11. Примеры NP-полных проблем: изоморфное вложение графов, проблема клики, существования Гамильтонова цикла (с доказательством).


б)Практические занятия

Тема 2. Методы проектирования алгоритмов.

Упражнения на алгоритмы сортировки и поиска (сравнениями, выбором, вставкой, слиянием).

Упражнения на матричные алгоритмы: алгоритм Штрассена умножения матриц, обращение матриц, решение систем линейных уравнений.

Решение алгоритмических задач на применение метод отката: обходы конем, поиск в лабиринте, гамильтов цикл.

Решение алгоритмических задач на применение метода ветвей и границ: наибольшее паросочетание, остовное дерево, гамильтов цикл.

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

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


Тема 3. Недетерминированные и альтернирующие вычисления.

Упражнения на составление недетерминированных алгоритмов.

Упражнения на доказательство NP-полноты.

Упражнения на доказательство NP-полноты. (Продолжение.)

Упражнения на составление альтернирующих алгоритмов.