Что такое алгоритм и зачем оно нам нужно
Компьютер, как современная техническая игрушка, интересен и сам по себе, но в деловом мире важнее то, для решения каких задач эта "игрушка" может быть использована.
Ясно, что если требуется всего лишь сложить несколько чисел, то быстрее и дешевле сложить их столбиком вручную на бумаге, чем приобретать для этого сложный и дорогой прибор. Однако, применение компьютера оправдано для тех задач, в которых:
- количество исходных данных невелико, но требуется очень сложная, многоступенчатая их обработка (например, вычисление тригонометрической функции или решение алгебраического уравнения пятой степени);
- обработка данных является простой, но количество исходных данных очень велико (например, поиск нужной записи в неупорядоченном телефонном справочнике на миллион абонентов или упорядочение этого справочника по алфавиту);
- очень большое количество исходных данных и очень сложная их обработка (например, численный прогноз погоды).
Даже человеку практически невозможно решить задачу, если он не знает метода её решения. Если задачу должна решать машина, тем более, все действия нужно расписать по элементарным шагам. То есть, подготовить для машины программу.
Тот, кому приходится исполнять программу (это может быть человек или машина), понимает и умеет выполнять лишь определённый набор команд. К примеру, выпускник средней школы способен выполнить команду "приготовить завтрак". Может выполнить команду "решить квадратное уравнение". Даже может найти и принести пришедшей с работы маме домашние тапочки, если она хорошо попросит.
Центральный процессор компьютера обладает гораздо более скромными
способностями. Тапочки он, уж точно, не сможет принести. Ведь это электронный автомат для работы с числами. Но, (вот беда!) ни нахождение интегралов, ни даже решение квадратных уравнений не входят в набор "встроенных" в него команд. Изначально процессор может выполнять лишь команды сложения, вычитания, умножения и деления чисел, команды сравнения двух чисел между собой, команды чтения чисел из памяти и записи в память, и тому подобные простейшие вещи.
Для выполнения более сложных действий, например, для нахождения тригонометрической функции или упорядочения списка по алфавиту, процессору требуется внешняя (то есть, не "вшитая" в него при его изготовлении) программа. Причём, алгоритм, лежащий в её основе, должен быть составлен, в конечном счёте, только из элементарных арифметических и логических действий с числами.
Где искать синус?
Математические вычисления всегда производятся по алгоритмам, иногда на удивление сложным. Но для первого впечатления, чтобы сразу не отбить охоту, мы разберем сравнительно простой пример.
Пусть требуется найти синус заданного угла.
(Может быть, он нужен капитану дальнего плавания, чтобы проложить курс корабля с учётом направления и скорости подводного течения. А может быть, Вы просто поспорили на миллион, что для любого заданного угла сможете найти синус.)
Будем «танцевать», как принято в математике, «от печки», то есть рассмотрим определение. Выберем, например, такое: синус - это число, равное отношению длины катета к длине гипотенузы прямоугольного треугольника.
Согласно этому, алгоритм нахождения синуса угла α, который, например, задан в градусах, должен был бы быть таким:
- С помощью транспортира и линейки построить прямоугольный треугольник с углом α при вершине.
- Измерить длину противолежащего к углу катета и длину гипотенузы. Получатся два числа.
- Разделить первое число на второе.
К сожалению, в этом алгоритме не все хорошо. Даже если этот танец с транспортиром и линейкой исполняется человеком, возникает трудность точного построения заданного угла. Длину сторон треугольника тоже можно измерить только приближенно. Ну а для компьютера такой алгоритм и вовсе не годится, так как процессор компьютера для геометрических построений и измерений не предназначен.
К счастью, как выяснили математики, вполне можно обойтись без построения треугольника.
Нахождение синуса можно свести к вычислению значения полинома (алгебраического многочлена) определенного вида. Это большая удача, потому что при вычислении значения полинома применяются только арифметические действия, и для такой деятельности компьютер идеально подходит.
Если x – угол, заданный в радианах (обратите внимание: в радианах, а не в градусах!), полином, «представляющий» синус, имеет вид:
Внимательно изучая эту формулу, можно заметить много интересного.
Во-первых, каждый член «волшебного» полинома представляет собой дробь. В числителе этой дроби стоит нечётная степень x, а в знаменателе - произведение натуральных чисел, начиная от единицы и кончая числом, равным показателю степени х.
Во-вторых, знаки членов полинома (плюс или минус) - чередуются. Многоточие в конце формулы означает, что полином бесконечно длинный. В высшей математике такой полином принято называть степенным рядом.
С ростом порядкового номера, члены этого ряда быстро убывают (потому что знаменатель дроби растёт), и, следовательно, суммировать бесконечное число членов на практике не требуется. Достаточно просуммировать несколько начальных. Конечно, нужно иметь в виду, что от количества учтённых членов зависит точность результата. (Чтобы вычислить синус абсолютно точно, пришлось бы просуммировать весь бесконечный степенной ряд, и мы обречённо занимались бы этим до конца своей жизни.)
Вот пример "экономного" компьютерного алгоритма нахождения sin(α), основанного на весьма "урезанном" степенном ряде:
- Преобразовать значение угла из градусов в радианы по формуле:
x = α ∙ 3,1415926 / 180
Это и есть первый член полинома. - Вычислить квадрат аргумента:
y = x^2 - Вычислить второй член полинома по формуле:
p = x ∙ y / (2∙3) - Вычислить третий член полинома по формуле:
q = p ∙ y / (4∙5) - Сложить найденные члены полинома с учетом их знака:
sin(α) = x – p + q
Этот алгоритм содержит не такое уж большое количество арифметических действий. Их нужно лишь строго по порядку "тупо" выполнять, и в итоге получится ответ.
Насколько результат окажется точным? Для испытания вычислим по этому алгоритму синус 30 градусов (его точное значение равно 0,5).
Результаты всех вычислений (приведённые с шестью значащими цифрами):
α = 30
x = 0,523598
y = 0,274155
p = 0,0239245
q = 0,000327951
sin(α) = 0,523598 – 0,0239245 + 0,000327951 = 0,500001
Неплохо. Итак, Вы выиграли спор. Миллион - Ваш!
Считаем секунды до встречи
На этот раз рассмотрим пример задачи, ответ для которой не удаётся вычислить по формуле так уж запросто. Ответ нужно наугад искать среди множества чисел. Искать аналогично тому, как ищут грибы в лесу (разумеется, съедобные).
Разрешите Вам представить: задача поиска нужного элемента в некотором списке! Итак, начнём.
Четыреста лет назад итальянский физик и астроном Галилео Галилей экспериментально изучал законы свободного падения тел и выяснил важное правило: расстояние, пройденное падающим телом, пропорционально квадрату времени падения.
В современных обозначениях это утверждение записывается формулой:
где h - расстояние, пройденное телом (высота, с которой оно упало), g - ускорение свободного падения (примем для него величину 10 м/с^2), t - время падения.
Если время падения известно, высота вычисляется по этой формуле в три арифметических действия. Но возможна и обратная задача: известна высота, с которой тело уронили, и нужно выяснить, через какое время произойдёт его встреча с землёй. (Для парашютиста, совершающего затяжной прыжок, то есть прыжок с долго не раскрываемым парашютом, это более чем важная информация.)
В такой постановке задачи записанная выше формула представляет собой квадратное уравнение относительно неизвестной t. Пусть, например, тело падает с высоты 25 м (приблизительно, с 10-го этажа). Тогда уравнение для времени падения приводится к виду:
t^2 = 5
Разумеется, Вы скажете мне, что решение такого "простого" уравнения получают извлечением корня квадратного. На первый взгляд, это легко. Ведь каждый знает на память, чему равен корень из числа 4 или корень из числа 9.
Так то оно, конечно, так. Но в школьном учебнике не сказано, чему равен корень из числа 5. Только не говорите мне, что достаточно нажать нужную кнопку на компьютере или калькуляторе и готово! Это неправда, потому что Вы ещё не составили для этих электронных устройств программу! Ну и что, что кто-то другой составил? Ведь не Вы же.
А когда сами начнёте составлять - сразу задумаетесь о том, какие простейшие
арифметические действия нужно выполнять для решения этой задачи. В этом и состоит проблема обратных операций. Как выполнять вычитание, если умеем выполнять лишь сложение? Как делить, если умеем только умножать?
Не отчаивайтесь. Снова обратимся к уравнению:
t^2 = 5
Из него видно, что время падения t - это такое число, что если оно вдруг окажется в наших руках, и мы возведём его в квадрат (то есть, умножим само на себя), то получится точно 5.
Таким образом, как опознать искомое число - ясно. Проблема лишь в том, чтобы это число как-то у нас в руках оказалось.
Ответ, конечно, можно искать, беспорядочно тыча пальцем в разные числа и возводя их в квадрат. Но чисел бесконечно много, и шансов случайно попасть пальцем в нужное число меньше, чем шансов найти иголку в стоге сена.
Тогда не будем полагаться на случайность. Составим упорядоченный по возрастанию список чисел. Пусть, вначале, это будут целые неотрицательные числа:
0; 1; 2; 3; 4; ...
Учиним их проверку. Будем по порядку брать каждое число из списка, возводить в квадрат, и сравнивать результат с числом 5. Это как проверка при стрельбе из пушки: недолёт или перелёт.
0^2 = 0 (результат меньше 5-ти) - слишком мало;
1^2 = 1 (результат меньше 5-ти) - слишком мало;
2^2 = 4 (результат меньше 5-ти) - слишком мало;
3^2 = 9 (результат больше 5-ти) - чересчур много!
Проверять остальные целые числа из списка не имеет смысла. Ясно, что среди целых чисел искомого числа нет. Выходит, искомое число – дробное. И очевидно, что расположено оно где-то между числами 2 и 3.
Тогда разделим интервал между числами 2 и 3 на десять частей. (Не знаю, почему, но хочется именно на десять.) И, соответственно, создадим другой упорядоченный список чисел: положительные дробные числа от 2 до 3 с одним знаком после запятой:
2,0; 2,1; 2,2; 2,3; . . . 2,9; 3,0.
Проверка чисел из списка:
2,0^2 = 4,00 (результат меньше 5-ти) - слишком мало;
2,1^2 = 4,41 (результат меньше 5-ти) - слишком мало;
2,2^2 = 4,84 (результат меньше 5-ти) - слишком мало;
2,3^2 = 5,29 (результат больше 5-ти) - чересчур много!
Ну вот, уже ясно, что искомое число лежит где-то в интервале от 2,2 до 2,3. Мы заметно уточнили ответ.
Теперь следует остановиться и подумать, получили ли мы решение задачи с достаточной точностью? Мы уже узнали, что упавшее с высоты 25 метров тело будет лететь до земли больше, чем 2,2 секунды, но меньше, чем 2,3 секунды. Ответ не вполне определённый, но если неточность в одну десятую долю секунды для нас приемлема, то можно на этом и остановиться. Если же ответ нужен с точностью в одну сотую долю секунды, придётся строить ещё один список чисел: список чисел с двумя знаками после запятой.
В общем, нетрудно заметить, что в этом алгоритме поиска циклически повторяются одни и те же действия: перемещение по списку, возведение числа в квадрат, сравнение пары чисел между собой. Но очевидно, что этот алгоритм предназначен всё же для человека, а не для компьютера. Человек приучен к десятичным числам, и поэтому мы делили интервал поиска именно на десять частей.
В компьютере внутреннее представление чисел - двоичное, и алгоритм поиска выгоднее строить иначе: последовательно делить интервал между числами не на десять частей, а на две (пополам). Такой поиск в информатике называют дихотомическим ("дихотомия" [греч.] - рассечение надвое).
Разумеется, многим из людей поиск корня квадратного среди роя чисел покажется задачей слишком скучной. Могу предложить другую задачу: аналогичную, но более занимательную, похожую на интерактивную игру во "взломщика".
Компьютерная игра "Поиск в камере хранения"
Вы - взломщик, и проникли в тайную камеру хранения, состоящую из 512 пронумерованных ячеек. В ячейках хранятся карточки с записанными на них секретными числами. В каждой ячейке - по одной карточке. Вам известно, что числа на карточках не повторяются и не идут подряд: возможны пропуски в последовательности чисел. И ещё Вам известно, что с возрастанием номеров ячеек секретные числа на карточках возрастают.
Разумеется, каждая ячейка камеры хранения закрыта на замок.
С помощью своего "хакерского" компьютера Вы, к сожалению, не можете открыть все ячейки разом: завоет сирена тревоги. Зато Вы можете открывать их поодиночке, набирая на своём компьютере порядковый номер произвольной интересующей Вас ячейки.
Располагая таким скромным инструментом взлома, постарайтесь за наименьшее количество попыток (долго возиться - опасно) выяснить, имеется ли в камере хранения карточка с числом 217. (Её там попросту может не быть.) Если имеется, надо записать в "хакерский" блокнот порядковый номер ячейки, в которой Вы эту карточку нашли. Этот номер и число 217 - вместе составляют ключ для доступа к фотографии секретного агента, которую Вы очень хотите увидеть.
Доступ к фотографии секретного агента
Станция "Сортировочная"
Рассмотрим пример алгоритма, в котором действия по обработке элементов
данных очень просты. Но вот количество обрабатываемых элементов может быть очень велико. Речь пойдёт о задаче сортировки списка.
Список – это хранимая на бумаге или в памяти компьютера последовательность объектов. Например, список фамилий постояльцев гостиницы, с указанием даты заселения:
25.09.2015 Сидоров
27.09.2015 Петров
29.09.2015 Иванов
02.03.2016 Фролов
Подобный список естественным путем возникает, если администратор гостиницы добросовестно регистрируют постояльцев в специальном журнале. Ясно, что иногда может возникнуть необходимость поискать в этом списке нужную запись.
Пока список не очень велик, задача поиска нужной записи решается просмотром всего списка человеком. Если же список содержит большое количество записей (например, сотни тысяч или миллионы), задача становится слишком трудоемкой для человека, и ее лучше поручить компьютеру. Несмотря на свое название (английское слово «компьютер» переводится как «вычислитель»), большинство компьютеров в мире занимаются не столько вычислениями, сколько именно работой со списками.
Трудоемкость поиска нужной записи в списке, конечно, зависит от того, упорядочен ли список по какому-нибудь признаку. В приведенном выше примере список постояльцев упорядочен по дате заселения. Поэтому фамилию постояльца, который заселился в известный день, найти легко.
Если искать нужную запись требуется не по дате заселения, а по фамилии постояльца, то и упорядочение списка лучше произвести по фамилии, по алфавиту.
Для упорядочения списка по алфавиту необходимо условиться о том, как сравнивать две произвольные фамилии, то есть ввести правило для использования знаков «больше» (>) и «меньше» (<) применительно к буквам.
Это нетрудно, если буквы алфавита пронумерованы, то есть имеют числовые коды. При сравнении фамилий сравниваются коды их первой буквы. Если первая буква двух фамилий одинакова, сравниваются вторые буквы, если и они одинаковы – третьи и т.д. Согласно этому правилу можно считать, что Петров «больше», чем Иванов, а Сидоров «меньше», чем Фролов (даже если высоченный Сидоров и невысокий Фролов думают иначе).
Упорядочение первоначально неупорядоченного списка иногда называют сортировкой. Ею и займемся.
Человек, видя весь список целиком (если список небольшой), выполняет сортировку довольно легко. Компьютер "по-человечески" сделать это не может, так как он не видит весь список сразу. Центральный процессор за один приём может сравнить только два числа. То есть "зрение" у компьютера, по-сравнеию с человеком, сужено до двух элементов списка, и для него приходится придумывать специальные алгоритмы, учитывающие ограниченность его способностей.
Рассмотрим, для примера, один из сугубо "компьютерных" алгоритмов сортировки: не самый быстрый из них, зато очень простой. Этот алгоритм получил название "пузырьковый", так как в нем по мере сортировки "тяжёлые" элементы списка опускаются вниз, а "легкие" - всплывают вверх, как пузырьки углекислого газа в стаканчике с газировкой. (У Вас, возможно, появилось желание немедленно сбегать за газировкой, но прежде давайте рассмотрим алгоритм.)
В этом алгоритме компьютер последовательно проходит по списку, сравнивая каждые два соседних элемента. Если они неупорядоченв между собой, он переставляет их друг с другом местами. Факт обмена элементов местами запоминается компьютером в специально отведённой для этого ячейке памяти.
За одно прохождение по списку, обычно, достичь его полного упорядочения не удаётся. Может понадобиться несколько последовательных прохождений.
О том, что список, наконец-то, упорядочен, компьютер "догадывается", если при очередном прохождении всего списка ни разу не потребовалось менять элементы местами.
Внимательно, шаг за шагом проследить за работой компьютера по этому алгоритму можно с помощью автомата для пузырьковой сортировки списка.
Вы можете "вручную" опробовать все алгоритмы из пройденных тем, чтобы ощутить, каково это: быть компьютером. Для этого нужно просто выполнить практическую работу.