Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

ЧТО ТАКОЕ АЛГОРИТМ? 19
Возьмем три удара и четыре тихих отрезка:
×
×
×
•
•
• •
Ритм в пропорции семь/четыре довольно популярен, и не только в тра- диционной музыке. Среди прочих мелодий его можно расслышать в песне
Monkey.
Таким образом, составляя столбцы из крестиков и точек и перемещая их туда-сюда, как мы только что делали, можно вывести много других рит- мов. Чтобы проиллюстрировать эту процедуру, для наглядности мы изме- ряли оставшиеся столбцы. Вместо создания столбцов, проверки их располо- жения и перемещения их из стороны в сторону мы могли бы оформить все это в виде простых численных операций. Давайте вернемся к примеру из 12 ча- стей и семи ударений. Для начала разделим 12 на 7, что даст нам целую часть 1 и остаток 5:
12 = 1 × 7 + 5.
Это говорит о том, что семь ударений нужно поместить в начало. Полу- чится семь акцентированных отрезков, за которыми следуют оставшиеся пять тихих:
× × × × × × × • • • • •
Давайте еще раз выполним деление, но на этот раз разделим сам делитель из предыдущей операции 7 на полученный остаток 5. Мы снова получим це- лую часть 1 и остаток 2:
7 = 1 × 5 + 2.
Это означат, что нам нужно взять пять столбцов справа и поместить их под пятью столбцами слева. Останется 2:
× × × × × × ×
• • • • •

20 ГЛАВА 1
Повторим тот же шаг: разделим делитель предыдущей операции 5 на ее остаток 2. Получится 2 с остатком 1:
5 = 2 × 2 + 1.
Из этого следует, что мы должны дважды взять два крайних справа столбца и поместить их под двумя столбцами, крайними слева. Останется 1:
× × ×
× ×
× ×
• • •
• •
Обратите внимание на то, что дважды — это эквивалент двух шагов без использования деления, которые мы выполняли ранее. Сначала мы пере- шли бы от
× × × × × × ×
• • • • •
к
× × × × ×
× ×
• • • • •
а затем к
× × ×
× ×
× ×
• • •
• •
Если свести столбцы вместе, получится ритм Mpre:
×
× ×
×
× ×
×
•
•
•
•
•

ЧТО ТАКОЕ АЛГОРИТМ? 21
Наш первый алгоритм
Метод, который мы применяли выше, можно записать чуть более формально, разбив его на следующие шаги. Предполагается, что мы начинаем с двух чи- сел, a и b. Пусть a будет общим количеством отрезков. Если ударений больше, чем тихих отрезков, b обозначает количество ударений. В противном случае это количество тихих отрезков. Вначале мы выставляем в ряд ударения, за ко- торыми идут тихие отрезки.
1. Выполняем деление a на b. Так мы получим целую часть (q) и остаток (r).
Выходит a = q × b + r. Это знакомое всем целочисленное деление. Берем
b крайних справа столбцов q раз и размещаем их под крайними слева столбцами, оставляя справа r столбцов.
2. Если остаток r равен нолю или единице, мы останавливаемся. В про- тивном случае возвращаемся к шагу 1, но на этот раз роль а играет b, а роль b — r. Иными словами, мы повторяем первый шаг, делая a рав- ным b, и b равным r.
Повторяем деление в эти два этапа, пока это имеет смысл. Выполненные нами шаги можно оформить в виде следующей таблицы (как и раньше, начи- наем с a = 12 и b = 7 и получаем в каждой строке a = q × b + r):
a
q
b
r
12 1 7 5 7
1 5 2 5
2 2 1
Если проанализировать эту таблицу, можно убедиться в том, что каждая строка соответствует одному этапу формирования и перемещения столбцов.
Но этот метод можно описать еще точнее. На самом деле мы получили после- довательность шагов, которые можно выполнить с помощью ручки и листа бумаги. Это наш первый алгоритм! Он позволяет создавать последовательно- сти, которые соответствуют удивительно большому количеству музыкальных ритмов. Меняя смещения и число тихих отрезков, мы можем получить около
40 последовательностей, которые встречаются в разных ритмах по всему миру. Этот простой алгоритм (всего два шага, которые повторяются) выдает столько интересных результатов!

22 ГЛАВА 1
Но наш алгоритм этим не ограничивается. Поскольку речь идет о деле- нии двух чисел, давайте подумаем о следующей проблеме общего характера: как найти максимальный делитель, который подходит как для a, так и для b?
Это наибольший общий делитель двух чисел. Он встречается в элементарной арифметике, например в следующей задачке: если у нас есть 12 пакетов с кре- керами и 4 пакета с сыром, как распределить их по корзинам таким образом, чтобы в каждой корзине крекеры и сыр были в одной и той же пропорции?
Так как 12 делится на четыре, вы получите четыре корзины с тремя пакетами крекеров и одним пакетом сыра в каждой; наибольший общий делитель для
12 и 4 равен 4. Все становится интереснее, если взять 12 пакетов с крекерами и восемь пакетов с сыром. Одно на другое не делится, но наибольшее число, на которое можно поделить 12 и 8, равно 4; это означает, что у вас опять по- лучится четыре корзины, но на этот раз с тремя пакетами крекеров и двумя пакетами сыра в каждой.
Так как же найти наибольший общий делитель для двух произвольных це- лых чисел? Мы уже видели, что, если одно число делится на другое, этот дели- тель и есть наибольший общий. В противном случае достаточно найти наи- больший общий делитель остатка от деления этих двух чисел и второго числа.
Это проще изобразить с помощью математических символов. Если у нас есть два числа, a и b, их наибольший общий делитель равен наибольшему общему делителю остатка от a ÷ b и b. Это возвращает нас к ритмам: их подбор подо-
бен поиску наибольшего общего делителя двух чисел.
Метод поиска наибольшего общего делителя для двух чисел называется
алгоритмом Евклида, в честь древнегреческого математика Евклида, кото- рый впервые описал его в своей книге «Начала» (300 г. до н. э). Основная идея этого метода в том, что наибольший общий делитель для двух чисел оста- ется неизменным, если вместо большего числа подставить результат вычи- тания из него меньшего числа. Возьмем, к примеру, 56 и 24. Их наибольший общий делитель равен 8, что является наибольшим общим делителем и для
56 – 24 = 32 и 24, а также для 32 и 24 и т. д. Повторение вычитания — это фак- тически деление, поэтому алгоритм Евклида состоит из следующих шагов.
1. Чтобы найти наибольший общий делитель для a и b, делим a на b. Это даст нам целую часть (q) и остаток (r). Тогда получается a = q × b + r.
2. Если остаток r равен 0, мы останавливаемся, а наибольший общий дели- тель для a и b будет равен b. В противном случае возвращаемся к шагу 1, но на этот раз роль а играет b, а роль b — r. Иными словами, мы повто- ряем первый шаг, делая a равным b и b равным r.

ЧТО ТАКОЕ АЛГОРИТМ? 23
Это, в сущности, те же шаги, которые мы видели ранее. Единственное от- личие в том, что при поиске ритма мы останавливаемся, если остаток во вто- ром шаге равен 0 или 1, а алгоритм Евклида останавливается, только если остаток равен 0. Но на самом деле это то же самое: если остаток равен 1, при следующем повторении первого шага получается нулевой остаток, так как на 1 делится любое целое число. Попробуем 9 и 5: 9 = 1 × 5 + 4, поэтому мы делаем 5 = 1 × 4 + 1 и затем 4 = 1 × 4 + 0; таким образом наибольший об- щий делитель 9 и 5 равен 1.
Чтобы вам было легче понять, как это работает, взгляните на следующую таблицу с a = 136 и b = 56, похожую на ту, которую мы уже видели при обсу- ждении наших ритмов. Получается, что наибольшим общим делителем для
136 и 56 является число 8.
a
q
b
r
136 2 56 24 56 2 24 8
24 3
8 0
Как уже отмечалось с 9 и 5, алгоритм Евклида выдает правильный резуль- тат во всех случаях, даже когда у двух чисел нет никакого общего делителя, кроме 1. Именно это произошло с a = 9 и b = 5. Вы можете сами увидеть, что случится, если попробовать выполнить этот алгоритм для a = 55 и b = 34; он пройдет несколько шагов, но в итоге определит, что единственный общий де- литель равен 1.
Шаги алгоритма Евклида выполняются в строго определенном порядке.
Ниже описано, как они объединяются в целое.
1. Шаги формируют последовательность.
2. Шаги могут описывать выборку, которая определяет, что делать дальше.
В шаге 2 мы проверяем, равен остаток 0 или нет. Затем в зависимости от результата предоставляются две альтернативы: мы либо останавли- ваемся, либо возвращаемся к шагу 1.
3. Шаги могут находиться в цикле и выполняться многократно. Если в шаге
2 остаток не равен 0, мы возвращаемся к шагу 1.
Эти три способа объединения шагов называются управляющими струк-
турами, поскольку они определяют, какие действия будут выполнены в про- цессе работы алгоритма. Все алгоритмы структурированы подобным образом.

24 ГЛАВА 1
Они состоят из шагов, на которых производятся вычисления и обрабатыва- ются данные; эти шаги собираются в единое целое и регулируются с помо- щью приведенных выше управляющих структур. Более сложные алгоритмы состоят из большего числа шагов, и их механизмы регулирования могут быть более замысловатыми. Но этих трех управляющих структур достаточно для описания того, как скомпоновать шаги любого алгоритма.
Кроме того, шаги алгоритма могут работать с вводом, который мы предо- ставляем. Ввод — это данные, обрабатываемые алгоритмом. Если поставить данные во главу угла, можно сказать, что алгоритмы предназначены для пре- образования информации, описывающей задачу, в нечто, соответствующее ее решению.
Мы обнаружили алгоритм, представляющий собой операции деления, за музыкальными ритмами, но в действительности нам необязательно по- гружаться так глубоко, ведь операция деления сама по себе является алго- ритмом. Даже если вам ничего не известно о Евклиде, вы знаете, как поде- лить два больших числа; в начальной школе все учатся умножать и делить в столбик. Учителя час за часом вдалбливали нам в головы, как выполнять эти операции; это были последовательности шагов, в ходе которых мы раз- мещали числа в нужных местах и делали с ними всякие вещи, то есть алго- ритмы. Но алгоритмы не ограничены одними лишь числами. Вы сами видели, что с их помощью можно создавать музыку. Это способ распределения ударе- ний на отрезке времени, но тот же принцип применим и для упаковывания крекеров с сыром.
Источник применения алгоритма Евклида к ритмам довольно необыч- ный — лаборатория SNS в Ок-Ридж, Теннесси. SNS расшифровывается как
(нейтронный источник); он генерирует интенсивное импульсное нейтрон- ное излучение, которое используют для экспериментов в физике элементар- ных частиц (корень слова spallation, spall, означает дробление материи на бо- лее мелкие части; если обратиться к ядерной физике, тяжелое ядро излучает большое количество протонов и нейтронов, если попасть в него высокоэнер- гетической частицей). В работе SNS участвуют такие компоненты, как блоки питания высокого напряжения, которые позволяют сделать пульсацию более равномерной. Алгоритм, выведенный для распределения импульсов, по сво- ему принципу не отличается от евклидового или того, который мы использо- вали для получения ритмов. Таким образом мы пришли от музыки к числам, а затем к субатомным частицам.

ЧТО ТАКОЕ АЛГОРИТМ? 25
Алгоритмы, компьютеры и математика
Мы сказали, что алгоритмы не имеют прямого отношения к компьютерам, но на сегодня большинство людей связывает эти понятия. Действительно, компьютер позволяет проявить настоящий потенциал алгоритмов, однако это всего лишь устройство, которое выполняет отдаваемые ему команды.
Чтобы командовать компьютером, мы его программируем, и обычно это де- лается для выполнения алгоритмов.
Это подводит нас к самому программированию. Программирование — это преобразование наших намерений в такой вид, в котором их может по- нять компьютер. Этот «вид» мы называем языком программирования, потому что иногда это действительно выглядит так, будто мы пишем текст на чело- веческом языке. Но языки программирования несравнимы по своему раз- нообразию и сложности с человеческой речью. Компьютер, конечно же, ни- чего в действительности не понимает. Возможно, в будущем что-то изменится и нам удастся создать по-настоящему разумные устройства, но пока, когда мы говорим о том, что компьютер что-то понимает, мы имеем в виду, что язык пе- реводится в набор инструкций для управления током в электронных схемах
(вместо тока также можно использовать свет, но принцип тот же).
Если алгоритм — это последовательность шагов, которые мы можем вы- полнить самостоятельно, то программирование — это процесс записи этих шагов в формате, понятном компьютеру. И компьютер сам занимается их вы- полнением. Компьютеры работают намного быстрее людей, поэтому они мо- гут выполнять те же шаги за меньшее время. Основополагающим фактором вычислений является скорость. Компьютеры не могут делать что-то прин- ципиально отличное от того, что делаем мы, люди, но они могут делать это быстрее — намного быстрее. Алгоритм становится существенно полезнее на компьютере, поскольку там он может быть выполнен на порядок быстрее, хотя шаги, из которых он состоит, все те же.
Язык программирования позволяет нам описать для компьютера шаги алгоритма. Он также дает возможность структурировать их с помощью трех фундаментальных управляющих структур: последовательности, выбора и итерации. Мы записываем эти шаги и определяем, как они должны быть скомпонованы, используя словарь и синтаксис нашего языка программиро- вания.
Помимо скорости, у компьютеров есть еще одно преимущество. Вспо- мните, как вы учились делить и умножать в столбик — это требовало много практики и было довольно скучно. Как уже отмечалось выше, эти вещи

Программирование — это преобразование наших намерений в такой вид, в котором их может понять компьютер. Этот «вид» мы называем языком
программирования.

ЧТО ТАКОЕ АЛГОРИТМ? 27
вбивались нам в головы в раннем возрасте, и процесс не самый приятный.
Но компьютерам не бывает скучно, поэтому еще одна причина доверить им алгоритмы состоит в том, что так мы можем освободить себя от рутинной ра- боты и заняться чем-то более интересным.
Алгоритмы в основном выполняются на компьютере, но на языках про- граммирования их, как правило, записывают люди, поэтому мы должны по- нимать, как они работают и как их можно использовать. Это подводит нас к кое-чему очень важному, о чем иногда забывают даже бывалые программи- сты и опытные специалисты в области компьютерных наук. Алгоритм по-на- стоящему можно понять только одним способом, — выполнив его вручную.
Мы должны уметь выполнять алгоритмы так же, как компьютеры выполняют программы, которые реализуют эти алгоритмы. Нам посчастливилось жить во времена, когда для изучения всевозможных вещей доступно невероятное количество материала: превосходные видеоуроки, анимированные курсы и симуляции находятся на расстоянии одного щелчка мышью. Это все заме- чательно, но на случай каких-либо трудностей всегда держите при себе ручку и блокнот. Это относится и к данной книге. Вы уверены, что поняли, как со- здаются ритмы? Пробовали делать это сами? Можете ли вы найти наиболь- ший общий делитель для 252 и 24?
Все программы реализуют последовательность шагов для выполнения каких-то задач, поэтому может возникнуть соблазн приравнять их к алгорит- мам. Но мы относимся к этому более строго и хотим, чтобы наши шаги обла- дали определенными характеристиками.
1. Количество шагов должно быть конечным. Алгоритмы не могут рабо- тать вечно (программа может работать до тех пор, пока работает ком- пьютер, на котором она запущена; но такая программа была бы не реа- лизацией алгоритма, а просто вычислительным процессом).
2. Шаги должны быть точными, чтобы их можно было выполнять без дву- смысленностей.
3. Алгоритм может работать с каким-нибудь вводом; например, алгоритм
Евклида работает с двумя целыми числами.
4. У алгоритма есть какой-то вывод; в этом весь его смысл: вернуть что-то в качестве результата. В алгоритме Евклида это наибольший общий де- литель.
5. Алгоритм должен быть эффективным. У человека должна быть возмож- ность выполнить каждый его шаг за разумное время с помощью ручки и листа бумаги.