Аннотация

Дисциплины по теории алгоритмов кроме изучения теоретического материала предусматривают решение практических заданий по построению математической модели для решаемой задачи, разработке эффективного (с точки зрения трудоёмкости) алгоритма с последующим высоким уровнем его реализации на некотором языке программирования. Для проверки работоспособности программ на факультете прикладной математики и информатики БГУ применяется система автоматического тестирования. Ее функциональность позволяет организовать дистанционное обучение, самостоятельную и контролируемую работу студентов. Используя в своей работе систему автоматического тестирования, преподаватель освобождается от рутинной работы, связанной с проверкой решений, получая возможность уделять больше внимания вопросам алгоритмизации. Учебно-методическое пособие состоит из двух частей: «Алгоритмы на графах» и «Бинарные поисковые деревья». Первая часть содержит практические задачи, которые могут быть сформулированы в графовой постановке. Далее для их решения применяются соответствующие алгоритмы, например алгоритм построения максимального потока, кратчайшего пути и др. Во второй части рассматриваются вопросы организации поиска некоторого элемента в совокупности элементов. Известно, что данная задача может быть решена с использованием списковых структур, хеширования, а также путём построения для последовательности элементов поисковых деревьев (АВЛ-деревьев, 2-3-деревьев и др.). Авторы предлагают построить по последовательности ключей бинарное поисковое дерево, выполнить, используя соответствующий способ обхода вершин дерева, определённые действия с его вершинами и затем вершину, которая удовлетворяет требуемым свойствам. К каждой части приведены указания к решению задач. Отметим, что многие задачи, рассмотренные в сборнике, предлагались на международных олимпиадах по программированию, что, несомненно, является свидетельством их высокого уровня. Учебно-методическое пособие будет интересно всем, кто стремится углубить свои знания в области алгоритмики.удалить