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

Алгоритмы

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

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

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

Какие задачи решаются с помощью алгоритмов?

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

• Целью проекта по расшифровке генома человека является идентификация всех 100000 генов, входящих в состав ДНК человека, определение последовательностей, образуемых 3 миллиардами базовых пар, из которых состоит ДНК, сортировка этой информации в базах данных и разработка инструментов для ее анализа. Для реализации всех перечисленных этапов нужны сложные алгоритмы. Это позволяет ученым достигать поставленных целей, эффективно используя вычислительные ресурсы. При этом экономится время (как машинное, так и затрачиваемое сотрудниками) и деньги, а также повышается эффективность использования лабораторного оборудования.

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

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

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

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

Алгоритмы как технология

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

Эффективность

Алгоритмы, разработанные для решения одной и то же задачи, часто очень сильно различаются по эффективности. Эти различия могут быть намного значительнее, чем те, что вызваны применением неодинакового аппаратного и программного обеспечения. В качестве примера можно привести два алгоритма сортировки. Для выполнения первого из них, известного как сортировка вставкой, требуется время, которое оценивается как с1*n2, где n — количество сортируемых элементов, а с1 — константа, не зависящая от п. Таким образом, время работы этого алгоритма приблизительно пропорционально n2. Для выполнения второго алгоритма, сортировки слиянием, требуется время, приблизительно рав-
ное c2*lg n, где lg n — краткая запись log2 n, а с2 — некоторая другая константа, не зависящая от п. Обычно константа метода вставок меньше константы метода слияния, т.е. с1 < c2. Мы убедимся, что постоянные множители намного меньше влияют на время работы алгоритма, чем множители, зависящие от п. Для двух приведенных методов последние относятся как lg n к n. Для небольшого количества сортируемых элементов сортировка включением обычно работает быстрее, однако когда n становится достаточно большим, все заметнее проявляется преимущество сортировки слиянием, возникающее благодаря тому, что для больших n незначительная величина lg n по сравнению с п полностью компенсирует разницу величин постоянных множителей. Не имеет значения, во сколько раз константа c1 меньше, чем c2. С ростом количества сортируемых элементов обязательно будет достигнут переломный момент, когда сортировка слиянием окажется более производительной.
В качестве примера рассмотрим два компьютера — А и Б. Компьютер А более быстрый, и на нем работает алгоритм сортировки вставкой, а компьютер Б более медленный, и на нем работает алгоритм сортировки методом слияния. Оба компьютера должны выполнить сортировку множества, состоящего из миллиона чисел. Предположим, что компьютер А выполняет миллиард инструкций в секунду, а компьютер Б — лишь десять миллионов. Таким образом, компьютер А работает в 100 раз быстрее, чем компьютер Б. Чтобы различие стало еще большим, предположим, что код для метода вставок (т.е. для компьютера А) написан самым лучшим в мире программистом с использованием команд процессора, и для сортировки n чисел надо выполнить 2*n2 команд (т.е. с1 = 2). Сортировка же методом слияния (на компьютере Б) реализована программистом-середнячком с помощью языка высокого уровня. При этом компилятор оказался не слишком эффективным,
и в результате получился код, требующий выполнения 50*n*lg n команд (т.е. c2 = 50). Для сортировки миллиона чисел компьютеру А понадобится 2*(106)2 команд/109 команд/c = 2000 c
компьютеру Б — 50 * 106 * lg 106команд / 107 команд/с = 100 c
Как видите, использование кода, время работы которого возрастает медленнее, даже при плохом компиляторе на более медленном компьютере требует на порядок меньше процессорного времени! Если же нужно выполнить сортировку 10 миллионов чисел, то преимущество метода слияния становится еще более очевидным: если для сортировки вставкой потребуется приблизительно 2.3 дня, то для сортировки слиянием — меньше 20 минут. Общее правило таково: чем больше количество сортируемых элементов, тем заметнее преимущество сортировки слиянием.

Алгоритмы и другие технологии

Приведенный выше пример демонстрирует, что алгоритмы, как и аппаратное обеспечение компьютера, представляют собой технологию. Общая производительность системы настолько же зависит от эффективности алгоритма, как и от мощности применяющегося аппаратного обеспечения. В области разработки алгоритмов происходит такое же быстрое развитие, как и в других компьютерных технологиях.
Возникает вопрос, действительно ли так важны алгоритмы, работающие на современных компьютерах, если и так достигнуты выдающиеся успехи в других областях высоких технологий, таких как:
• аппаратное обеспечение с высокими тактовыми частотами, конвейерной обработкой и суперскалярной архитектурой;
• легкодоступные, интуитивно понятные графические интерфейсы (GUI);
• объектно-ориентированные системы;
• локальные и глобальные сети.
Ответ — да, безусловно. Несмотря на то, что иногда встречаются приложения, которые не требуют алгоритмического наполнения (например, некоторые простые Web-приложения), для большинства приложений определенное алгоритмическое наполнение необходимо. Например, рассмотрим Web-службу, определяющую, как добраться из одного места в другое. В основе ее реализации лежит высокопроизводительное
аппаратное обеспечение, графический интерфейс пользователя, глобальная сеть и, возможно, объектно-ориентированный подход. Кроме того, для определенных операций, выполняемых данной Web-службой, необходимо использование алгоритмов — например, таких как вычисление квадратных корней (что может потребоваться для определения кратчайшего пути), визуализации карт и интерполяции адресов.
Более того, даже приложение, не требующее алгоритмического наполнения на высоком уровне, сильно зависит от алгоритмов. Ведь известно, что работа приложения зависит от производительности аппаратного обеспечения, а при его разработке применяются разнообразные алгоритмы. Все мы также знаем, что приложение тесно связано с графическим интерфейсом пользователя, а для разработки любого графического интерфейса пользователя требуются алгоритмы.
Вспомним приложения, работающие в сети. Чтобы они могли функционировать, необходимо осуществлять маршрутизацию, которая, как уже говорилось, основана на ряде алгоритмов. Чаще всего приложения составляются на языке, отличном от машинного. Их код обрабатывается компилятором или интерпретатором, которые интенсивно используют различные алгоритмы. И таким примерам нет числа.
Кроме того, ввиду постоянного роста вычислительных возможностей компьютеров, они применяются для решения все более сложных задач. Как мы уже убедились на примере сравнительного анализа двух методов сортировки, с ростом сложности решаемой задачи различия в эффективности алгоритмов проявляются все значительнее.
Знание основных алгоритмов и методов их разработки — одна из характеристик, отличающих умелого программиста от новичка. Располагая современными компьютерными технологиями, некоторые задачи можно решить и без основательного знания алгоритмов,

Ссылки

Алгоритмы: построение и анализ 2-е издание Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн

Курсы

Технологии

Продукты

Visual Studio

DreamSpark Academy

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