8(495)912-63-37 
gmc@edu.mos.ru
FacebookВКонтактеYouTubeInstagram

Вторник, 18 Май 2021 19:18

Рабочая программа учебного курса по выбору «Теория графов. Первые шаги к машинному обучению»

Освоение программы курса «Теория графов. Первые шаги к машинному обучению» обеспечивает изучение элементов содержания предметов «Математика», «Информатика» в формате учебно-практических занятий и позволяет получить общее представление о применимости графов в приёмах машинного обучения.

Содержание курса «Теория графов. Первые шаги к машинному обучению» основано на следующих межпредметных понятиях:

  • алгоритм;
  • анализ;
  • база данных;
  • данные;
  • модель;
  • система;
  • граф.

Теория графов – одно из наиболее перспективных направлений в машинном обучении, а графы – один из самых мощных и гибких способов представления данных. Графы могут использоваться как обозначение большого числа систем в различных областях, включая общественные науки (социальные сети), естествознание (физические системы и сети межбелкового взаимодействия), графы знаний и многие другие области исследований.

Отображение данных в виде графов обеспечивает большую гибкость и может дать совершенно другой взгляд на различные проблемы. С помощью графа можно представить сколь угодно сложные данные. Такая структура подходит для организации различных данных – от разработки лекарств до рекомендаций о дружбе в социальных сетях. Графы стали основой многочисленных систем, позволяющих эффективно хранить и получать доступ к реляционным знаниям о взаимодействующих объектах.

Реализация программы «Теория графов. Первые шаги к машинному обучению» рассчитана на 34 часа учебно-практических занятий. Последовательность модулей программы выстроена в логике процесса решения кейсовых задач обучающимися и выполнения комплексного проекта. Область применения разработанного проекта в процессе освоения данной программы может быть различной (бизнес, медицина, образование, строительство и т. д.)

Программа рассчитана на уровень среднего общего образования (СОО).

Программа предусматривает индивидуальные, групповые и иные формы работы.

Режим занятий: 1 занятие по 45 мин. 1 раз в неделю.

Срок реализации программы – 1 год (34 часа).

I. Планируемые результаты

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

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

II. Содержание курса

Основные разделы программы учебного курса.

Модуль 1. Понятие графа, основные методы просмотра вершин графа.

Основные понятия и терминология. Способы представления графа. Поиск в глубину. Поиск в ширину.

Модуль 2. Деревья.

Определение дерева. Перечисление остовных деревьев связного помеченного графа. Алгоритм представления дерева в виде последовательности чисел.

Модуль 3. Связность.

Вершинная и реберная связность. Метод нахождения блоков графа. Теорема Менгера. Связность в орграфе.

Модуль 4. Циклы.

Эйлеровы графы. Гамильтоновы графы. Фундаментальное множество циклов.

Модуль 5. Покрытия и независимость.

Основные понятия. Метод генерации всех независимых множеств вершин графа. Клики. Доминирующие множества. Паросочетания. Диаграмма взаимосвязей между задачами.

Модуль 6. Планарные графы.

Основные понятия. Формула Эйлера. Алгоритм укладки графа на плоскости.

Модуль 7. Раскраска вершин графа.

Хроматическое число. Метод правильной раскраски. Методы поиска минимальной раскраски.

Модуль 8. Кратчайшие пути в графе.

Постановка задачи. Вывод пути. Алгоритмы поиска кратчайших путей.

Модуль 9. Потоки в сетях.

Основные понятия и постановка задачи. Введение в метод блокирующих потоков. Основные алгоритмы.

III. Тематическое планирование 

№ п/п

Название разделов

Всего

1.

Понятие графа, основные методы просмотра вершин графа

3

2.

Деревья

3

3.

Связность

4

4.

Циклы

4

5.

Покрытия и независимость

6

6.

Планарные графы

3

7.

Раскраска вершин графа

3

8.

Кратчайшие пути в графе

3

9.

Потоки в сетях

5

 

Всего:

34