Магистерская диссертация на тему: Работа алгоритма поиска в ширину. Неформальное описание. Формальное описание

Введение

Алгоритм - набор инструкций <https://ru.wikipedia.org/wiki/%D0%9Е%D0%ВF%D0%В5%D1%80%D0%В0%D1%82%D0%ВЕ%D1%80_%28%D0%ВF%D1%80%D0%ВЕ%D0%В3%D1%80%D0%В0%D0%ВС%D0%ВС%D0%В8%D1%80%D0%ВЕ%D0%В2%D0%В0%D0%ВD%D0%В8%D0%В5%29>, описывающих порядок действий исполнителя для достижения результата решения задачи <https://ru.wikipedia.org/wiki/%D0%А0%D0%В5%D1%88%D0%В5%D0%ВD%D0%В8%D0%B5_%D0%В7%D0%В0%D0%В4%D0%В0%D1%87> за конечное число действий. В старой трактовке вместо слова "порядок" использовалось слово "последовательность", но по мере развития параллельности в работе компьютеров слово "последовательность" стали заменять более общим словом "порядок". Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы. Таким образом, некоторые инструкции должны выполняться строго после завершения работы инструкций, от которых они зависят. Независимые инструкции или инструкции, ставшие независимыми из-за завершения работы инструкций, от которых они зависят, могут выполняться в произвольном порядке, параллельно или одновременно, если это позволяют используемые процессор и операционная система.

Ранее часто писали "алгорифм", сейчас такое написание используется редко, но, тем не менее, имеет место (например, Нормальный алгорифм <https://ru.wikipedia.org/wiki/%D0%9D%D0%ВЕ%D1%80%D0%ВС%D0%В0%D0%ВВ%D1%8С%D0%ВD%D1%8В%D0%B9_%D0%В0%D0%ВВ%D0%В3%D0%ВЕ%D1%80%D0%В8%D1%84%D0%ВС> Маркова <https://ru.wikipedia.org/wiki/%D0%9С%D0%В0%D1%80%D0%ВА%D0%ВЕ%D0%В2,_%D0%90%D0%ВD%D0%В4%D1%80%D0%В5%D0%B9_%D0%90%D0%ВD%D0%В4%D1%80%D0%В5%D0%В5%D0%В2%D0%В8%D1%87_%28%D0%ВС%D0%ВВ%D0%В0%D0%В4%D1%88%D0%В8%D0%В9%29>).

Часто в качестве исполнителя выступает некоторый механизм (компьютер, токарный станок, швейная машина), но понятие алгоритма необязательно относится к компьютерным программам <https://ru.wikipedia.org/wiki/%D0%9А%D0%ВЕ%D0%ВС%D0%ВF%D1%8С%D1%8Е%D1%82%D0%В5%D1%80%D0%ВD%D0%В0%D1%8F_%D0%ВF%D1%80%D0%ВЕ%D0%В3%D1%80%D0%В0%D0%ВС%D0%ВС%D0%В0>, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек.

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

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

Рисунок 1 - Поиск в ширину

Оглавление

- Введение

- Работа алгоритма поиска в ширину

- Неформальное описание

- Формальное описание

- Схема алгоритма поиска в ширину

- Примеры реализации Заключение

- Список литературы