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

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

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

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

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

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

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