Алгоритмы. 2

Министерство  образования и науки РФ

Государственное образовательное учреждение высшего  профессионального образования  «Дагестанский государственный  университет»

 

 

 

 

 

Реферат

на тему:

 «Алгоритмы»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Махачкала 2013 год

Содержание

 

• Введение
• Алгоритм и его свойства
• Различные подходы к понятию «алгоритм»
• Понятие исполнителя алгоритма
• Свойства алгоритмов
• Виды алгоритмов
• Способы записи алгоритмов
• Понятие алгоритмического языка
• Понятие блок-схемы
• Понятие языка программирования
• Эволюция языков программирования
• Заключение
• Список литературы
• Введение

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Предположим, мы прочитали в учебнике, что самый  короткий путь из точки А в точку  В - это прямая. Это утверждение  становится нашим знанием. Да теперь мы знаем, что если понадобится пройти из точки. А в точку В самым коротким путём, то нужно будет идти по прямой. Но сможем ли мы в конкретной ситуации пройти этой самой прямой. Например, в лесу. Сомневаюсь. От того, что мы знаем, что надо делать ещё не появляется знание как это сделать.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

1.1 Различные  подходы к понятию «алгоритм»

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

Алгоритмы являются объектом систематического исследования пограничной  между математикой и информатикой научной дисциплины, примыкающей к математической логике - теории алгоритмов.

Особенность положения  состоит в том, что при решении  практических задач, предполагающих разработку алгоритмов для реализации на ЭВМ, и  тем более при использовании  на практике информационных технологий, можно, как правило, не опираться на высокую формализацию данного понятия. Поэтому представляется целесообразным познакомиться с алгоритмами и алгоритмизацией на основе содержательного толкования сущности понятия алгоритма и рассмотрения основных его свойств. При таком подходе алгоритмизация более выступает как набор определенных практических приемов, особых специфических навыков рационального мышления в рамках заданных языковых средств. Можно провести аналогию между этим обстоятельством и рассмотренным выше подходом к измерению информации: тонкие математические построения при «кибернетическом» подходе не очень нужны при использовании гораздо более простого «объемного» подхода при практической работе с компьютером.

Само слово «алгоритм» происходит от algorithmi - латинской формы написания имени великого математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами.

 

1.2 Понятие  исполнителя алгоритма

Понятие исполнителя  невозможно определить с помощью  какой-либо формализации. Исполнителем может быть человек, группа людей, робот, станок, компьютер, язык программирования и т.д. [3] Важнейшим свойством, характеризующим любого из этих исполнителей, является то, что исполнитель умеет выполнять некоторые команды. Так, исполнитель-человек умеет выполнять такие команды как «встать», «сесть», «включить компьютер» и т.д., а исполнитель-язык программирования Бейсик - команды PRINT, END, LIST и другие аналогичные. Вся совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя (СКИ).

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

Одно из принципиальных обстоятельств состоит в том, что исполнитель не вникает в смысл того, что он делает, но получает необходимый результат. В таком случае говорят, что исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции. [4]

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

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

 

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

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

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

II. Используемые на  практике алгоритмы составляются  с ориентацией на определенного  исполнителя. Чтобы составить  для него алгоритм, нужно знать,  какие команды этот исполнитель  может понять и исполнить, а  какие - не может. Мы знаем, что у каждого исполнителя имеется своя система команд. Очевидно, составляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые он может понять. Это свойство алгоритмов будем называть понятностью.

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

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

Отмеченное свойство алгоритмов называют определенностью  или детерминированностью.

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

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

 

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

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

· Механические алгоритмы, или иначе детерминированные, жесткие (например алгоритм работы машины, двигателя  и т.п.);

· Гибкие алгоритмы, например стохастические, т.е. вероятностные и эвристические.

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

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

· Эвристический алгоритм (от греческого слова “эврика”) - это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и прошлом опыте решения схожих задач.

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

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

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

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

 

 

 

 

 

 

 

 

 

 

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

 

На практике наиболее распространены следующие формы  представления алгоритмов:

I. псевдокоды (полуформализованные  описания алгоритмов на условном  алгоритмическом языке, включающие  в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

II. графическая (изображения  из графических символов);

III. программная (тексты  на языках программирования).

 

2.1 Понятие  алгоритмического языка

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

Как и каждый язык, алгоритмический  язык имеет свой словарь. Основу этого  словаря составляют слова, употребляемые для записи команд, входящих в систему команд исполнителя того или иного алгоритма. Такие команды называют простыми командами. В алгоритмическом языке используют слова, смысл и способ употребления которых задан раз и навсегда. Эти слова называют служебными. Использование служебных слов делает запись алгоритма более наглядной, а форму представления различных алгоритмов - единообразной.

Алгоритм, записанный на алгоритмическом языке, должен иметь  название. Название желательно выбирать так, чтобы было ясно, решение какой задачи описывает данный алгоритм. Для выделения названия алгоритма перед ним записывают служебное слово АЛГ (АЛГоритм). За названием алгоритма (обычно с новой строки) записывают его команды. Для указания начала и конца алгоритма его команды заключают в пару служебных слов НАЧ (НАЧало) и КОН (КОНец). Команды записывают последовательно.

 

2.2 Понятие  блок-схемы

А этот способ оказался очень  удобным средством изображения  алгоритмов и получил широкое  распространение в научной и  учебной литературе.

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

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

Можно встретить даже такое утверждение: «Внешне алгоритм представляет собой схему - набор  прямоугольников и других символов, внутри которых записывается, что  вычисляется, что вводится в машину и что выдается на печать и другие средства отображения информации «. Здесь форма представления алгоритма смешивается с самим алгоритмом.

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

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

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

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

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

Блок «решение» используется для обозначения переходов управления по условию. В каждом блоке «решение» должны быть указаны вопрос, условие или сравнение, которые он определяет.

Блок «модификация» используется для организации циклических  конструкций. (Слово модификация означает видоизменение, преобразование). Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения.

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

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

 

2.3 Понятие  языка программирования

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

Язык программирования служит двум связанным между собой  целям: он дает программисту аппарат  для задания действий, которые  должны быть выполнены, и формирует  концепции, которыми пользуется программист, размышляя о том, что делать. Первой цели идеально отвечает язык, который настолько "близок к машине", что всеми основными машинными аспектами можно легко и просто оперировать достаточно очевидным для программиста образом. Второй цели идеально отвечает язык, который настолько «близок к решаемой задаче», чтобы концепции ее решения можно было выражать прямо и коротко.

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

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

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

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

· интерпретаторы, которые  сканируют и проверяют исходный код в один шаг,

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

 

2.4 Эволюция  языков программирования

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

- высокое качество  создаваемых программ (компактность  и скорость выполнения);

- возможность использования  конкретных аппаратных ресурсов;

- предсказуемость объектного кода и заказов памяти;

- для составления эффективных  программ необходимо знать систему  команд и особенности функционирования  данной ЭВМ;

- трудоемкость процесса  составления программ (особенно  на машинных языках и ЯСК), плохо  защищенного от появления ошибок;

- низкая скорость программирования;

- невозможность непосредственного  использования программ, составленных  на этих языках, на ЭВМ других  типов.

Машинно-ориентированные  языки по степени автоматического  программирования подразделяются на классы.

Машинный язык. Отдельный компьютер имеет свой определенный Машинный язык (далее МЯ), ему предписывают выполнение указываемых операций над определяемыми ими операндами, поэтому МЯ является командным. Однако, некоторые семейства ЭВМ (например, ЕС ЭВМ, IBM/370/ и др.) имеют единый МЯ для ЭВМ разной мощности. В команде любого из них сообщается информация о местонахождении операндов и типе выполняемой операции. [5]

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

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

Использование символических  адресов - первый шаг к созданию ЯСК. Команды ЭВМ вместо истинных (физических) адресов содержат символические адреса. По результатам составленной программы определяется требуемое количество ячеек для хранения исходных промежуточных и результирующих значений. Назначение адресов, выполняемое отдельно от составления программы в символических адресах, может проводиться менее квалифицированным программистом или специальной программой, что в значительной степени облегчает труд программиста.

Автокоды. Есть также  языки, включающие в себя все возможности  ЯСК, посредством расширенного введения макрокоманд - они называются Автокоды.

В различных программах встречаются некоторые достаточно часто использующиеся командные  последовательности, которые соответствуют  определенным процедурам преобразования информации. Эффективная реализация таких процедур обеспечивается оформлением их в виде специальных макрокоманд и включением последних в язык программирования , доступный программисту. Макрокоманды переводятся в машинные команды двумя путями - расстановкой и генерированием. В постановочной системе содержатся «остовы» - серии команд, реализующих требуемую функцию, обозначенную макрокомандой. Макрокоманды обеспечивают передачу фактических параметров, которые в процессе трансляции вставляются в «остов» программы, превращая её в реальную машинную программу.

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

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

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

Макрос. Язык, являющийся средством для замены последовательности символов описывающих выполнение требуемых действий ЭВМ на более сжатую форму - называется Макрос (средство замены).

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

Макрос одинаково может  работать, как с программами, так и с данными.

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

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

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

Проблемно - ориентированные  языки. С расширением областей применения вычислительной техники возникла необходимость формализовать представление постановки и решение новых классов задач. Необходимо было создать такие языки программирования, которые, используя в данной области обозначения и терминологию, позволили бы описывать требуемые алгоритмы решения для поставленных задач, ими стали проблемно - ориентированные языки. Эти языки, языки ориентированные на решение определенных проблем, должны обеспечить программиста средствами, позволяющими коротко и четко формулировать задачу и получать результаты в требуемой форме. [5]

Проблемных языков очень  много, например:

Фортран, Алгол - языки, созданные  для решения математических задач;

Simula, Слэнг - для моделирования;

Лисп, Снобол - для работы со списочными структурами.

Универсальные языки. Универсальные  языки были созданы для широкого круга задач: коммерческих, научных, моделирования и т.д. Первый универсальный  язык был разработан фирмой IBM, ставший  в последовательности языков Пл/1. Второй по мощности универсальный язык называется Алгол-68. Он позволяет работать с символами, разрядами, числами с фиксированной и плавающей запятой. Пл/1 имеет развитую систему операторов для управления форматами, для работы с полями переменной длины, с данными организованными в сложные структуры, и для эффективного использования каналов связи. Язык учитывает включенные во многие машины возможности прерывания и имеет соответствующие операторы. Предусмотрена возможность параллельного выполнение участков программ.