Алгоритм

Учебные вопросы

1. Понятие Алгоритма

Ø Понятие графа

Ø Блок-схема алгоритма

2. Понятие программирования.

Ø Языки программирования.

Ø Язык написания процедур (.bat – файлов)

- @echo [on|off]

- метка;

- Goto;

- pause;

- MenuItem;

- перенаправление вывода «>», «>>»

- Call;

- Choice;

- Copy;

- Delete;

- цикл if

- выбор For;

3.

Оглавление

Учебные вопросы........................................................................................................................ 2

Алгоритм......................................................................................................................................... 3

Программа.............................................................................................................................. 5

Алфавит................................................................................................................................... 6

Блок-схема алгоритма.................................................................................................................. 6

Граф.............................................................................................................................................. 6

Блок-схема алгоритма......................................................................................................... 7

Программирование....................................................................................................................... 8

Создание простейших *.bat файлов в операционной системе DOS............................... 8

Команды, используемые при создании *.bat файлов................................................... 8

Содержание понятия "алгоритм" можно определить следующим образом.

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

Алгоритмы возникли вместе с появлением математики. Школьный курс математики предлагает большой выбор алгоритмов: алгоритмы сложения и умножения "столбиком", деления "углом", приведения дробей к общему знаменателю, построения биссектрисы угла и т. д. В высшей математике алгоритмов еще больше, причем наряду с численными алгоритмами (решение дифференциальных уравнений, задач математического программирования и др.) появляются алгоритмы над нечисловыми объектами {логическими выражениями, последовательностями произвольных символов, графами и т. п.).

Алгоритм — это точная инструкция, а инструкции встречаются практически во всех областях человеческой деятельности. Возможны алгоритмы проведения физического эксперимента, сборки шкафа или телевизора, обработки детали. Однако не всякая инструкция есть алгоритм. Инструкция становится алгоритмом только тогда, когда она удовлетворяет определенным требованиям. Эти требования частично сформулированы в начале статьи, хотя упомянутые в определении понятия однозначности и элементарности сами нуждаются в уточнении. Алгоритм однозначен, если при применении к одним и тем же данным он дает один и тот же результат. Но как по описанию алгоритма определить, однозначен он или нет? В каком случае шаги считаются элементарными?

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

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

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

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

1. Всякий алгоритм применяется к исходным (входным) данным и выдает результаты (выходные данные). Кроме того, в ходе работы алгоритма появляются различные промежуточные данные. Поэтому должны быть указаны виды данных, с которыми могут работать алгоритмы. Для описания данных, во-первых, фиксируется набор элементарных символов (алфавит данных) и, во-вторых, даются правила построения сложных данных из простых. Примеры простых данных: целые и действительные числа, логические переменные, символьные переменные. Примеры сложных данных: массивы чисел, изображения на экране ЭВМ.

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

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

4. Последовательность шагов алгоритма должна быть однозначной. Не допускается произвола при выборе очередного шага алгоритма. Обязательно должны быть зафиксированы начальный и заключительный шаги алгоритма.

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

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

6. Всякая алгоритмическая модель предполагает некоторый механизм исполнения алгоритмов, который обеспечивает доступ к ячейкам памяти, а также имеет средства для выполнения всех элементарных действий и управления процессом вычисления (т. е. пуском, остановкой и соблюдением нужной последовательности действий). Физическая реализация этого механизма (электронная, механическая или какая-либо другая) с алгоритмической точки зрения несущественна, хотя, разумеется, от нее зависят такие важные показатели, как скорость реализации алгоритма, надежность и т. д. Речь идет лишь о функциональной схеме механизма. В машинных моделях он описан непосредственно (машина и есть такой механизм). Для языковой модели путь от описания к реализации лежит через транслятор — специальную программу, которая перерабатывает текст на алгоритмическом языке в последовательность машинных команд. В роли исполнителя алгоритма может выступать и человек.

Как видим, для того чтобы набор инструкций можно было назвать алгоритмом, он должен удовлетворять многим достаточно жестким требованиям. Поэтому при описаниях алгоритмов, предназначенных для передачи другому человеку (например, в научных публикациях или при постановках задач), эти требования в полном объеме, как правило, не соблюдаются. Последствия такого несоблюдения могут быть различными. В одних случаях их выполнение связано лишь с некоторой рутинной работой, требующей профессиональных навыков и времени. Такие описания воспринимаются однозначно и в уточнениях нуждаются только тогда, когда дело доходит до программирования. В других случаях процесс уточнения может привести к полной переделке исходного текста. Короче говоря, путь от полуалгоритмического описания, имеющего лишь некоторые черты алгоритма, до настоящего алгоритма (который, как правило, имеет вид программы) может быть трудным. Пройти его — задача программиста. Однако, если в исходном описании есть неоднозначности, программисту может потребоваться помощь автора предлагаемой процедуры. Чтобы пояснить, о чем идет речь, рассмотрим простой пример.

Дано: последовательность чисел.

Требуется: найти в этой последовательности максимальное число.

Метод решения:

1. В некоторой памяти М запоминаем первое число.

2. Следующее число последовательности сравниваем с числом, лежащим в М. Записываем в М большее из этих чисел (т.е. либо сохраняем в М прежнее число — если оно больше, — либо записываем вместо него следующее).

3. Повторяем шаг 2 до конца данной последовательности.

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

Вопросы к постановке задачи:

а) Каково представление чисел, т. е. представлены ли они целыми числами, десятичными дробями (действительными числами), простыми дробями или арифметическими выражениями типа 2 + Ö`7 Непосредственно можно сравнивать только целые или действительные числа. Поэтому если в исходной последовательности встречаются арифметические выражения <а простые дроби — это тоже арифметические выражения, содержащие только операцию деления), то их сравнению должно предшествовать их вычисление, т. е. к предлагаемому алгоритму добавится еще ряд шагов.

б) Что значит "найти максимальное число" — просто дать его значение или, кроме того, указать еще и его место в последовательности? Предлагаемый метод решения дает только значение. Если нужно указывать место числа, то числа последовательности нужно как-то нумеровать или именовать, а метод решения изменить. Кроме того, как быть, если найдено несколько одинаковых максимальных чисел — указывать все их места или, например, первое по порядку?

Ответы на эти вопросы неоднозначны. Дать их может только тот, кто ставит задачу. Предположим, что в нашем случае ответы таковы: числа — целые

Дата добавления: 2014-01-11