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

  • 1. Изучение быстрых алгоритмов и подходов к ускорению программ.

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


    Примерные задания

    Вариант 1

         Написать программу, выполняющую нумерацию вершин ориентированного графа. Нумерация должна выполняться, опираясь на следующие действия:

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

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

     

    Вариант 13

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

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

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



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

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


      Примерные задания


      Вариант 1

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

           Доклад должен включать в себя: устное выступление с использованием презентации содержащей визуальное подкрепление основной информации используемой в докладе. У доклада должна быть выделена четкая структура, отображенная в презентации.

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