ВУЗ:
4. АЛГОРИТМЫ
Во второй главе уже отмечалось, что прежде чем машина сможет выполнить какую-либо задачу, ей нужно дать алго-
ритм (algorithm), точно описывающий, что делать. Поэтому наука об алгоритмах является краеугольным камнем вычисли-
тельной техники. В этой главе мы рассмотрим базовые понятия науки об алгоритмах, включая вопросы разработки и пред-
ставления алгоритмов, а также понятия итерации и рекурсии. Мы также опишем известные алгоритмы поиска и сортировки.
4.1. ПОНЯТИЕ АЛГОРИТМА
Понятие алгоритма неформально можно определить как последовательность этапов, описывающую способ решения по-
ставленной задачи. В данном разделе мы рассмотрим это основополагающее понятие более детально. Вначале подчеркнем
различие между алгоритмом и его представлением, что аналогично различию между сюжетом и книгой. Сюжет абстрактен
или концептуален по своей природе, а книга является его физическим представлением. Если книгу перевести на другой язык
или опубликовать в другом формате, изменится только представление сюжета, сам по себе сюжет останется прежним.
Точно так же алгоритм является абстракцией и отличается от своего конкретного представления. Существует много
способов представления одного и того же алгоритма. Например, алгоритм для перевода показаний температуры по шкале
Цельсия в показания по шкале Фаренгейта традиционно представляется в виде алгебраической формулы
F = (9/5)С + 32.
Однако его можно представить и в виде инструкции: умножить значение температуры в градусах Цельсия на 9/5, а за-
тем к полученному произведению прибавить 32.
Эту последовательность действий можно представить даже в виде электронной схемы. В каждом случае лежащий в ос-
нове алгоритм остается прежним, отличаются только методы его представления.
В контексте обсуждения различий между алгоритмами и их представлениями следует также прояснить различие между
двумя другими, связанными с ними понятиями: программами и процессами. Программа является представлением алгоритма.
По сути, специалисты в области компьютерных наук используют термин "программа" по отношению к формальному пред-
ставлению алгоритма, разработанного для некоторого компьютерного приложения. В главе 3 мы определили процесс как
деятельность, связанную с выполнением программы. Однако следует заметить, что выполнить программу – означает также и
выполнить
Рис. 4.1. Определение алгоритма
алгоритм, представленный этой программой; поэтому процесс можно эквивалентно определить как деятельность по выпол-
нению алгоритма. Из сказанного можно сделать заключение, что процессы, алгоритмы и программы – это различные, хотя и
взаимосвязанные понятия.
Рассмотрим теперь формальное определение алгоритма, приведенное на рис. 4.1. Требование упорядоченности этапов
алгоритма указывает, что отдельные этапы алгоритма должны составлять четко определенную структуру в смысле порядка
их выполнения. Однако это не означает, что этапы должны выполняться в строгой последовательности: первый, второй и т.д.
Например, некоторые алгоритмы, называемые параллельными, содержат больше одной последовательности этапов, каждая
из которых разработана так, что может выполняться отдельным процессором многопроцессорной машины. В таких случаях
алгоритм в целом не представляет собой единую последовательность этапов, соответствующую сценарию "первый этап,
второй этап". Он содержит множество последовательностей, которые разветвляются и вновь объединяются, по мере того как
разные процессоры выполняют различные части задачи. Другими примерами могут служить алгоритмы, выполняемые таки-
ми электронными схемами, как триггеры (см. раздел 1.1), в которых каждый вентиль реализует отдельный этап всего алгоритма.
В этом случае этапы упорядочены как причина и следствие, так как действие каждого вентиля распространяется на всю схему.
Теперь рассмотрим требование, по которому алгоритм должен состоять из выполнимых этапов. Чтобы оценить важ-
ность этого условия, рассмотрим последовательность инструкций.
Этап 1. Составить список всех целых положительных чисел.
Этап 2. Упорядочить этот список в убывающем порядке (от большего значения к меньшему).
Этап 3. Выбрать первое число из отсортированного списка.
Этот набор инструкций не является алгоритмом, так как этапы 1 и 2 выполнить невозможно. Никто не в состоянии соста-
вить список всех целых положительных чисел, и целые положительные числа невозможно упорядочить, начиная с "наи-
большего". Для понятия "выполнимый" специалисты в области компьютерных наук используют термин "эффективный". Та-
ким образом, если говорится, что данный этап эффективен, то, значит, он осуществим.
Еще одним требованием, налагаемым определением, приведенным на рис. 4.1, является недвусмысленность этапов ал-
горитма. Это означает, что во время выполнения алгоритма, при любом состоянии процесса, информации должно быть дос-
таточно, чтобы полностью и однозначно определить действия, которые требуется осуществить на каждом его этапе. Другими
словами, выполнение любого этапа алгоритма не потребует каких-либо творческих способностей. Наоборот, единственное требо-
вание состоит в способности следовать имеющимся инструкциям.
При обсуждении проблемы неоднозначности важно различать алгоритм и его представление. Неоднозначность кон-
кретного представления алгоритма часто неправильно интерпретируется как неоднозначность, присущая самому алгоритму.
Распространенным примером является степень детализации в описании алгоритма. Для метеорологов инструкция "Перевес-
ти показания в градусах Цельсия в эквивалентные им показания по шкале Фаренгейта" будет вполне удовлетворительной, но
Алгоритм – это упорядоченный набор из недвусмысленных и
выполнимых этапов, определяющий некоторый конечный процесс.
Страницы
- « первая
- ‹ предыдущая
- …
- 76
- 77
- 78
- 79
- 80
- …
- следующая ›
- последняя »
