В основу какой технологии были положены структуры алгоритмов

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Понятие и свойства алгоритма .doc

Скачиваний:

• Содержание.
• Алгоритмы. Понятие и свойства алгоритма.
• Примеры простой и непростых программ:
• Основные (базовые) структуры алгоритмов и их производные:
• Стадии создания алгоритма:
• Программа.
• Вычислительные машины.
• Хронология Вычислительных Машин
• Список использованной литературы.

Заказать учебную работу

Закажи выполнение студенческой работы и сдай на отлично

Временно скрыть

Больше не показывать

Консультант Анна

Помощник Анна

Только сегодня: скидка до 20% в подарок на первый заказ.
Какую работу нужно написать?

Другую работу

Помощник Анна

Московский Авиационный Институт (Технический Университет) Реферат Введение в специальность Тема: Алгоритм и программа для вычислительной машины. Выполнила студентка группы 04-115 Малкова Екатерина Сергеевна Москва -2007- Алгоритмы. 3 Понятие и свойства алгоритма. 3 Примеры простой и непростых программ: 5 5 Основные (базовые) структуры алгоритмов и их производные: 6 Стадии создания алгоритма: 6 Программа. 6 Основные языки программирования 7 Вычислительные машины. 7 Хронология Вычислительных Машин 7 Список использованной литературы. 9

Алгоритмы. Понятие и свойства алгоритма.

Алгоритм — формальное описание последовательности действий, которое необходимо выполнить для решения задачи; — предписание, определяющее ход вычислительного процесса, связанного с преобразованием данных от некоторого их исходного состояния к требуемому результату. Формальные описания алгоритмов аналогичны представлениям основных частей программ, которые их реализуют, поэтому многое, что относят к описанию конкретных программ, применимо к алгоритму и наоборот. Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово алгоритм возникло в Европе после перевода на латынь книги этого математика. Теория алгоритмов имеет большое практическое значение. Алгоритмический тип деятельности важен не только как мощный тип деятельности человека, но и как одна из эффективных форм его труда. Через алгоритмизацию, через расчленение сложных действий на все более простые действия, выполнение которых доступно машинам, пролегает путь к автоматизации. Создание алгоритма для решения задач какого-либо типа, его представление исполнителю в удобной для него форме – это творческий акт. Образно говоря, историю математики можно было бы назвать историей открытия алгоритмов и их внедрения в человеческую практику. Если внимательно оглядеться вокруг, то можно обнаружить множество постоянно выполняемых алгоритмов. Мир алгоритмов очень разнообразен. Несмотря на это, удается выделить общие свойства, которыми обладает любой алгоритм (Рис. 1). Рис. 1 Свойства алгоритмов1. Дискретность. Алгоритм представляет процесс решения задачи как последовательность выполнения шагов-этапов. Для выполнения каждого этапа требуется определенное время, т.е. преобразование исходных данных в результат происходит дискретно во времени. 2. Определенность (детерминированность). Каждое правило алгоритма должно быть четким и однозначным. Отсюда выполнение алгоритма носит механический характер. 3. Результативность (финитность, конечность). Алгоритм должен приводить к решению задачи за конечное число шагов. 4. Массовость. Алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся исходными данными (область применимости алгоритма). В

Вид стандартного графического объекта Назначение

Начало, завершение программы или подпрограммы

Ввод-вывод данных

Обработка данных (вычисление, пересылка и т.п.)

Проверка условия

Вызов процедуры

Соединительные линии и их объединение.

Точки связи или соединители

Комментарий

Рис. 2 Вид и назначение графического объекта иды алгоритмов:

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

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

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

Основные понятия программирования

Основные понятия программирования • Основные определения, свойства алгоритма • Формы представления алгоритмов • Язык блок-схем • Базовые структуры алгоритмов: следование, ветвление, повторение • Язык псевдокода

Основные определения • Алгоритм (от имени учѐного аль-Хорезми (перс. یمزراوخ‎[al-Khwārazmī]) — точный набор инструкций, которые необходимо выполнить для решения поставленной задачи за конечное число шагов. • Команда – элементарное предписание, предусматривающее выполнение какого-либо действия. • Операторы – действия, предписываемые командой. • Программа – данные, их описание и алгоритм, записанный на языке программирования. • Программирование – процесс создания программ. • Язык программирования – формализованный язык для написания программ. Все языки программирования являются искусственными, в них синтаксис и семантика строго определены.

Основные определения Свойства алгоритма • Дискретность – возможность разбиения алгоритма на отдельные элементарные действия. Алгоритм представляет процесс решения задачи как последовательность выполнения шагов-этапов. Для выполнения каждого эпата требуется определенное время, т.е. преобразование исходных данных в результат происходит дискретно во времени. • Определенность (детерминированность) – обеспечение однозначности результата при многократных расчетах с одними и теми же исходными данными. Каждое правило алгоритма должно быть четким и однозначным, исключая возможность искажения или двусмысленного толкования. • Результативность (финитность, конечность) – обязательное получение результата за конечное число шагов. Невозможность получения результата свидетельствует о том, что данный алгоритм неприменим для решения поставленной задачи. • Массовость – возможность получения результата для некоторого класса задач, различающихся исходными данными ( область применимости алгоритма ). Алгоритм решения задачи должен разрабатываться в общем виде для некоторого класса сходных задач.

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

Формы представления алгоритмов Пример словесного способа записи алгоритма решения квадратного уравнения ax²+bx+c=0 Задать коэффициенты уравнения a, b, c Вычислить дискриминант по формуле d=b² − 4ac Если дискриминант меньше нуля, то вывести ответ «Корней нет» и остановиться (конец алгоритма); в противном случае продолжить выполнение алгоритма; Вычислить корни уравнения по формулам x 1 =( − b+√d)/2a; x 2 =( − b − √d)/2a; Вывести полученные значения в качестве ответа. Конец алгоритма

Язык блок-схем Некоторые условные графические обозначения символов блок-схем

Название символа	Обозначение и пример заполнения Пояснение
Начало-конец	Начало или конец
алгоритма, вход или
	выход в подпрограмму
Начало		Конец

Ввод-вывод

Ввод или вывод данных

Печать Z

Процесс		Обработка данных
			(вычисление,
Z = X + Y	пересылка и т.п.)

Язык блок-схем Некоторые условные графические обозначения символов блок-схем (продолжение)

Название символа	Обозначение и пример заполнения				Пояснение
Предопределенный	Вызов процедуры,
		процесс	вычисления по
Имя				подпрограмме
Решение	Проверка условия
Да		Нет

I >10 Комментарии

Линии потока	Соединительные
линии, точки связи

Язык блок-схем Пример графического способа представления алгоритма решения квадратного уравнения ax²+bx+c=0

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

Базовые структуры алгоритмов: следование, ветвление, повторение Базовая структура «следование» Следование – это последовательное выполнение действий (блоков). Эта базовая структура означает, что несколько операторов должны быть выполнены последовательно один за другим и только единственный раз за время выполнения данной программы. Алгоритм, составленный из только из базовых структур «следование», называется линейным . 1 Оператор 1 2 Оператор 2 3 Оператор 3

Разработка алгоритмов решения задачи

Информатика, информационные технологии

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

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

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

Различают последовательности действий (вычислений) линейной, разветвленной и циклической структуры.

Линейная структура процесса вычислений предполагает, что для получения результата необходимо выполнить некоторые операции в определенной последовательности. Например, для определения площади треугольника по формуле Герона необходимо сначала определить полупериметр треугольника, а затем по формуле его площадь.

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

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

Процессы вычислений циклической структуры в свою очередь можно

разделить на три группы:

• циклические процессы, для которых количество повторений известно – (счетные циклы или циклы с заданным количеством повторений);

• циклические процессы, завершающиеся по достижении или нарушении некоторых условий — итерационные циклы;

• циклические процессы, из которых возможны два варианта выхода: выход по завершении процесса и досрочный выход по какому-либо дополнительному условию — поисковые циклы.

Формальное описание алгоритмов осуществляют с использованием схем алгоритмов и псевдокодов.

На изображение схем алгоритмов существует ГОСТ 19.701-90, согласно которому каждой группе действий ставится в соответствие блок особой формы.

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

Основные элементы схем алгоритма Таблица 1

Наименование	Обозначение	Функция
Блок начало-конец (пуск-остановка)	Элемент отображает вход из внешней среды или выход из нее (наиболее частое применение ? начало и конец программы). Внутри фигуры записывается соответствующее действие.
Блок вычислений (вычислительный блок)	Выполнение одной или нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно сами операции, например, операцию присваивания a = 10*b + c.
Логический блок (блок условия)	Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути. Примеры решения: в общем случае ? сравнение (три выхода: ,
Предопределенный процесс	Символ отображает выполнение процесса, состоящего из одной или нескольких операций, который определен в другом месте программы (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в него данные. Например, в программировании ? вызов процедуры или функции.
Данные (ввод-вывод)	Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические символы).
Граница цикла	Символ состоит из двух частей ? соответственно, начало и конец цикла ? операции, выполняемые внутри цикла, размещаются между ними. Условия цикла и приращения записываются внутри символа начала или конца цикла ? в зависимости от типа организации цикла. Часто для изображения на блок-схеме цикла вместо данного символа используют символ решения, указывая в нем условие, а одну из линий выхода замыкают выше в блок-схеме (перед операциями цикла).
Соединитель	Символ отображает вход в часть схемы и выход из другой части этой схемы. Используется для обрыва линии и продолжения ее в другом месте (для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит из нескольких страниц). Соответствующие соединительные символы должны иметь одинаковое (при том уникальное) обозначение.
Комментарий	Используется для более подробного описания шага, процесса или группы процессов. Описание помещается со стороны квадратной скобки и охватывается ей по всей высоте. Пунктирная линия идет к описываемому элементу, либо группе элементов (при этом группа выделяется замкнутой пунктирной линией). Также символ комментария следует использовать в тех случаях, когда объём текста, помещаемого внутри некоего символа (например, символ процесса, символ данных и др.), превышает размер самого этого символа.

Для рисования схем алгоритмов удобно использовать программу Microsoft Office Visio.

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

В случае, когда схема алгоритма не умещается на листе, используют соединители. При переходе на другой лист или получении управления с другого листа в комментарии указывается номер листа, например «с листа 3» «на лист 1».

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

• следование — обозначает последовательное выполнение действий

• ветвление — соответствует выбору одного из двух вариантов действий

• цикл-пока — определяет повторение действий, пока не будет нарушено

условие, выполнение которого проверяется в начале цикла (рис. 2, в).

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

производные от базовых:

• выбор — выбор одного варианта из нескольких в зависимости от значения некоторой величины (рис. 3, а);

• цикл до — повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле (рис. 3, в);

• цикл с заданным числом повторений (счетный цикл) — повторение некоторых действий указанное число раз (рис. 3, д).

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

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

Схема алгоритма детально отображает особенности разработанного алгоритма. Иногда такой высокий уровень детализации не позволяет выделить суть алгоритма. В этих случаях для описания алгоритма используют псевдокод.

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

Для каждой структуры используют свою форму описания, которая, в общем случае может быть произвольной.

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

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

Статьи к прочтению:

Разработка экспертных систем: практикум.
Разработка руководства пользователя (оператора)

Пример вычисления определителя четвертого порядка по теореме Лапласа

Основные структуры алгоритмов. реализация алгоритмов.

Информатика, информационные технологии

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

Элементарные шаги алгоритма при укрупнении объединяются в алгоритмические конструкции: последовательные, ветвящиеся, циклические, рекурсивные. В 1969 году Эдсгер В. Дейкстра в статье Структуры данных и алгоритмы доказал, что для записи любого алгоритма достаточно трех основных алгоритмических конструкций: последовательных, ветвящихся, циклических. (Бойм и Якопини (Bohm, Jacopini, 1966), Миле (Mills, 1972))

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

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

Определение.Алгоритм Р реализован через последовательную алгоритмическую конструкцию,если каждый шаг алгоритма Р выполняется один раз, причем после каждого i-го шага выполняется ( i +1)-й шаг, если i-й шаг — не конец алгоритма.

Т.е. следование- это последовательное размещение блоков и групп блоков.

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

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

На рисунках P1 и P2 представляют собой в общем случае некоторые серии команд для соответствующего исполнителя. В зависимости от истинности (Да) или ложности (Нет) условия управление передаётся по одной из двух ветвей.

Обход- частный случай разветвления, когда одна ветвь не содержит ни каких действий.

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

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

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

Тело цикла — та последовательность действия, которая выполняется многократно (в цикле).

Цикл «До» применяется при необходимости выполнить какие-либо вычисления несколько раз до выполнения условия.

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

Цикл «Пока» отличается от цикла «До» тем, что проверка условия производится до выполнения тела цикла. В этом случае, если при первой проверке условия оно выполняется, то тело цикла не выполняется ни разу. Поэтому цикл «Пока» называют циклом «с предусловием», а цикл «До» — «с постусловием».

Определение.Алгоритм R называется рекурсивным,если на каком-либо шаге он прямо или косвенно обращается сам к себе.

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

Вопросы для активизации и создания проблемной ситуации.

1. Что понимается под стратегией решения задач?

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

3. Что понимается под поиском решений задач?

4. Свойства алгоритма.

5. В чем заключается свойство массовости?

6. В чем заключается свойство конечности?

7. В чем заключается свойство результативности?

8. Какие стратегии реализации алгоритма существуют?

9. На какие виды подразделяются алгоритмы?

10. Способы записи алгоритмов

11. Графический способ записи алгоритмов.

12. Какие виды блок- схем существуют?

Лекция №10. Реализация алгоритмов. Основные вычислительные алгоритмы. (1 час)

Цель лекции: Изучить историю возникновения теории алгоритмов; принцип

работы абстрактных вычислительных конструкции; рассмотреть

принцип действия Машины Тьюринга. Сделать анализ алгоритмов;

дать понятие сложности алгоритма.

1. Основные вычислительные алгоритмы.

2. Машина Тьюринга.

3. Анализ алгоритмов. Понятие сложности алгоритма

4. Сопоставление алгоритмических моделей

В основу какой технологии были положены структуры алгоритмов