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