1. Изучение быстрых алгоритмов и подходов к ускорению программ.
Рассматриваются эвристические алгоритмы на примерах задач разбиения графа, нумерации вершин графа и др. Обсуждаются варианты жадных алгоритмов решающих эти задачи
Полезные материалы
Сайт с описанием различных алгоритмов
Примерные задания
Вариант 1
Написать программу, выполняющую нумерацию вершин ориентированного графа. Нумерация должна выполняться, опираясь на следующие действия:
Очередной вершиной берется та, из которой выходит множество дуг с максимальным суммарным весом.
Особенности программы: Язык – C++; граф представлен матрицей смежностей и хранится в файле input.txt (новая строка матрицы – новая строка файла); в файл result.txt записывается число, являющееся количеством дуг, идущих от вершин с большим номером к вершинам с меньшим (в первой строке) и перестановка вершин (новая строка перестановки – новая строка файла).
Вариант 13
Написать программу, выполняющую разбиение неориентированного графа на две равные по количеству вершин части. Разбиение должно выполняться, опираясь на следующие действия:
Первой вершиной части 1 разбиения берется случайная вершина графа. Очередной вершиной, попадающей в часть 1 является та, от которой к уже набранным ведет наибольшее количество ребер. Это повторяется до тех пор, пока в части 1 не окажется половина всех вершин графа. Остальные попадают в часть 2.
Особенности программы: Язык – C++; граф представлен матрицей смежностей и хранится в файле input.txt (новая строка матрицы – новая строка файла); в файл result.txt записывается число, являющееся количеством дуг, идущих из одной части графа в другую (в первой строке) и наборы вершин, относящиеся к первой и второй части разбиения (вторая строка – вершины графа, относящиеся к части 1 разбиения, третья строка – вершины графа, относящиеся части 2 разбиения).