Главная » Информационные системы » Алгоритмизация

Алгоритмизация

Уточним понимание определения «алгоритм в информатике». Это не так легко. С этой целью сформулированы общие свойства алгоритма. Информатика позволяет на их основе отличать алгоритмы от иных инструкций.

Алгоpитм – это точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Название алгоритм произошло от латинской формы имени среднеазиатского математика аль-Хорезми - Algorithmi.

Исполнитель алгоритма - это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Исполнителя характеризуют: среда, элементарные действия, система команд, отказы. Среда (или обстановка) - это место обитания исполнителяКаждый исполнитель может выполнять команды только из некоторого строго заданного списка -системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды. После вызова команды исполнитель совершает соответствующее элементарное действие. Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.

В информатике универсальным исполнителем алгоритмов является компьютер.

Основные понятия теории алгоритмов (Алгоритм, свойства алгоритма. Формы представления алгоритмов. Основныеалгоритмические конструкции)
Методика пространственно-временного компромисса (Определение. Алгоритмы и задачи: алгоритмы Бойера-Мура и Хорспула поиска подстроки)
Методика динамического программирования (Определение.Алгоритмы и задачи: вычисление биномиальных коэффициентов, алгоритм Флойда)
Методика «жадные алгоритмы» (Определение. Алгоритмы и задачи : задача о размене денег)
Методика поиска с возвратом» (Определение. Алгоритмы и задачи: задача о n-ферзях)
Методика ветвей и границ (Определение. Алгоритмы и задачи: задача о рюкзаке)
Приближенные методы решения (Основные понятия: ошибки усечения, ошибки округления, значащие цифры в представлении числа, абсолютная и относительная точность, стабильные и нестабильные алгоритмы, плохо обусловленные алгоритмы.)
Генерация комбинаторных объектов (Генерация перестановок, подмножеств)
Генетические алгоритмы (Основные понятия: генотип,фенотип, особь и качество особи, популяция и размер популяции,поколение, родители и потомки. Операторы скрещивания, мутации, отбора,редукции, останова)
Эффективность применения генетических алгоритмов (Области применения. Основные характеристики ГА: скорость и устойчивость. Способы повышения скорости генетического алгоритма:распараллеливание, кластеризация.
Динамические структуры данных (Линейные динамические структуры (списки). Основные операции: включение узла в начало или в конец, исключение узла из начала или конца, перестановка указателя)
Формализация понятия алгоритма (Массовая и индивидуальная задачи. Алгоритм. Направления основных формализмов теории алгоритмов.Способы описания алгоритма: машины Поста)
Графы (Представление графов в виде: матрицы смежности, списочными структурами с двумя адресными полями, массива списков смежных вершин, матрицы смежности для взвешенных графов. Операции над графами. Алгоритмы обхода графа в глубину
Деревья общего вида (Основные понятия:определение, степень узла, степень дерева, лист, уровень узла, предок, потомок, высота дерева, полное дерево. Основные свойства деревьев.
Основные этапы решения алгоритмической задачи (Понимание задачи. Выбор вычислительных средств, структуры данных, методик проектирования алгоритма. разработка алгоритма. Оценка корректности алгоритма. Анализ алгоритма. Реализация алгоритма)
Основы анализа эффективности алгоритмов (Определение входной длины индивидуальной задачи. Показатели эффективности алгоритма: временная, пространственная. Зависимость показателей эффективности алгоритма от входной длины задачи.
Классы эффективности алгоритмов (Порядок роста функции трудоемкости. Асимптотические классы эффективности. Классификация алгоритмов по типу зависимости функции трудоемкости от характеристик входных данных. Сложностные классы задач
Методика «грубой силы» разработки алгоритмов(Определение. Алгоритмы и задачи: сортировка выбором, пузырьковая сортировка, последовательный поиск, поиск подстроки, задача о паре двух ближайших точек)
Методика декомпозиции (Определение. Алгоритмы и задачи:сортировка слиянием, бинарный поиск, быстрая сортировка, задача о паре двух ближайших точек, задача о выпуклой оболочке)
Методика уменьшения размерности (Определение. Алгоритмы и задачи: сортировка вставкой, задача поиска фальшивой монеты, задача Иосифа)
Методика преобразования (Определение. Алгоритмы и задачи:схема Горнера вычисления значения полинома в точке, бинарное возведение в степень, пирамидальная сортировка, приведение задач, задача линейного программирования)

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.

Поделиться

Дисциплины