Вводные рассуждения

Лекция 4. Развитие понятия алгоритма

Первоначальное понятие Алгоритма было сформулировано для наиболее абстрактного Исполнителя. Т.е. понятие Алгоритма было инвариантно относительно архитектуры Исполнителя (системы команд, организации памяти, принципов работы процессора) и языка программирования, на котором алгоритм был бы сформулирован.

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

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

Новые возможности ЭВМ должны эффективно использоваться. Это становится возможным:

- при изменении языков общения программиста с ЭВМЖ

- при появлении новых подходов к программированию.

П. 2 Три варианта понятия Алгоритма

1. Классический Алгоритм.

2. Объектно-ориентированный Алгоритм.

3. Распределённый Алгоритм.

1. Классическое понятие Алгоритма связано со словом ОДИН.

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

Программа разворачивает решение задачи в последовательность шагов вычислителя, но эта последовательность никак не связана с реальным (астрономическим) временем. Считается, что вычисления происходят в дискретные моменты 1, 2, 3…
Важным свойством Алгоритма является воспроизводимость или повторяемость результатов при повторном выполнении.
В результате выполнения каждого шага получается новый набор значений, называемых «промежуточными», при этом ранее полученные наборы значений не используются.
На выполнение шага требуется какое-то время, но само изменение значений происходит мгновенно в начале или в конце шага.
В процессе выполнения шага нечего не происходит из того, что могло бы повлиять на результат – на промежуточные значения.
В паре «алгоритм – данные» Алгоритм является главным. Алгоритм обрабатывает (управляя Исполнителем) Данными и они являются окончательным продуктом. Классическая формула степени важности:
Алгоритм >>Данные. Очень много научных работ посвящено Алгоритмам и относительно мало теории типов Данных.

2. Объектно-ориентированное понятие алгоритма связано с понятие СТРУКТУРА.
В ОПП всё сделано «поставлено с ног на голову»:
- в классическом алгоритме ДАННЫЕ определяются внутри алгоритма,
- в ОПП алгоритмы (методы) сделались частью СТРУКТУР данных (объектов).
ОПП ближе к мировосприятию человека: объекты – дома, автомобили, людей мы видим повсюду, а алгоритмов не видим нигде.
Эти объекты характеризуются различными параметрами (свойствами): адресами, высотой, скоростью.
Эти объекты могут совершать какие-то действия (реализовать свои методы). При этом классическое понятие Алгоритма не утратило своей значимости. Как базовые элементы (строительные кирпичики) алгоритм остаётся в ОПП в виде методов.

Эти объекты можно создавать, перестраивать, уничтожать, провоцировать (инициировать) их на какие-то действия.

Все понятия ОПП связаны с понятием СТРУКТУРА.
Строение объекта – структура.

Иерархия объектов со свойством наследования – структура.

Разделение переменных на локальные и глобальные, разделение входов-выходов (инкапсуляция) – структура.

ОПП характеризуется формулой АЛГОРИТМ=ДАННЫЕ.

Возникают новые программные продукты:

- операционные системы, которые никогда не должны останавливаться,

- системы реального времени,

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

Технологическая особенность ООП: Исполнитель в ОПП открыт для взаимодействия с внешним миром – он содержит входы, через которые может получать сообщения (даже не связанные с исполняемой программой) и обязан реагировать на них.

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

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

3. Понятие распределенного алгоритма связано со словами МНОГО, БОЛЬШОЙ, СТРУКТУРА.

С развитием информатизации произошли следующие изменения:

- если на первых порах развития вычислительной техники у каждой из 10 тысяч программ было по несколько десятков пользователей, то сейчас на каждую из десяти наиболее популярных программ приходятся десятки миллионов пользователей. Как следствие в массовом сознании понятие ЭВМ вытиснилось понятием IBM PC, а операционная система – словом Windows.

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

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

Проблемы данных, их представления, типов данных становятся более серьезными, чем проблемы алгоритмов, во многом уже исследованные. Среди всех типов данных на первый план выходит самый большой – файловый. Появляются все многочисленные новые форматы файлов. Структурированность данных вышла на мегауровень: большинство данных объединилось в одну единственную суперструктуру – WWW. Появляется термин добыча данных data mining.

Даже на уровне отдельного (stand-alone) исполнителя давно уже утрачена строгая последовательность выполнения шагов алгоритма.

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

Многие свойства, сформулированные для классического алгоритма, видоизменяются, появляются новые свойства алгоритмов.

Детерминированность сохраняется на уровне локального исполнителя. НО когда программа исполняется множеством компьютеров, объединенных в сеть, нет никаких гарантий получения одного и того же результата.

Финитность алгоритма становится не внутренним его свойством, говорящим, что через некоторое число шагов он остановится, а внешним – способностью остановиться по команде из вне.

Новые свойства:

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

Масштабируемость: свойство близкое к переносимости – возможность исполнения программы на различных ресурсах исполнителя с мало меняющимися показателями эффективности.
Например, для ресурсов, различающихся количеством процессоров, произведение времени исполнения на количество процессоров должно быть приблизительно const.
Если ресурс память, то масштабируемая программа должна уметь использовать всю предоставляемую ей память. При этом время выполнения программы должно быть прямо пропорционально объему предоставляемой памяти.

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

Эффективная распараллеливаемость или многопоточность – необходимое свойство.

Таким образом, можно следующим образом представить эволюцию алгоритмов:

- программы, полностью владеющие данными, с которыми они работают,

- программы, разделяющие данные с другими программами (САПР). При этом структура данных строго определена, хотя объем данных может меняться.

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

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