Этапы решения алгоритмической задачи. Базовые структуры данных

Можно выделить несколько типов задач, которые считаются наиболее важными из-за их практического значения или каких-то свойств, представляющих особый интерес для исследования:

• сортировка;
• поиск;
• обработка строк;
• задачи из теории графов;
• комбинаторные задачи;
• геометрические задачи;
• численные задачи.

Сортировка

Задача сортировки заключается в упорядочении заданной последовательности каких-либо элементов в возрастающем порядке по ключу (некоторой части элемента). Упорядочение позволяет ускорить поиск информации. Часто сортировка используется как вспомогательный этап в некоторых алгоритмах.

Не существует универсального алгоритма сортировки, который бы наилучшим образом подходил для всех случаев. Хотя для произвольных данных доказана эффективность `n * log_2 n` операций, но для ограниченного диапазона ключей есть алгоритм c эффективностью `n`, а для небольших `n` алгоритм c эффективностью `n^2` может работать быстрее из-за больше его простоты.

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

Поиск

Задача поиска связана с нахождением заданного значения (ключа поиска) среди заданного множества (мультимножества).

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

Обработка строк

Для задач, связанных с обработкой текста, были разработаны специальные алгоритмы. К задаче поиска подстрок может быть сведена задача поиска в базе данных генетической информации.

Задачи из теории графов

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

К классическим задачам теории графов относятся: обход графа, топологическая сортировка, раскраска графа, поиск кратчайшего пути, максимального потока, минимального остова, задача о назначениях.

Комбинаторные задачи

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

Примером такой задачи является задача коммивояжера, которая заключается в нахождении кратчайшего пути между `n` городами, каждый из которых он должен посетить только один раз.

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

Геометрические задачи

Геометрические задачи возникают в компьютерной графике, робототехнике при работе с такими геометрическими объектами как точки, линии, многоугольники.

Решение некоторых из них возможно только при помощи алгоритмов, например, построение выпуклой оболочки.

Численные задачи

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

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

Задания для практики

1. Предположим, что четыре человека движутся по дороге в одном направлении и хотят перейти через мост. Ваша задача помочь им переправиться на другой берег за 17 минут. На дворе ночь, и у них только один фонарик. По мосту одновременно могут следовать не более двух человек (т.е. либо один, либо два), причем у одного из них обязательно должен быть фонарик. Фонарик нельзя перебросить с одного берега реки на другой, его можно только перенести по мосту обратно. Каждый человек затрачивает разное время на прохождение моста: первый — 1 минуту, второй — 2 минуты, третий — 5 минут и четвертый — 10 минут. Если по мосту передвигается пара людей, то они идут со скоростью более медлительного из них.
   Например, если по мосту передвигается первый и четвертый человек, то они достигнут противоположного берега через 10 минут. Если четвертый человек будет возвращать фонарь на другой берег, то с момента начала задачи пройдет 20 минут, и вы не решите задачу.
2. Назовите известные вам алгоритмы поиска. Кратко опишите словами каждый алгоритм.
3. Предложите алгоритм проверки того, являются ли два заданных слова анаграммами, т.е. того, что одно из слов может быть получено путем перестановки букв другого слова.
4. Предложите алгоритм поиска наилучшего маршрута для пассажира метрополитена. Какие критерии могут быть использованы для сравнения качества двух маршрутов?
5. Напишите алгоритм, который находит координаты общей точки двух отрезков, если таковая существует.