» »

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

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

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

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

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

=1. Основные понятия теории алгоритмов (Алгоритм, свойства алгоритма. Формы представления алгоритмов. Основные алгоритмические конструкции)
=10. Методика пространственно-временного компромисса (Определение. Алгоритмы и задачи: алгоритмы Бойера-Мура и Хорспула поиска подстроки)
=11. Методика динамического программирования (Определение. Алгоритмы и задачи: вычисление биномиальных коэффициентов, алгоритм Флойда)
=12. Методика «жадные алгоритмы» (Определение. Алгоритмы и задачи : задача о размене денег)
=13. Методика поиска с возвратом» (Определение. Алгоритмы и задачи: задача о n-ферзях)
=14. Методика ветвей и границ (Определение. Алгоритмы и задачи: задача о рюкзаке)
=15. Приближенные методы решения (Основные понятия: ошибки усечения, ошибки округления, значащие цифры в представлении числа, абсолютная и относительная точность, стабильные и нестабильные алгоритмы, плохо обусловленные алгоритмы.
=16. Генерация комбинаторных объектов (Генерация перестановок, подмножеств)
=17. Генетические алгоритмы (Основные понятия: генотип, фенотип, особь и качество особи, популяция и размер популяции, поколение, родители и потомки. Операторы скрещивания, мутации, отбора, редукции, останова)
=18. Эффективность применения генетических алгоритмов (Области применения. Основные характеристики ГА: скорость и устойчивость. Способы повышения скорости генетического алгоритма: распараллеливание, кластеризация. Способы повышения ус
=19. Динамические структуры данных (Линейные динамические структуры (списки). Основные операции: включение узла в начало или в конец, исключение узла из начала или конца, перестановка указателя,
=2. Формализация понятия алгоритма (Массовая и индивидуальная задачи. Алгоритм. Направления основных формализмов теории алгоритмов. Способы описания алгоритма: машины Поста)
=20. Графы (Представление графов в виде: матрицы смежности, списочными структурами с двумя адресными полями, массива списков смежных вершин, матрицы смежности для взвешенных графов. Операции над графами. Алгоритмы обхода графа в глубину
=21. Деревья общего вида (Основные понятия: определение, степень узла, степень дерева, лист, уровень узла, предок, потомок, высота дерева, полное дерево. Основные свойства деревьев. Представление дерева списочно
=22 Алгоритмы из докладов.
=3. Основные этапы решения алгоритмической задачи (Понимание задачи. Выбор вычислительных средств, структуры данных, методик проектирования алгоритма. разработка алгоритма. Оценка корректности алгоритма. Анализ алгоритма. Реализация алгоритма)
=4. Основы анализа эффективности алгоритмов (Определение входной длины индивидуальной задачи. Показатели эффективности алгоритма: временная, пространственная. Зависимость показателей эффективности алгоритма от входной длины задачи. Ед
=5. Классы эффективности алгоритмов (Порядок роста функции трудоемкости. Асимптотические классы эффективности. Классификация алгоритмов по типу зависимости функции трудоемкости от характеристик входных данных. Сложностные классы задач
=6. Методика «грубой силы» разработки алгоритмов (Определение. Алгоритмы и задачи: сортировка выбором, пузырьковая сортировка, последовательный поиск, поиск подстроки, задача о паре двух ближайших точек, задача о выпуклой
=7. Методика декомпозиции (Определение. Алгоритмы и задачи: сортировка слиянием, бинарный поиск, быстрая сортировка, задача о паре двух ближайших точек, задача о выпуклой оболочке)
=8. Методика уменьшения размерности (Определение. Алгоритмы и задачи: сортировка вставкой, задача поиска фальшивой монеты, задача Иосифа)
=9. Методика преобразования (Определение. Алгоритмы и задачи: схема Горнера вычисления значения полинома в точке, бинарное возведение в степень, пирамидальная сортировка, приведение задач, задача линейного программирования, задача целочисленного линейн

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