Алгоритмы программирования. Роль алгоритмов в программировании

Любое управление процессом требует определенных правил и четких действий. Компьютер – это устройство, предназначенное для автоматизации создания, хранения, обработки и передачи данных, а значит здесь должны выполняться четкие предписания для выполнения той или иной задачи.

Для создания программ, предназначенной для решения на ЭВМ какой-либо задачи, требуется составление алгоритма ее решения.

Алгоритмами, например, являются правила сложения, умножения, решения алгебраических уравнений, умножения матриц и т.п. Слово алгоритм происходит от algoritmi, являющегося латинской транслитерацией арабского имени хорезмийского математика IX века аль-Хорезми. Благодаря латинскому переводу трактата аль-Хорезми европейцы в XII веке познакомились с позиционной системой счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система счисления и правила счета в ней.

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

Инструкция становится алгоритмом только тогда, когда она удовлетворяет определенным требованиям. Одно из требований алгоритма однозначность, т.е. если при применении к одним и тем же данным он даст один и тот же результат.

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

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

· дискретностью;

· определенностью;

· результативностью;

· массовостью.

Дискретность – последовательное выполнение простых или ранее определённых (подпрограммы) шагов. Преобразование исходных данных в результат осуществляется дискретно во времени.

Определенность состоит в совпадении получаемых результатов независимо от пользователя и применяемых технических средств (однозначность толкования инструкций).

Результативность означает возможность получения результата после выполнения конечного количества операций.

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

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

· набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;

· правило начала;

· правило непосредственной переработки информации (описание последовательности действий);

· правило окончания;

· правило извлечения результатов.

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

Понятия алгоритма и программы разграничены не очень чётко. Обычно программой называют окончательный вариант алгоритма решения задачи, ориентированный на конкретного пользователя.

Таким образом, можно дать следующее определение программы для ЭВМ:

К основным способам описания алгоритмов можно отнести следующие:

· словесно-формульный (на естественном языке);

· структурный или блок-схемный;

· с использованием специальных алгоритмических языков;

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

Перед составлением программ чаще всего составляют алгоритм решения поставленной задачи одним из вышеописанных способов.

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

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

у = 4а – (х + 3).

Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:

1. Ввести значения а и х.

2. Сложить х и 3.

3. Умножить а на 4.

4. Вычесть из 4а сумму (х+3).

5. Вывести у как результат вычисления выражения.

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

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

Оформление программ должно соответствовать определенным требованиям (рис. 2.). В настоящее время действует единая система программной документации (ЕСПД), которая устанавливает правила разработки, оформления программ и программной документации. В ЕСПД определены и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД).

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

Любой вычислительный процесс может быть представлен как комбинация элементарных алгоритмических структур:

· Следование. Предполагает последовательное выполнение команд сверху вниз. Если алгоритм состоит только из структур следования, то он является линейным.

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

· Цикл. Предполагает возможность многократного повторения определенных действий. Количество повторений зависит от условия цикла.

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

При этом выделят три основных вида алгоритмов:

Современные системы программирования обычно предоставляют пользователям мощные и удобные средства разработки программ. В них входят:

· компилятор или интерпретатор;

· интегрированная среда разработки;

· средства создания и редактирования текстов программ;

· обширные библиотеки стандартных программ и функций;

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

· "дружественная" к пользователю диалоговая среда;

· многооконный режим работы;

· мощные графические библиотеки; утилиты для работы с библиотеками;

· встроенный ассемблер;

· встроенная справочная служба;

· другие специфические особенности.

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

Алгоpитм – это точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Название "алгоритм " произошло от латинской формы имени среднеазиатского математика аль-Хорезми - Algorithmi.

Исполнитель алгоритма - это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Исполнителя характеризуют: среда, элементарные действия, система команд, отказы. Среда (или обстановка) - это "место обитания" исполнителя. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка - системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды. После вызова команды исполнитель совершает соответствующее элементарное действие . Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.

В информатике универсальным исполнителем алгоритмов является компьютер.

2. Свойства алгоритмов

Можно выделить следующие основные свойства алгоритмов:

1) Понятность для исполнителя - т.е. исполнитель алгоритма должен знать, как его выполнять.

2) Дискретность (прерывность, раздельность) - т.е. алгоритм должен представлять процесс решения задачи как последовательное выполнение простых или ранее определенных шагов.

3) Определенность - т.е. каждое правило алгоритма должно быть четким, однозначным и не оставлять места для разночтений.

4) Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.

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

3. Формы представления алгоритмов

Наиболее распространенными формами представления алгоритмов являются: словесная, графическая, псевдокоды и программная.

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

Пример. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел.

Алгоритм: 1) задать два числа; 2) если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма; 3) определить большее из чисел; 4) заменить большее из чисел разностью большего и меньшего из чисел; 5) повторить алгоритм с шага 2.

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

Словесный способ не имеет широкого распространения, поскольку такие описания:

а) строго не формализуемы;

б) страдают многословностью записей;

в) допускают неоднозначность толкования отдельных предписаний.

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

Подробнее об этом ниже…

3) Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Он занимает промежуточное место между естественным и формальным языками.

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

Пример. 1) задать два числа x и y; 2) ЕСЛИ x=y, ТО НОД=x и КОНЕЦ; 3) ЕСЛИ x>y, ТО x=x-y, ИНАЧЕ y=y-x; 4) ПЕРЕЙТИ в пункт 2.

4) Программная форма представляет собой тексты программ, написанных на различных языках программирования.

Ниже приведены графические обозначения на блок-схемах.

На схемах СЕРИЯ обозначает один или несколько любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе - по НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ - параметр цикла, НЗ - начальное значение параметра цикла, КЗ - конечное значение параметра цикла, Ш - шаг изменения параметра цикла.

Начало и конец алгоритма на блок-схемах обозначают овалом, вводимые и выводимые переменные записываются в параллелограмме.

Проблема

• 5-6 лет потерянных на изучение предметов и наук, которые больше никогда не понадобятся;
• Необходимая смена мышления с гуманитарного\технического на логическое\цифровое;
• Освоение 5-6 лет программы технического вуза в кратчайшие сроки;
• Создание угрозы жизни и благополучия людей, компаний, бизнеса...

Время

Хорошо, если он обучается на платном отделении, а если за счет государства? Это значит, что кто-то, мечтавший стать архитектором, менеджером, финансистом, военным, не попал на это место. Ему пришлось искать другое место под солнцем, возможно, он пошел учиться на программиста.

Там же все просто!

Приведу несколько жизненных примеров:

1. «Программист» пишет вторую версию программы. В первой - была одна форма на 50 кнопок. Вторая версия обладает большей функциональностью, но ее логика не так прозрачна. Планируется писать программу пару месяцев. В функционал заложено порядка 100 кнопок на одной форме. После 10-и минутного введения в теорию графов количество кнопок сократилось до одной (удаление точки), срок написания программы сократился до двух дней.
2. «Программисту» дали задание написать программу-конвертер. Логика простая: приходит пакет вида ключ=значение, надо по специальной таблице конвертировать его в пакет2 вида ключ2=значение2 и отправить дальше. После двух месяцев «изучения платформы» ему был передан каркас приложения (прием пакета, трансформация, отправка пакетов) старшими товарищами. Через месяц конвертер был готов!
3. Множество реализованных велосипедов;
4. Говорящий за себя http://govnokod.ru ;

Таланты

«Найди себе дело по душе и ни единой минуты в жизни ты не будешь работать» - Конфуций. Важно не потратить на поиск этого дела всю жизнь, иначе придется всю жизнь «вкалывать».

Запах пороха

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

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

Заключение

Все же, думаю, большинство «новых программистов» стремятся больше зарабатывать: сидишь себе - деньги получаешь. Правда, потом такие люди сильно подводят свою команду, работают не в полную силу. А если еще и начальство закроет на это глаза (да, да, такое бывает!), то с ними каши не сваришь, google не разработаешь.

Как показывают исследования . IT в России - не самая высокооплачиваемая отрасль. Она занимает лишь третье место. На втором месте сырьевые отрасли, а на первом - высший менеджмент . Из-за специфики IT, программист никогда не достигнет ступеньки высшего менеджмента. Максимум, на что стоит рассчитывать, это должность руководителя отдела, ведущего направления, директора собственной компании.

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

P.S. В комментариях спрашивают про цели заметки: серьезнее относиться в выбору профессии, заниматься только любимым делом, учиться тому что нравится, профессионально расти, а не пробовать все понемногу без определенной цели. Удивляют люди, которые в 30-40 лет так и не смогли найти себе занятие по душе.

). Разработка программы с помощью такой системы программирования состоит из двух этапов: 1) создание в визуальном режиме элементов графического интерфейса программы; 2) разработка программного кода. Такой подход существенно облегчает создание программ, так как разработка графического интерфейса вручную (в процедурных языках) сложный и трудоёмкий процесс.

Первый шаг к пониманию важности изучения и знания алгоритмов это дать точное определение тому, что понимается под алгоритмом. Алгоритм в программировании- это понятная и точная последовательность действий , записанных на языке программирования.Согласно популярной книге Алгоритмы: построение и анализ (Кормен, Лейзерсон, Ривест, Штайн)"алгоритм (algorithm) - это любая корректно определенная вычислительная процедура, на вход (input) которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (output) величина или набор значений". Другими словами, алгоритмы похожи на дорожные карты для достижения четко определенной цели. Код, для вычисления членов последовательности Фибоначчи - это реализация конкретного алгоритма. Даже простая функция сложения двух чисел является алгоритмом, хотя и простым.

Для создания алгоритма (программы) необходимо знать:

полный набор исходных данных задачи (начальное состояние объекта);

цель создания алгоритма (конечное состояние объекта);

систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить).

Полученный алгоритм (программа) должен обладать следующим набором свойств:

дискретность (алгоритм разбит на отдельные шаги - команды);

однозначность (каждая команда определяет единственно возможное действие исполнителя);

понятность (все команды алгоритма входят в систему команд исполнителя);

результативность (исполнитель должен решить задачу за конечное число шагов).

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

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

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

Анализ времени выполнения алгоритма

Одним из наиболее важных аспектов алгоритма является его скорость. Часто бывает легко придумать алгоритм решающий задачу, но если алгоритм слишком медленный, то он возвращается на доработку. Поскольку точная скорость алгоритма зависит от того где запускается алгоритм, а также деталей реализации, компьютерные специалисты обычно говорят о времени выполнения относительно входных данных. Например, если вход состоит из N целых чисел, то алгоритм может иметь время выполнения пропорциональное N 2 , что представляется как O(N 2). Это означает, что если вы запустите реализацию алгоритма на компьютере с входом размером в N, то это займет C*N 2 секунд, где C-некоторая константа, которая не меняется с изменением размера входа.

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

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

Приведем пример описания алгоритма суммирования двух величин в виде блок-схемы:

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

Сортировка

Сортировка является хорошим примером алгоритма, который часто используется программистами. Самый простой способ отсортировать группу элементов это начать с удаления наименьшего элемента из группы, и поставить его первым. Затем удаляется второй по величине элемент и ставится вторым и т.д. К сожалению, время работы этого алгоритма составляет O(N 2), а это означает, что потребуется количество времени пропорциональное количеству элементов в квадрате. Если бы нам пришлось сортировать млрд. элементов, то этот алгоритмы бы потребовал 10 18 операций. Если считать что обычные настольные ПК делают примерно 10 9 операций в секунду, то потребуются годы чтобы закончить сортировку этого млрд. элементов.

К счастью существует ряд более совершенных алгоритмов, например, быстрая сортировка (quicksort), пирамидальная сортировка (heapsort) и сортировка слияния(mergesort). Эти алгоритмы имеют время выполнения O(N * Log(N)). Таким образом, число операций необходимых для сортировки млрд. элементов сокращается до таких разумных пределов, что даже самый дешевый настольный ПК способен провести такую сортировку. Вместо млрд. в квадрате операций (10 18) эти алгоритмы требуют только 10 млрд. операций (10 10), т.е. в 100 млн. раз быстрее.

Кратчайший путь

Алгоритмы поиска кратчайшего пути из одной точки в другую исследуются уже на протяжении многих лет. Примеров прикладного применения этих алгоритмов предостаточно, однако для простоты изложения будем придерживаться следующей постановки: требуется найти кратчайший путь из точки А в точку Б в городе с несколькими улицами и перекрестками. Существует много разных алгоритмов для решения этой задачи и все они со своими преимуществами и недостатками. Прежде чем мы углубимся в их изучение, давайте рассмотрим время выполнения простого алгоритма перебором. Если алгоритм рассматривает каждый возможный путь от А до Б (который не образует циклов) он вряд ли закончится при нашей жизни, даже если А и Б находятся в маленьком городке. Время выполнения этого алгоритма является экспоненциальным, что обозначается как O(C N) для некоторого C. Даже для малых значений C, C N становится астрономическим числом, когда N принимает умеренно большое значение.

Один из самых быстрых алгоритмов для решения этой задачи имеет время выполненияO(E+V*Log(V)), где E число дорожных сегментов, а V число пересечений. Алгоритм займет около 2 секунд времени, для поиска кратчайшего пути в городе из 10000 пересечений и 20000 дорожных сегментов (обычно бывает около 2 дорожных сегментов на одно пересечение). Этот алгоритм известен как алгоритм Дейкстры, он является довольно таки сложным и требует использования структуры данных очередь с приоритетом (priority queue). Однако в некоторых случаях даже такое время выполнения является слишком медленным (взять например нахождение кратчайшего пути от Нью-Йорка до Сан-Франциско - в США есть миллионы пересечений), в таких случаях программисты пытаются улучшить время выполнения с помощью так называемой эвристики. Эвристика - это приближенное значение чего-то, что имеет отношение к задаче. В задаче поиска кратчайшего пути, например, может оказаться полезным знать, как далеко находится точка от пункта назначения. Зная это можно разработать более быстрый алгоритм (например алгоритм поиска А* в некоторых случаях работает значительно быстрее чем алгоритм Дейкстры). Такой подход не всегда улучшает время выполнения алгоритма в наихудшем случае, но в большинстве реальных приложений алгоритм начинает работать быстрее.

Приближенные алгоритмы

Иногда даже самый продвинутый алгоритм с самой продвинутой эвристикой работает слишком медленно на самом быстром компьютере. В таких случаях приходится снижать точность конечного результата. Вместо того чтобы пытаться получить кратчайший путь, можно ограничиться путем, который например на 10% больше чем кратчайший путь.

На самом деле есть немало важных задач, для которых известные на сегодня алгоритмы выдают оптимальный результат слишком медленно. Наиболее известная группа из этих задач называется NP (non-deterministic polynomial). Если задача называется NP-полной или NP-трудной, то это означает, что никто не знает достаточно хорошего способа для получения оптимального решения. Кроме того, если кто-то разработает эффективный алгоритм для решения одной NP-трудной задачи, то этот алгоритм можно будет применить ко всем NP-трудным задачам.

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

Случайные алгоритмы

Еще один подход, применяемый для решения некоторых задач, заключается в том, чтобы сделать алгоритм случайным. Данный подход не улучшает время алгоритма в худшем случае, но довольно часто хорошо работает в среднем случае. Алгоритм быстрой сортировки является хорошим примером использования рандомизации. В худшем случае, алгоритм быстрой сортировки сортирует группу элементов за O(N 2), где N количество элементов. Если в этом алгоритме использовать рандомизацию, то шансы на худший случай становятся незначительно малыми, и в среднем случае алгоритм быстрой сортировки работает за время O(N*Log(N)). Другие алгоритмы даже в худшем случае гарантируют время работы O(N*Log(N)), однако они медленнее в среднем случае. Хотя оба алгоритма имеют время работы пропорциональное N*Log(N), алгоритм быстрой сортировки имеет более меньший постоянный коэффициент (constant factor) - т.е. он требует C*N*Log(N), в то время как другие алгоритмы требуют более 2*C*N*Log(N) операций.

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

Основная идея алгоритма поиска медианы это выбрать среди чисел случайное, и посчитать, сколько чисел в группе меньше чем выбранное число. Допустим, есть N чисел, K из них меньше или равно выбранному числу. Если K меньше чем половина N, тогда мы знаем что медиана это (N/2-K)-е число которое больше чем случайно выбранное число, так что мы отбрасываем K чисел меньших или равных случайному числу. Теперь допустим мы хотим найти (N/2-K)-е наименьшее число, вместо медианы. Алгоритм такой же, мы просто случайно выбираем число и повторяем описанные шаги.

Сжатие

Еще один класс алгоритмов предназначен для сжатия данных. Этот алгоритм не имеет ожидаемого результата (как например, алгоритм сортировки), но вместо этого делается оптимизация по некоторым критериям. В случае сжатия данных, алгоритм (например, LZW) пытается сделать так чтобы данные занимали как можно меньше байтов, но в то же время, чтобы можно было распаковывать их до первоначальной формы. В некоторых случаях этот тип алгоритмов использует те же методы что и другие алгоритмы, что приводит к хорошему результату, но неоптимальному. Например, JPG и MP3 сжимают данные таким образом, что конечный результат получается более низкого качества, чем оригинал, однако и размер меньше. MP3 сжатие не сохраняет каждую особенность оригинального аудио файла, но пытается сохранить достаточно деталей, чтобы обеспечить приемлемое качество и в то же время значительно сократить размер файла. Формат JPG следует тому же принципу, но детали существенно отличаются, т.к. целью является сжатие изображения, а не аудио.

Зачем нужно знать всякие алгоритмы

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

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

В качестве примера можно рассмотреть, как работают сетевые коммутаторы. Коммутатор имеет N подключенных к нему кабелей, и принимает пакет данных, поступающих по этим кабелям. Коммутатор должен сначала проанализировать пакеты, а затем отправить их обратно по правильному кабелю. Коммутатор также как и компьютер работает в дискретном режиме - пакеты отправляются дискретными интервалами, а не непрерывно. Быстрый коммутатор стремится послать, как можно больше пакетов в течение каждого интервала иначе они накопятся и коммутатор "упадет". Цель алгоритма отправлять максимальное количество пакетов в течение каждого интервала, а также обеспечить порядок, при котором пакеты, пришедшие раньше других отправлялись тоже раньше других. В этом случае оказывается, что для решения этой задачи подходит алгоритм известный как "stable matching", хотя на первый взгляд это может быть не очевидно. Такие связи между задачей и решением можно обнаружить только с помощью уже имеющихся алгоритмических знаний.

Реальные примеры

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

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

Алгоритм поиска максимального потока

Задача поиска максимального потока состоит в том, чтобы посредством имеющейся сети наилучшим образом переместить что-то из одного места в другое. Конкретно такая проблема впервые возникла в 1950-х в связи с железнодорожными путями Советского Союза. США хотели знать, как быстро Советский Союз может подвозить материалы к государствам-сателлитам в Восточной Европе через свою сеть железных дорог.

Кроме того США хотели знать какую часть рельсов можно наиболее легко уничтожить чтобы отрезать государства-сателлиты от остальной части Советского Союза. Оказалось, что эти две задачи тесно связаны и что решение задачи поиска максимального потока также решает задачу о минимальном разрезе, что, в конечном счете, позволит выяснить самый дешевый способ отрезать Советский Союз от своих спутников.

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

Поскольку задача была четко поставлена, обнаружилось множество различных применений. Алгоритм напрямую связан с Интернетом, где важно транспортировать максимум данных из одной точки в другую. Задача также возникает во множестве бизнес-процессов, и является важной частью исследования операций. Например, если есть N сотрудников и N задач, которые должны быть сделаны, но не каждый сотрудник может справиться с каждой задачей, то поиск максимального потока выдаст решение, как назначить N сотрудников на задачи таким образом, чтобы каждая задача была выполнена при условии что это возможно. Задача Graduation из TopCoder SRM 200является хорошим примером задачи на поиск максимального потока.

Сравнение последовательностей

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

Например, рассмотрим последовательности "AABAA" и "AAAB". Для преобразования первой последовательности во вторую самое простое, что нужно сделать это удалить B в середине и изменить последнюю A на B. Этот алгоритм имеет множество применений, включая некоторые задачи связанные с ДНК и обнаружением плагиата. Однако многие программисты используют его в основном для сравнения версий одного и того же файла с исходным кодом. Если элементы последовательности это строки в файле, тот этот алгоритм позволяет узнать какие строки надо удалить, вставить, изменить чтобы преобразовать одну версию файла в другую.

Без динамического программирования приходится перебирать экспоненциальное число преобразований, чтобы перейти от одной последовательности к другой. Однако динамическое программирование сокращает время выполнения алгоритма до O(N*M), где N и M количество элементов в двух последовательностях.

Заключение

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