Conference publications

Abstracts

XIII conference

Обучение студентов построению оценок комбинаторных алгоритмов

Melnikov O.I.

Belarus, 220007, Minsk, Bakinskaya str., 18/2, apt. 1

На Международном симпозиуме «Алгоритмы в современной математике и ее приложениях» в 1979 г. введение времени как оценки сложности алгоритмов было от-несено к основным открытиям общей теории алгоритмов.

При решении прикладных задач алгоритм является основным, конструктивным средством получения нужного результата. Реализация алгоритма на ЭВМ, несмотря на возрастающие с каждым годом возможности техники, требует экономного использова-ния машинных ресурсов. Все это приводит к необходимости обучения оценке алгорит-мов студентов разных специальностей.

Необходимость оценки алгоритмов не вызывает сомнений у студентов. Они все-гда называют две причины этого: 1) выбор лучшего алгоритма из существующих для решения конкретной задачи; 2) сравнение нового алгоритма с существующими. Но есть одна причина, о которой студенты часто не подозревают. Как правило, заказчик при решении производственной задачи указывает время, за которое задача должна быть решена с помощью ЭВМ конкретной модели. Оценивание быстродействия алгоритма позволяет прогнозировать время выполнения исследования.

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

Принцип приоритетности оценки скорости реализации алгоритма утверждает главенство оценки данного параметра над другими.

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

Принцип массовости оценки предполагает вычисления оценки для всех задач из данного класса независимо от их размеров и структуры.

Принцип функциональности оценки рассматривает получение оценки в виде функции от величины входной информации задачи, решаемой с помощью алгоритма.

Принцип иерархичности вычисления оценки предусматривает построение оценки алгоритма на основании оценок трудоемкости составляющих его частей.

Принцип упорядочения информации при вычислении оценки утверждает необхо-димость использования при построении алгоритмов и их оценок специальных структур данных.

Принцип универсальности оценки говорит о справедливости оценки вне зависи-мости от программиста, реализующего алгоритм.