Автор: Пользователь скрыл имя, 20 Августа 2011 в 18:52, реферат
"Алгоритм" является фундаментальным понятием информатики. Представление о нем необходимо для эффективного применения вычислительной техники к решению практических задач. Алгоритм - это предписание исполнителю (человеку или автомату) выполнить точно определенную последовательность действий, направленных на достижение заданной цели. Алгоритм - это сформулированное на некотором языке правило, указывающее на действия, последовательное выполнение которых приводит от исходных данных к искомому результату.
"Алгоритм" является
фундаментальным понятием
Свойства алгоритма (отличающие его от
любых других предписаний): понятность
(для конкретного исполнителя); дискретность
(команды последовательны, с точной фиксацией
моментов начала и конца выполнения команды);
точность (после выполнения каждой команды
точно известно, завершено ли исполнение
алгоритма или же какая команда должна
выполниться следующей); результативность
(после конечного числа шагов задача решается
или же становится ясно, что процесс решения
не может быть продолжен): массовость (алгоритм
единым образом применяется к любой конкретной
формулировке задачи, для которой он разработан).
1. Дискретность - разбиение алгоритма
на ряд отдельных законченных действий
- шагов. Выполнение алгоритма разбивается
на последовательность законченных действий
- шагов. Каждое действие должно быть закончено
исполнителем алгоритма прежде, чем он
приступит к исполнению следующего действия.
2. Точность - однозначные указания. На
каждом шаге однозначно определено преобразование
объектов среды исполнителя, полученной
на предыдущих шагах алгоритма. Если алгоритм
многократно применяется к одному и тому
же набору исходных данных, то на выходе
он получает каждый раз один и тот же результат.
Запись алгоритма должна быть такой, чтобы
на каждом шаге его выполнения было известно,
какую команду надо выполнять следующей.
3. Понятность - однозначное понимание
и исполнение каждого шага алгоритма его
исполнителем. Алгоритм должен быть записан
на понятном для исполнителя языке.
4. Результативность - обязательное получение
результата за конечное число шагов. Каждый
шаг (и алгоритм в целом) после своего завершения
дает среду, в которой все объекты однозначно
определены. Если это по каким-либо причинам
невозможно, то алгоритм должен сообщать,
что решение задачи не существует. Работа
алгоритма должна быть завершена за конечное
число шагов. Информатика оперирует только
с конечными объектами и конечными процессами,
поэтому вопрос о рассмотрении бесконечных
алгоритмов остается за рамками теории
алгоритмов. 5. Массовость - применение
алгоритма к решению целого класса однотипных
задач.
Система команд исполнителя - точно описанная
обстановка, включающая формулировку
решаемой задачи, перечень объектов, вовлекаемых
в условие задачи и в ее решение, и возможности
исполнителя: свойства объектов, которые
он может узнать и действия, которые он
может совершить. Формальное исполнение
алгоритма производит компилятор или
интерпретатор, проверяя семантику.
Способы записи алгоритма
На практике наиболее
распространенными являются следующие
формы записи алгоритмов:
1) графическая запись (блок-схемы);
2) словесная запись (псевдокоды);
3) язык программирования.
Язык, используемый
для формальной записи алгоритмов,
называется алгоритмическим языком.
При описании любого языка (в том
числе естественного, например, русского,
английского и т.д.) используются
следующие понятия: алфавит, синтаксис
и семантика.
Алфавит языка - это множество простейших
знаков, которые могут быть использованы
в текстах этого языка. Последовательность
символов алфавита называют словом. Правила,
согласно которым образуются слова из
алфавита, называются грамматикой. Сам
же язык - это множество всех слов, записываемых
в данном алфавите согласно данной грамматике.
Синтаксис - это набор правил, определяющих
возможные сочетания (конструкции) из
букв алфавита. Для описания синтаксиса
языка, как правило, используют другой
язык (метаязык) или синтаксические диаграммы.
Семантика - это набор правил, определяющих
значение (смысл) отдельных конструкций
языка.
Одним из самых распространенных алгоритмических
языков является язык Pascal, который полезен
как для начинающих, так и для опытных
программистов. Обучение программированию
чаще всего основывается на этом языке.
| Данный блок имеет
один вход и один выход. Из простых
команд и проверки условий образуются
составные команды, имеющие более
сложную структуру и тоже один
вход и один выход. Структурный подход к разработке алгоритмов определяет использование только базовых алгоритмических структур (конструкций): следование, ветвление, повторение, которые должны быть оформлены стандартным образом. | |
| Рассмотрим основные
структуры алгоритма. Команда следования состоит только из простых команд. На рисунке простые команды имеют условное обозначение S1 и S2. Из команд следования образуются линейные алгоритмы. Примером линейного алгоритма будет нахождение суммы двух чисел, введенных с клавиатуры. | |
| Команда ветвления - это составная команда алгоритма, в которой в зависимости от условия Р выполняется или одно S1, или другое S2 действие. Из команд следования и команд ветвления составляются разветвляющиеся алгоритмы (алгоритмы ветвления). Примером разветвляющегося алгоритма будет нахождение большего из двух чисел, введенных с клавиатуры. | |
| Команда ветвления может быть полной и неполной формы. Неполная форма команды ветвления используется тогда, когда необходимо выполнять действие S только в случае соблюдения условия P. Если условие P не соблюдается, то команда ветвления завершает свою работу без выполнения действия. Примером команды ветвления неполной формы будет уменьшение в два раза только четного числа. | |
| Команда повторения
- это составная команда Команда повторения с предусловием не является единственно возможной. Разновидностью команды повторения с предусловием является команда повторения с параметром. Она используется тогда, когда известно количество повторений действия. В блок-схеме команды повторения с параметром условие записывается не в ромбе, а в шестиугольнике. Примером циклического алгоритма с параметром будет нахождение суммы первых 20 натуральных чисел. | |
| В команде повторения
с постусловием вначале выполняется
действие S и лишь затем, проверяется
условие P. Причем действие повторяется
до тех пор, пока условие не соблюдается.
Примером команды повторения с постусловием
будет уменьшение положительного числа
до тех пор, пока оно неотрицательное.
Как только число становится отрицательным,
команда повторения заканчивает свою
работу. С помощью соединения только этих элементарных конструкций (последовательно или вложением) можно "собрать" алгоритм любой степени сложности. |
Каждая указанная конструкция может быть без изменений в структуре реализована на любом языке программирования, например, на Паскале и Бейсике. Поэтому необходимо грамотно составить алгоритм с помощью блок-схемы, а уже затем, зная, как записываются команды на конкретном языке программирования, набрать программу на компьютере и получить результат, запустив ее на исполнение.
Линейный алгоритм
Приведем пример записи алгоритма в виде блок-схемы, псевдокодов и на языке Паскаль. Ручное тестирование и подбор системы тестов выполняются аналогично предыдущему заданию.
Разветвляющийся алгоритм
Приведем пример записи разветвляющегося алгоритма для нахождения наибольшего из двух чисел.
Циклический алгоритм
Рассмотрим алгоритм нахождения суммы первых натуральных нечетных чисел до n. Представим запись алгоритма тремя способами: в виде блок-схемы, школьного алгоритмического языка и на языке программирования Pascal.