Вопрос: история развития теории алгоритмов:

Теория алгоритмов, как наука, непосредственно связана с предметами математической логики и теории конечных автоматов. В Древней Греции Аристотель и его ученик Платон сформулировали основные правила логики, которые используются до нашего времени для доказательства правильности и решения логических задач.Математическая логика – это наука о правилах формального логического мышления.Теория автоматов изучает модели конечных автоматов, описывающие вычислительные узлы и элементы управления ЭВМ и других технических устройств. Возникновение понятия «алгоритм» связано с именем узбекского математика Маххамада ибн Мусса Аль-Хорезми (IX в.), который сформулировал правила умножения и деления чисел в десятичной системе счисления. В дальнейшем термин алгоритм использовался для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определённым правилам. На протяжении многих веков учёные всего мира создали много методов и алгоритмов решения различных задач в математике и физике. Само понятие алгоритма стало объектом математического изучения. В классической теории алгоритмов изучаются только вопросы существования или несуществования алгоритмов путем сведения этих вопросов к исследованию какого-либо одного узкого класса алгоритмов, что не позволяет охватить многие важные проблемы данной теории. До середины XX века использовалось понятие алгорифма, заимствованное из математики. Позже с возникновением практического аспекта теории алгоритмов стал использоваться термин алгоритм. Причиной этому послужило развитие наук, изучающих структуру и принципы работы ЭВМ. Решение задач на ЭВМ было принято описывать в виде алгоритмов. Создание компьютеров и языков программирования способствовало выделению теории алгоритмов как самостоятельной дисциплины. Сегодня понятие алгоритма вышло за пределы математики и используется в различных областях, где алгоритмом называют точно сформулированное правило, являющееся руководством для достижения необходимого результата. Кроме того, алгоритмы являются первоосновой для программирования задач на ЭВМ

Вопрос: понятие алгоритма и алгоритмического процесса:

Алгоритм – совокупность чётко определённых правил для решения задачи за конечное число шагов.

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

Вопрос: алгоритмический процесс:

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

Алгоритмический процесс состоит из конечного числа шагов, каждый из которых является простым и выполняется за конечное время. Число шагов алгоритмического процесса связано с количеством времени S(t), затрачиваемого на их выполнение, а в ряде случаев и расходом других ресурсов.

Вопрос: основные вопросы теории алгоритмов:

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

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

2) Ответ на второй вопрос требует рассмотрения принципов работы ЭВМ и организации вычислительных процессов для различных структур ЭВМ в рамках их классификации, а также оценки качества алгоритмов, реализуемых в различных ЭВМ.

3) Эффективным считается алгоритм, обладающий наибольшим быстродействием.

4) Для сравнения различных алгоритмов по быстродействию необходимо рассмотреть следующие параметры:

• временная функция T(N);

• функция сложности алгоритма O(g(N)), учитывающая зависимость скорости роста числа шагов алгоритма от объема исходных данных.

Вопрос: классификация алгоритмов

I. Т. к. алгоритм создается для решения задач одного класса, то вводят классификацию алгоритмов по типу решаемых задач:

Табличные алгоритмы имеют в своей основе таблицу (поле исходных значений) и правила поиска решений.

Численные алгоритмы задаются в виде формул и блок-схем. В их основе значительную роль играют арифметические операции (+,–, /, *).

Алгоритмы игр имеют в основе логические задачи.

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

II. По способу создания (источники) различают:

Эмпирические алгоритмы – алгоритмы, полученные в ходе эксперимента или имитационного моделирования.

Теоретически обусловленные алгоритмы – алгоритмы, возникшие из основных положения какой-либо теории.

Эвристические алгоритмы – алгоритмы, основанные на личном опыте, таланте и изобретательности разработчика.

Комбинационные алгоритмы – генерируются из уже известных алгоритмов.

III. По критерию реализуемости различают:

Простые алгоритмы – хорошо обусловленные алгоритмы.

Трудно разрешимые алгоритмы – алгоритмы решения частных задач, обладающих большой сложностью и не являющихся эффективными.

Нереализуемые алгоритмы.

IV. По критерию сложности различают:

Алгоритмы с логарифмической сложностью.

Полиномиальные алгоритмы (класс P).

Недетерминированные полиномиальные алгоритмы (класс NP), имеющие степенную или факториальную сложность.