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


Раздел 3. Структура и содержание дисциплины



Скачать 278.34 Kb.
страница3/6
Дата30.07.2018
Размер278.34 Kb.
ТипПрограмма
1   2   3   4   5   6

Раздел 3. Структура и содержание дисциплины


Семестр 6


пп

Модули

Лекции, час

Семинары, час

Лабораторные работы, час

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

Литература

1

Модуль 1. Теория графов

16

16




36

[1–8]

2

Модуль 2. Основы теории алгоритмов

8

8




20

[1–8]

3

Модуль 3. Математическая логика: исчисление высказываний

10

10




30

[1–8]

ДИСЦИПЛИНАРНЫЕ МОДУЛИ

Модуль 1. Теория графов


Виды учебной работы

Объем

в часах

Сроки

проведения, недели

Лекции

16

1–8

Семинары

16

1–8

Лабораторные работы







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







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







  • домашнее задание №1 «Конечные автоматы»

20

1–9

  • рубежный контроль №1

4

9

  • проработка лекционного материала, подготовка к семинарам

12




Трудоемкость, час

40




Трудоемкость, зач.единицы

1,1




Контроль освоения модуля 1

Неделя проведения

контроля модуля

Формы контроля


Оценка в баллах

минимальная

Максимальная

5

Домашнее задание

6

8

5

Рубежный контроль

14

22




ИТОГО

20

30

После освоения модуля 1 студент должен приобрести следующие знания, умения и владения, соответствующие компетенциям ООП.

Знания

Компетенции

  • понятие ориентированного и неориентированного графа;

  • методы обхода вершин графа (в глубину и в ширину);

  • понятие гомоморфизма и изоморфизма графов;

  • методы решения задачи о путях в размеченных ориентированных графах;

  • понятие пространства циклов неориентированного графа;

  • хроматическое число и хроматический многочлен;

  • понятие регулярного языка;

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

ОК-1, ОК-2, ОК-4, ОК-11, ОК-12, ОК-16
ПК-1, ПК-2, ПК-11




Умения

Компетенции

  • реализовывать алгоритмы поиска в глубину и в ширину в ориентированных и неориентированных графах;

  • вычислять группу автоморфизмов неориентированного графа, распознавать в простейших случаях изоморфность или неизоморфность графов;

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

  • определять размерность пространства циклов неориентированного графа и находить разложение произвольного цикла по базису;

  • вычислять хроматическое число графа;

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

ОК-1, ОК-2, ОК-4, ОК-11,

ОК-12
ПК-4, ПК-5,



ПК-14




Владение навыками

Компетенции

  • решения задач локального и глобального анализа графов;

  • использования методов теории графов в решении прикладных задач (сортировка, поиск, анализ информационных связей в программах);

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

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

ОК-1, ОК-2, ОК-4, ОК-11
ПК-5, ПК-12, ПК-13

Содержание модуля 1

Лекции

Введение (2 ч.). Основные понятия теории графов: способы представления (матричные и списковые структуры), пути, цепи, циклы, подграфы, компоненты связности. Сети, деревья и леса.

Основные алгоритмы (4 ч.). Поиск в глубину и поиск в ширину. Алгоритм Дейкстры. Алгоритм Демукрона топологической сортировки сети. Алгоритм Краскала поиска остовного дерева наименьшего веса.

Гомоморфизм и изоморфизм графов (2 ч.). Понятия гомоморфизма и изоморфизма. Группа автоморфизмов неориентированного графа и методы ее вычисления.

Пространство циклов неориентированного графа (2 ч.). Пространство подграфов неориентированного графа. Эйлеровы и квазиэйлеровы графы. Основная теорема о разложении произвольного цикла по базису (системе фундаментальных циклов относительно фиксированного остова)..

Задача о путях в размеченных ориентированных графах (3 ч.) Понятие ориентированного графа (орграфа), размеченного над полукольцом. Стоимость прохождения между двумя вершинами. Постановка задачи о путях и метод ее решения (алгоритм Флойда-Уоршелла-Клини). Задача вычисления транзитивного замыкания орграфа и задача вычисления матрицы кратчайших расстояний.

Анализ и синтез конечных автоматов (3 ч.). Полукольцо языков и регулярных языков в заданном конечном алфавите. Конечный автомат (КА) как орграф, размеченный над полукольцом регулярных языков. Анализ и синтез КА.

Семинары

Основные алгоритмы (4 ч.). Выполнение алгоритмов поиска в глубину и в ширину, алгоритмов Дейкстры, Демукрона и Краскалла

Изоморфизмы и группа автоморфизмов неориентированного графа (2 ч.). Разпознавание изоморфных и неизоморфных графов в простых случаях. Вычисление группы автоморфизмов неориентированного графа

Цикломатика и хроматические числа (2 ч.). Разложение циклов неориентированного графа по базису. Вычисление хроматических чисел.

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

Анализ и синтез конечных автоматов (3 ч.).. Решение задачи анализа КА как частного случая задачи о путях в размеченных орграфах. Синтез КА по регулярному выражению. Детерминизация и минимизация КА.

Рубежный контроль (2 ч.).

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

В модуле 1 предусмотрено выполнение домашнего задания, а также самостоятельная проработка материала лекций и семинаров и подготовка к итоговой аттестации (рубежному контролю). Рубежный контроль проводится в форме письменной работы на семинарском занятии.





Поделитесь с Вашими друзьями:
1   2   3   4   5   6


База данных защищена авторским правом ©znate.ru 2019
обратиться к администрации

    Главная страница