84442

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

Курсовая

Информатика, кибернетика и программирование

Вывод об алгоритмизации как части этапа программирования Алгоритмизация Понятие алгоритма Алгоритм –- это последовательность команд выполнение которых приводит к решению поставленной задачи. Понятие алгоритма относится к первоначальным основным базисным понятиям математики.

Русский

2015-03-19

118.84 KB

6 чел.

СОДЕРЖАНИЕ

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

1)история появление термина

2)понятие алгоритмизации

  1.  Этапы появления алгоритма при алгоритмизации

А) Замысел

Б) Моделирование

В) Алгоритм

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

  1) Требования к алгоритму

  2) критерий эффективности

4. Виды алгоритмов

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

6. Стандартизация алгоритмов

7. Вывод об алгоритмизации как части (этапа) программирования


    
Алгоритмизация

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

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

Понятие алгоритма относится к первоначальным, основным, базисным понятиям математики. Вычислительные процессы алгоритмического характера (арифметические действия над целыми числами, нахождение наибольшего общего делителя двух чисел и т. д.) известны человечеству с глубокой древности. Само слово «алгоритм» происходит от имени хорезмского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, первые использовал цифр 0 для обозначения пропущенной позиции в записи числа. В первой половине XII века книга аль-Хрезми в латинском переводе попала в Европу. Ей было дано название «Алгоритмы о счёте индийском». По-арабски книга называлась «Китаб аль-джебрваль-мукабала» («Книга о сложении и вычитании»). Из этого название в русский язык попало слово алгебра (алгебра - аль-джебр - восполнение). В течение нескольких следующих столетий появилось множество других трудов, посвященных обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi или algorismi. Со временем algorism (или algorismus) обрело значение способа выполнения арифметических действий. Именно в таком значении оно вошло во многие европейские языки. Постепенно значение слова расширялось. Учёные начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам (степени, дробные показатели, логарифмы)

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


  1.  Этапы появления алгоритма

Как пишут авторы книги «Алгоритмы. Построение и анализ» (Томас Кармен, Чарльз Лейзерсон, Рональд Ривест и Клиффорд Штайн):

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

1. Краткая содержательная формулировка задачи, решаемой на ЭВМ;

2. Построение математической модели рассматриваемого в задаче объекта или процесса (проверка исполнимости/реализуемости данной задачи, математическая модель – это один из методов этой проверки);

3. Разработка эффективного алгоритма решения задачи;

4. Создание продукта по разработанному алгоритму;

5. Проверка работоспособности («отладка», прорабатывание всех возможных вариантов входных данных и проверка правильности результата в каждом из случаев);

6. Оформление документации (запись нового алгоритма в соответствие с принятыми стандартами)

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

Ряд общих требований для каждого алгоритма:

  1.  Дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
  2.  Детерминированность (или определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит формальный характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
  3.  Понятность – алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд. Алгоритм должен быть понятным!
  4.  Результативность (или конечность). Это свойство состоит в том, что при корректно заданных исходных данных алгоритм должен завершать работу (приводить к решению задачи) и выдавать результат за конечное число шагов.
  5.  Массовость – универсальность. Это означает, что алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применения алгоритма. Но это правило не всегда действует, в основном разрабатывается один или несколько алгоритмов для решения одной задачи. Например можно решить задачу с помощью if-then-else или с использованием switch-case.

2) Эффективность алгоритмов

При оценке эффективности алгоритма учитывают его емкостной сложности и временной трудоемкости. Первая характеристика отвечает за то, сколько памяти потребуется, чтобы  разместить все данные, участвующие в вычислительном процессе. Естественно, к  ним  относятся  входные  наборы,  промежуточные,  и  выходная  информация. По второму критерию наилучшим вариантом будет тот алгоритм, который,  в  сравнении  с  конкурентами,  нуждается  в  наименее  продолжительном  по  времени вычислительном процессе, выполняющегося в равных условиях т.е. технические характеристики исполнителя (компьютера) и взаимодействие с другими выполняющимися в данный момент процессами одинаково.  Скорость  реализации  выбираемого  алгоритма  может  существенно зависеть от содержания набора входных данных. Наихудшее время выполнения — это максимальное время работы алгоритма при самом «плохом» из всех возможных входов. Средний случай выполнения — это среднее время работы алгоритма на всех возможных входах. Их этих двух типов времени выполнения, легче всего рассуждать о наихудшем случае и поэтому его используют чаще в качестве эталона для заданного алгоритма. Процесс определения наихудшего и среднего случая времени выполнения алгоритма может быть достаточно сложным, т.к. обычно невозможно запустить алгоритм для всех возможных входов. Обычно временную эффективность не связывают с конкретной вычислительной установкой,  а  оперируют  только «шагами».  Любой шаг алгоритма реализуется некоторым числом элементарных  инструкций  исполнителя.  Например, найти  сумму  натуральных  чисел  от 1 до  заданного n.  Если воспользоваться  известной  формулой  для суммы  арифметической  прогрессии, то вычисления потребуют лишь 3 шага: сложение, умножение и деление. Если  же  реализовать  вычислительный  процесс  как  циклический:  цикл  с параметром, управляющая переменная «пробежит» значения от 1 до n, – то придется  выполнить n шагов  алгоритма.  Сомнений,  какой  из  алгоритмов более  эффективен,  кажется,  не  возникает.  Однако  вспомните  о «худших случаях»:  при  небольших  значениях n (скажем,  от 2 до 4), «медленный» алгоритм, вероятно, предпочтительнее. Для  алгоритмов,  подобных  только  что  рассмотренному, – n шагов  для обработки n входных  значений, – очевидно,  что  количество  шагов  является функцией от числа обрабатываемых элементов. Можно считать, что количество шагов является функцией от количества элементов – f(n).  В  математике  существует  специальный  механизм  оценки  скорости  роста интересующей  исследователя  величины:  ее  сравнивают  с  какой-нибудь функцией,  чье  поведение  хорошо  исследовано.  При  этом  используется  обозначение g(n)=O(f(n)), – читается:  О-большое, – которое  мы  будем относить к интересующим нас дискретным функциям f(n) натурального n и  ко  всем  функциям g(n),  растущим  не  быстрее f(n).  Формулировка  «растущим  не  быстрее»  означает,  что  существует  такая  пара  положительных значений M и n0, что |g(n)|≤ M |f(n0)| для n≥n0.  Еще говорят, что функция g(n) – «порядка f(n) для больших n».  Такая O–нотация дает нам верхнюю оценку временно́й трудоемкости алгоритма  –  его асимптотическую  сложность.  Обратите  внимание,  что  использование констант M и n0,  фигурирующих  в  определении,  фактически  связано  с «большими»  значениями  аргумента n,  и  мало  что  дает  при  его  малых значениях.  

Укажем несколько важных свойств O-операций:  

(a) f(n)=O(f(n))  

(b) c*O(f(n))=O(f(n)), где c – некоторая константа

(c) O(f(n))+O(f(n))=O(f(n))  

(d) O(O(f(n)))=O(f(n))  

(e) O(f(n))*O(g(n))=O(f(n)*g(n))  

Кроме введенной терминологии, полезна и другая, т.н. o–нотация («о-малое»). Обозначение o(f(n)) относится к функциям, которые растут быстрее f(n).  Вновь  обращаясь  к  примеру  с  суммой  арифметической  прогрессии,  можем сказать,  что  асимптотическая  эффективность  алгоритма  непосредственного суммирования n элементов соответствует линейной сложности, поскольку его быстродействие, то есть число шагов, согласно свойству (a), есть O(n).  Вообще говоря, если алгоритм связан с обработкой n входных элементов, и аналитического выражения – формулы – для быстрого вычисления результата в нашем  распоряжении  нет,  то  достижение  лучшей  эффективности,  чем  O(n), если это вообще возможно, следует рассматривать как большой успех. Более  эффективным,  чем  алгоритм  с линейной  трудоемкостью,  является  его  конкурент,  чье  поведение  оценивается как O(log2n). Еще быстрее работает алгоритм с постоянной трудоемкостью – O(1),  с  одним  из  них  мы  уже  имели  дело – это  алгоритм  обмена. Соответственно, «между» O(n) и O(n2) находится место для O(n*log2n).

  1.  Виды алгоритмов
  2.  Линейные

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

  1.  Разветвляющиеся

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

  1.  Циклические

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

а) проверка условия выхода из цикла проводится до выполнения тела цикла. В том случае, если условие выхода из цикла выполняется, то тело цикла не выполняется ни разу.

б) первая проверка условия выхода из цикла осуществляется после того, как тело цикла выполнено, соответственно цикл выполняется хотя бы один раз

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

  1.  Комбинированные

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

  1.  Способы записи алгоритмов
  2.  Словесная форма

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

  1.  Графическая (блок-схемы)

Блок-схема представляет собой совокупность символов, соответствующих этапам работы алгоритма и соединяющих их линий.

  1.  Псевдокод

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

  1.  Стандартизация алгоритмов

На территории Российской Федерации действует единая система программной документации (ЕСПД), частью которой является Государственный стандарт — ГОСТ 19.701-90 «Схемы алгоритмов программ, данных и систем». Описанные в стандарте обозначения могут использоваться для изображения схем ресурсов системы, схем взаимодействия программ и т.п.

Рассматриваемый ГОСТ практически полностью соответствует международному стандарту ISO 5807:1985.

Блок-схема представляет собой совокупность символов, соответствующих этапам работы алгоритма и соединяющих их линий. Пунктирная линия используется для соединения символа с комментарием. Сплошная линия отражает зависимости по управлению между символами и может снабжаться стрелкой. Стрелку можно не указывать при направлении дуги слева направо и сверху вниз. Согласно п. 4.2.4, линии должны подходить к символу слева, либо сверху, а исходить снизу, либо справа. Есть и другие типы линий, используемые, например, для изображения блок-схем параллельных алгоритмов.

Вот примеры стандартов записи некоторых структурных элементов алгоритмов:

Терминатор: начало и конец процесса обработки данных

Данные: данные, носитель которых неопределен

Процесс: элементарная операция по обработке данных

Подготовка: подготовительные операции, выполняемые с целью модификации последующих данных (например для циклов с параметром)

Границы цикла: начало и конец цикла. Особенности работы цикла записываются в начале или конце, в завсимости от того где осуществляется их проверка (циклы while, until)

Предопределенный процесс (процедура): процесс, состоящий из операций, описанных в другом месте

Решение: операция с одним входом и несколькими альтернативными выходами, один из которых активизируется после проверки условия, записанного внитри символа (конструкция if - else)

Комментарий: символ используется для внесения пояснительных записей

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

  1.  Вывод об алгоритмизации как части (этапа) программирования

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

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

Формальное следование существующим стандартам документирования алгоритмов, особенно при «не автоматизированном (ручном) исполнении» может существенно замедлить процесс документирования.


 

А также другие работы, которые могут Вас заинтересовать

35598. Геологическая деятельность человека 30 KB
  Геология сегодня это фундаментальная наука. Геология это наука о Земле. Геология разделяется на теоретическую и практическую.
35599. Геологическая деятельность озер и болот 17.94 KB
  Источниками питания озер служат атмосферные воды поверхностный сток и подземная разгрузка водоносных горизонтов; Основную массу воды в озера поставляют реки. По величине озера сильно различаются. Существенно различаются озера по глубине солености воды и т. По этому признаку выделяются озера экзогенные происхождение которых связано с поверхностными факторами и эндогенные появление которых обусловлено поверхностным проявлением глубинных факторов.
35600. Тектонические движения 15.19 KB
  Хайн разделил все тектонические движения по уровню их зарождения в земном шаре. Он все тектонические движения разделил на: 1 Общие колебания в ядре Земли; 2 Сверхглубинные движения в нижней мантии; 3 Глубинные движения в верхней мантии в результате физикохимических процессов; 4 Коровые движения производные от глубинных движений делятся на складчатые и разрывные; 5 Покровные поверхностные возникают в результате перетока пластичных масс или гравитационного соскальзывания крупных пластин осадочного чехла что приводит к образованию...