01. Что такое алгоритмы и структуры данных

---

ВПЕРЁД ⇒

Описание работы алгоритма через псевдокод

⇐ НАЗАД

Что такое алгоритмы и структуры данных

---

Что такое алгоритмы и структуры данных?

Алгоритмы

Понятие алгоритма

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

В роли исполнителя могут выступать разные сущности, например:

• Компьютер, исполняющий определённый набор процессорных инструкций для решения поставленной задачи.
• Человек, который, к примеру, при приготовлении пищи может выполнять чётко определённые шаги из рецепта приготовления блюда. В данном случае рецепт - это алгоритм приготовления блюда.

Нас, как программистов, в роли исполнителя будет интересовать компьютер, исполняющий реализацию некоторого целевого алгоритма.

Раньше, при описании понятия алгоритм, вместо слова “порядок” использовалось слово “последовательность”, то есть предполагалось, что алгоритм - последовательность действий исполнителя для решения поставленной задачи. Однако, по мере развития параллельных компьютерных вычислений, слово “последовательность” стали заменять словом “порядок”, так как независимые инструкции компьютер может выполнять параллельно, а не последовательно.

Можно дать и иное определение понятию алгоритма:

Алгоритм - любая корректно определённая вычислительная процедура, на вход (input) которой подаётся некоторая величина или набор величин и результатом выполнения которой является выходная (output) величина или набор величин. До появления параллельных вычислений алгоритмы трактовались как последовательности вычислительных шагов, преобразующих входные величины в выходные.

Алгоритмы и параллельные вычисления

Но откуда вообще возникла необходимость рассматривать алгоритмы не как обычные последовательности действий, а как параллельно выполняемые упорядоченные наборы действий?

Многие годы производительность процессоров устойчиво возрастала за счёт повышения их тактовых частот, а сами процессоры при этом содержали только одно вычислительное ядро. Но подобный рост производительности не мог продолжаться бесконечно, поскольку физика диктует свои правила. С ростом тактовой частоты процессора выделение тепловой мощности растёт нелинейным образом, и рано или поздно становится сложным выполнять отвод тепла от процессора, что чревато его перегревом и повреждением. По этой причине, для повышения количества вычислений, выполняемых за единицу времени, проектировщиками в последние годы применяется другой подход - разработка процессоров с большим количеством вычислительных ядер. Для того, чтобы выжать из многоядерных процессоров максимальную производительность, необходимо использовать алгоритмы, базирующиеся на механизмах параллельных вычислений. Речь идёт о модели так называемых многопоточных (multithreaded) алгоритмов. Эта модель, с теоретической точки зрения, обладает рядом преимуществ в сравнении с классической моделью последовательных алгоритмов.

Постановка вычислительных задач

Предназначение любого алгоритма - решение корректно поставленной вычислительной задачи (computational problem). В постановке задачи в общих чертах задаётся отношение между входом и выходом. В алгоритме при этом описывается конкретная вычислительная процедура, с помощью которой удаётся добиться выполнения указанного отношения.

Наиболее популярным примером постановки вычислительной задачи является постановка задачи сортировки:

• Вход. Дана последовательность из $n$ чисел (то есть дана упорядоченная n-ка) $⟨x_1,x_2,...,x_n⟩$.
• Выход. Необходимо выполнить перестановку (переупорядочивание) $⟨x_1^{\prime },x_2^{\prime },...,x_n^{\prime }⟩$ входной последовательности, такую, что $x_1^{\prime }\le x_2^{\prime }\le ...\le x_n^{\prime }$.

Например, если на вход подаётся последовательность $⟨9,1,8,2,7,3,6,4,5⟩$, то выводом алгоритма сортировки должно быть $⟨1,2,3,4,5,6,7,8,9⟩$. Подобная входная последовательность называется экземпляром (instance) задачи сортировки. Если говорить более точно, то экземпляр задачи состоит из входных данных, необходимых для решения задачи и удовлетворяющих всем ограничениям, наложенным при постановке задачи.

Говорят, что алгоритм корректен (correct), если для любых входных данных результатом его работы являются корректные выходные данные. Мы говорим, что корректный алгоритм решает данную вычислительную задачу. Если алгоритм некорректный, то для некоторых вводов он может вообще не завершить свою работу или выдать неправильный результат.

Структуры данных

Структура данных (data structure) - способ хранения и организации данных, облегчающий доступ к этим данным и их модификацию.

Различие между алгоритмом и структурой данных

• Структура данных задаёт способ формирования и хранения данных на носителе информации.
• Алгоритм извлекает с носителя информации (из структуры данных) хранимые данные, совершает над ними манипуляции/преобразования/вычисления, требуемые задачей, обратно сохраняет промежуточные и конечные результаты преобразований на носитель информации (в структуру данных).

Таким образом, структура данных говорит нам о том, в каком виде хранить данные, а алгоритм - как эти данные обрабатывать.

---

ВПЕРЁД ⇒

Описание работы алгоритма через псевдокод

⇐ НАЗАД

Что такое алгоритмы и структуры данных

---

Источники

• Павел Маврин “АиСД, Семестр 1, Лекция 1. Оценка времени. Сортировка слиянием”
• Алгоритм (Wiki)
• Томас Кормен “Алгоритмы. Построение и анализ”. Глава 1 “Роль алгоритмов в вычислениях”, параграф 1.1 “Что такое алгоритмы” (стр. 26-32).

Категория

Алгоритмы-и-структуры-данных Алгоритмы-и-структуры-данных

Теги

• Алгоритм Алгоритм
• Отношение Отношение