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

Уфимский государственный нефтяной технический университет

АЛГОРИТМИЗАЦИЯ

И

ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ

VISUAL BASIC

(Лекции)

Стерлитамак

Основы алгоритмизации и объектно-ориентированного программирования

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

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

Слово “алгоритм” происходит от “algorithmi” – латинской формы написания имени выдающегося математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических операций.

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

Пример 1. Составим алгоритм решения квадратного уравнения :

1. Пусть a=1; b=5; c=4
2. Вычислить d=b-4ac
3. Сравнить d с нулем. Если d<0 перейти к пункту 4. В противном случае вычислить , .
4. Прекратить вычисления.

Пример 2. Пользователю необходимо произвести редактирование текста. Исходное состояние: фрагмент текста “информационная модель”, курсор находится перед первым символом. Необходимо перевести его в конечное состояние: “модель информационная”, курсор находится после последнего символа.

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

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

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

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

К алгоритму предъявляются следующие требования:

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

2. Алгоритм должен быть понятен исполнителю. Каждое правило алгоритма должно быть четким, однозначным, выполнение алгоритма носит механический характер – это свойство алгоритма называется определенностью.

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

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

5. Алгоритм решения задачи разрабатывается в общем виде так, чтобы его можно было применить к решению данного класса задач, различающихся лишь исходными данными. Например, в алгоритме решения квадратного уравнения значения a,b,c можно поменять и решить другое уравнение. Это свойство алгоритма называется массовостью.

Алгоритм можно фиксировать несколькими способами:

1. На естественном языке, как был написан алгоритм решения квадратного уравнения.

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

3. На специальном языке.

Специальные языки – алгоритмические языки, близки к естественному, но имеют жесткие правила, которые должен понимать компьютер. Алгоритм, записанный на специальном языке, понятном компьютеру, называется программой. Компьютер понимает только машинные команды, то есть набор нулей и единиц. На заре компьютерной эры ( 50-е годы XX века) программы писались на машинном языке и представляли собой очень длинные последовательности нулей и единиц, такие языки программирования назывались языками низкого уровня, языком программирования низкого уровня (близким к машинному) является Assembler. Достоинством языков низкого уровня является то, что с их помощью создаются самые эффективные программы (краткие и быстрые), обычно их применяют для написания программ-драйверов устройств, но их очень трудно изучить, ведь для каждого типа процессора свой язык Assembler. В 60-70 годах для облегчения труда программистов начали создаваться языки программирования высокого уровня ( более понятные человеку, чем компьютеру), формальные языки, кодирующие алгоритмы в виде предложений. Они строились на основе использования определенных инструкций (операторов), жестко определенного списка ключевых слов и строгих правил построения предложений (синтаксиса). Для того чтобы реализовать эти правила и практически получить результаты программы на компьютере, создавалась специальная программа – транслятор, которая переводила программу с алгоритмического языка в машинный код. По принципу действия различают два вида трансляторов: компиляторы и интерпретаторы. Интерпретаторы работают как синхронные переводчики: берут один оператор из программы, транслируют его в машинный код и исполняют, лишь только после того, как исполнение прошло успешно, интерпретатор берет следующий оператор. Если какой-то оператор многократно используется в программе, интерпретатор будет добросовестно выполнять его перевод так, как будто встретил его впервые. Компиляторы обрабатывают программу в несколько приемов. Сначала они несколько раз просматривают исходный текст (исходный код), находят общие места, выполняют проверку на наличие синтаксических ошибок и противоречий, а лишь потом переводят программу в машинный код. Программа получается компактной и эффективной. Если программа написана на интерпретируемом языке программирования, то ее можно выполнить лишь на том компьютере, на котором установлен данный интерпретатор, программы, написанные на компилируемых языках программирования, работают на любом компьютере и делают это в сотни раз быстрее. Наиболее широко распространенным типом языков программирования высокого уровня являются процедурные языки. Одним из первых процедурных языков был Бейсик (Basic), созданный в 1964 году. Далее появились QBasic, Pascal, C++. В настоящее время наибольшей популярностью пользуются системы объектно-ориентированного визуального программирования Microsoft Visual Basic (VB), Borland Delphi, Borland C и т.д.). Для создания приложений в среде Windows&Office используется язык программирования Visual Basic for Applications (VBA).