Экзамен

Для сдачи экзамена на оценку 3 или 4 необходимо пройти онлайн курс.

Для сдачи экзамена на оценку 5 необходимо пройти онлайн курс и решить практическую задачу.

Таблица курса

Форк LAGraph для реализаций практических задач

Онлайн курс.

Если уже имеется сертификат, то его можно просто предоставить.

Курс на Stepik. Отчитываться в таблице курса.

Курс на Stepik

• На 3 - не менее чем 105 баллов
• На 4 - не менее чем на 120 баллов
• На 5 - не менее чем на 105 баллов + практическая задача

ВНИМАНИЕ! В курсе много "peer review" задач.

Задачи

"Фиксация" задач: 02.03.2020. Брать задачу в таблице курса.

• на 5 - достаточно сложная задача и два доклада: один с введением, обзором, постановкой задачи (30-45 минут) и один с результатми (15-20 минут)

Задачей является реализация графового алгоритма через операции линейной алгебры над векторами/матрицами, используя стандарт GraphBLAS. Также необходимо сделать замеры полученной реализации и сравнение с аналогами. Датасет для замеров и реализации аналогов необходимо заранее согласовать с преподавателем. По завершению работы необходимо сделать pull request со своей реализацией в LAGraph.

Есть несколько возможностей.

1. Выбрать один из алгоритмов из списка ниже.
2. Предложить задачу на графах достаточной сложности не из списка, которую вы будете реализовывать через операции линейной алгебры. Предложения принимаются до конца февраля.
3. Если свободных задач из списка нету, то можно до конца февраля написать преподавателю на почту с просьбой выдать другую задачу.

Список алгоритмов

1. Алгоритм кластеризации вершин peer pressure. На вход подается граф G с ребрами вида (u,v,w), что означает наличие ребра из вершины u в вершину v с весом w. Также на вход подается текущее распределение вершин по кластерам в виде вектора C_i. Алгоритм возвращает финальное распределение вершин по кластерам C_f. Книга.

2. Edge betweenness centrality algorithm (Brandes' algorithm). На вход дан невзвешенный граф. Алгоритм считает метрику для каждого ребра e, показывающую количество кратчайших путей между всеми парами вершин, на которых лежит это ребро e. Книга.

3. Алгоритм раскраски графа. Дан невзвешенный граф. Требуется раскрасить его вершины в набор цветов (как можно меньшего размера), чтобы никакие две смежные вершины не были окрашены в один и тот же цвет. Статья с алгоритмом раскраски графа в терминах линейной алгебры.

4. Maximal cardinality matching. Дан невзвешенный неориентированный двудольный граф G. Необходимо найти паросочетание (набор ребер, не имеющих ни одной общей вершины), которое при добавление любого нового ребра перестает быть паросочетанием. Статья.

5. Maximum cardinality matching. Дан невзвешенный неориентированный двудольный граф G. Необходимо найти паросочетание (набор ребер, не имеющих ни одной общей вершины), с наибольшим количеством ребер. Статья.

6. Subgraph counting. Дан граф G и шаблон T его подграфов. Необходимо посчитать сколько граф G имеет подграфов, удовлетворяющих шаблону T. Статья с алгоритмом подсчета подграфов.

7. Triangle counting and enumeration. Дан невзвешенный неориентированный граф. Необходимо подсчитать количество треугольников (counting) и вывести их (enumeration). Статья.

8. Binary tree traversal (DFS). Обход в глубину бинарного дерева. Секция 4.

9. Topological sort (DFS). Топологическая сортировка ориентированного графа без циклов (DAG). Секция 5.

10. Biconnected components (DFS). Алгоритм поиска cut vertices (вершин, являющихся общими для нескольких biconnected компонент). Секция 6.

Общие моменты

Задачи фиксируются в начале семестра. Менять задачи нельзя, брать задачи после установленного срока нельзя. Оценка за задачи может быть снижена если

• Доклады выполнены "небрежно"
• Код реализации выполнен небрежно
  • Плохое качество кода
  • Нет или мало тестов
  • Нет апробации или она не достаточно показательна
  • Нет сравнения или оно не достаточно показательно
  • ...