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

Алгоритм и его свойства. Алгоритмы могут описывать процессы преобразования самых разных объектов. Широкое распространение получили вычислительные алгоритмы, ко­торые описывают преобразование числовых данных. Само слово «алгоритм» происходит от algorithmi — латинской формы написания имени выдающегося математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических операций.

Алгоритм - это строго детерминированная после­довательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных ис­полнителю команд.

Выберем в качестве объекта текст и построим алгоритм, описывающий процесс его редактирования.

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

Алгоритмы состоят из отдельных команд, которые испол­нитель выполняет одну за другой в определенной последова­тельности. Разделение информационного процесса в алго­
ритме на отдельные команды является важным свойством алгоритма и называется дискретностью.

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

Каждый исполнитель обладает определенным набором, системой команд, которые он может выполнить. Алгоритм должен быть понятен исполнителю, то есть должен содер­жать только те команды, которые входят в систему его команд.

В процессе редактирования текста возможны различные операции: удаление, копирование, перемещение или замена его фрагментов. Исполнитель редактирования текста дол­жен быть в состоянии выполнить эти операции.

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

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

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

формальное выполнение алгоритма. Алгоритм позволяет формализовать выполнение информационного процесса. Если исполнителем является человек, то он может выпол­нять алгоритм формально, не вникая в содержание постав­ленной задачи, а только строго выполняя последователь­ность действий, предусмотренную алгоритмом.

Рассмотрим работу пользователя, например, в среде тек­стового редактора Word. Word предоставляет пользователю возможность работы в мире своих объектов, которыми явля­ются документ, фрагмент документа, символ и так далее.

Предположим, что пользователю необходимо провести ре­дактирование текста. Пусть у нас есть объект — фрагмент. Надо перевести его из исходного состояния (содержание фрагмента — текст «информационная модель», курсор нахо­дится перед первым символом) в конечное состояние (текст «модель информационная», курсор находится после послед­него символа) — рис. 4.1.

' ¹ ' ² ' ³ ' | модель информационна^

ли

Рис. 4.1. Начальное и конечное состояния объекта

Необходимую для реализации такого преобразования по­следовательность действий, то есть алгоритм, запишем на естественном языке, который понятен пользователю компьютера:

1. Выделить слово «информационная» + пробел.

2. Вырезать этот фрагмент и поместить его в буфер обмена.

3. Установить курсор на позицию после слова «модель» + пробел.

4. Вставить вырезанный фрагмент текста.

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

Наш текст состоит из одной страницы, которая содержит одну строку. Команде Выделить слово «информационная» + пробел на формальном языке соответствует команда Выде­лить символы с 1 по 15, а команде Установить курсор после слова «модель» + пробел соответствует команда Установить курсор после 7-го символа.

1. Выделить символы с 1 по 15.

2. Вырезать этот фрагмент и поместить его в буфер обмена.

3. Установить курсор на позицию после 7-го символа.

4. Вставить вырезанный фрагмент текста.

щ Реаактиро«&ни».(*ос

Теперь этот алгоритм «Редактирование» пользователь может выполнять формально. В процессе выполнения алго­ритма на компьютере пользователь будет выполнять коман­ды алгоритма с помощью клавиатуры и мыши. Фактически же пользователь будет давать команды объектам програм­мной среды Windows&Office, которые будут действительны­ми исполнителями алгоритма.

Компьютер — автоматический исполнитель алгоритмов.

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

Алгоритм, записанный на «понятном» компьютеру языке программирования, называется програм­мой.

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

На заре компьютерной эры, в 50-е годы XX века, про­граммы писались на машинном языке и представляли собой очень длинные последовательности нулей и единиц. Состав­ление и отладка таких программ было чрезвычайно трудо­емким делом.

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

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

Одним из первых процедурных языков программирова­ния был известный всем Бейсик (Basic), созданный в 1964 году. В течение последующего времени Бейсик разви­вался, появлялись его различные версии (MSX-Basic, Бей­сик-Агат, QBasic и др.). Другим широко распространенным языком программирования алгоритмического типа является Pascal.

В настоящее время наибольшей популярностью пользуют­ся системы объектно-ориентированного визуального програм­мирования Microsoft Visual Basic и Borland Delphi. Для создания приложений в среде Windows&Office используется язык про­граммирования Visual Basic for Applications (VBA).

Вопросы для размышления

1. Какие из нижеперечисленных правил являются алгоритмами? Ответ обоснуйте:

• орфографические правила;

• правила выполнения арифметических операций;

• правила техники безопасности;

• правила перевода чисел из одной системы счисления в дру­гую.

2. В чем состоит различие между естественными языками и языка­ми программирования?

Задания

4.1. Составьте алгоритм преобразования слова «информатика» в слово «форма».