Алгоритмы и программы реферат

Обновлено: 03.07.2024

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

ее команды не допускают различных вариантов исполнения;

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

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

Какими свойствами должен обладать алгоритм? Перечислим их:

дискретность2 — алгоритм делится на отдельные элементарные шаги;

Нужна помощь в написании доклада?

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

определенность — каждая команда однозначно определяет действие исполнителя;

конечность(результативность) — алгоритм должен завершаться за конечное число шагов.

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

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

Нужна помощь в написании доклада?

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

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

Discrete (англ.) — состоящий из отдельных частей

Formalis (лат.) — строго по установленным правилам

Programma (греч.) — распоряжение

Translator (англ.) — переводчик

Нужна помощь в написании доклада?

Собрала для вас похожие темы рефератов, посмотрите, почитайте:

Введение

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

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

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

Такие качества:

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

Во-первых, неправильно связывать алгоритм с решением проблемы. Алгоритм может вообще не решить проблему.

Типы алгоритмов

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

Линейный алгоритм — набор команд (инструкций), которые выполняются одна за другой во времени.

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Список литературы

Образовательный сайт для студентов и школьников

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	реферат
Язык	русский
Дата добавления	13.03.2019
Размер файла	82,5 K

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

Московский государственный университет пищевых производств

Алгоритм. Виды и свойства алгоритмов

Целоусова Ирина Александровна

Основные характеристики алгоритмов

Способы описания алгоритма

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

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

Современное формальное определение алгоритма было дано в 30--50-х годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча -- Тьюринга), Н. Винера, А. А. Маркова.

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

Для изучения основ алгоритмизации применяется так называемый Русский алгоритмический язык (школьный алгоритмический язык), использующий понятные школьнику слова на русском языке.

Основные служебные слова алгоритмического языка:

1.Описание алгоритма: алг (алгоритм), арг (аргумент),рез (результат),

нач (начало) -- начало алгоритма,кон (конец), дано -- исходные данные в произвольной форме, надо -- цель алгоритма и тд

2.Типы данных: цел (целый), вещ (вещественный), сим (символьный),

лит (литера) -- строка,лог (логический),таб(таблица) -- для обозначения массива

3.Обозначение условий: если,то, иначе, все, выбор, при, знач

4. Обозначение циклов:нц (начало цикла), кц (конец цикла),пока, для, от, до, шаг

5.Логические функции и значения для составления выражений: и, или, не, да, нет

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

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

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

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

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

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

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

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

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

Само выражение “свойства алгоритма” некорректно. Свойствами обладают объективно существующие реальности. Можно говорить, например, о свойствах какого-либо вещества. Алгоритм - искусственная конструкция, которую мы сооружаем для достижения своих целей. Чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам. Поэтому нужно говорить не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к алгоритму.

Первое правило - при построении алгоритма прежде всего необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные.

Это правило позволяет сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

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

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

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

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

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

Основные характеристики алгоритмов

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

Временные характеристики алгоритма определяют длительность решения или временную сложность.

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

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

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

Для сложных задач эта характеристика имеет большое значение, т.к. ее изменение значительно сильнее влияет на время решения, чем изменение быстродействия ПК.

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

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

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

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

Способы описания алгоритма

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

1)словесно-пошаговый (на естественном языке);

2)графический (с помощью блок схем);

3)с помощью языка программирования.

Словесный способ описания алгоритмов

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

Способ основан на использовании общепринятых средств общения между людьми и с точки зрения написания трудностей не представляет. Такой способ записи удобно использовать на начальном этапе алгоритмизации задачи. К недостаткам словесного способа записи можно отнести следующее: 1) полное подробное описание алгоритма получается очень громоздким; 2) естественный язык допускает неоднозначность толкования отдельных инструкций; 3) при переходе к этапу программирования требуется дополнительная работа по формализации алгоритма, так как словесное описание может быть понятно человеку, но "непонятно" ПК. Поэтому словесный способ записи алгоритмов не имеет широкого распространения.

Блок-схема алгоритмов и ее элементы

Терминатор начала и конца работы функции

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

Операции ввода и вывода данных

В ГОСТ определено множество символов ввода/вывода, например вывод на магнитные ленты, дисплеи и т.п. Если источник данных не принципиален, обычно используется символ параллелограмма. Подробности ввода/вывода могут быть указаны в комментариях.

Выполнение операций над данными

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

Блок, иллюстрирующий ветвление алгоритма

Вызов внешней процедуры

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

Начало и конец цикла

Символы начала и конца цикла содержат имя и условие. Условие может отсутствовать в одном из символов пары. Расположение условия, определяет тип оператора, соответствующего символам на языке высокого уровня -- оператор с предусловием (while) или постусловием (do … while).

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

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

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

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

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

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

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

3)Разветвляющийся алгоритм -- алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.

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

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

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

1. Алгоритмы на C++,Автор: Роберт Седжвик,2017

2. Алгоритмы для начинающих. Теория и практика для разработчика, Автор: Панос Луридас,2017

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

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

Так, например, применение правила сложения дробей к 1/2 и 2/3 приводит к результату 5/6.

Основное внимание в теории алгоритмов уделяется методам задания (описания, конструирования) алгоритмов.

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

Так, алгоритм сложения дробей можно задать следующей последовательностью команд:

Пример 1 . Алгоритм сложения дробей.

1. Вычислить Y = B*D;

2. Вычислить X 1 = A*D;

3. Вычислить X 2 = B*C;

4. Вычислить X = X 1 +X 2 ;

5. Вычислить Z = НОД(X,Y);

6. Вычислить Е = X div Z;

7. Вычислить F = Y div Z; .

Наш алгоритм состоит из 7-ми инструкций, каждая из которых содержит описание одного из арифметических действий над целыми числами: сложение, умножение, вычисление НОД и целочисленное деление div. Кроме того, каждая инструкция (в неявном виде) содержит указание на следующую выполняемую инструкцию. Таким образом, алгоритм описывает детализированный по шагам процесс преобразования информации. Уровень детализации описания определяется набором допустимых команд. Этот набор называют набором команд Исполнителя или Интерпретатора. При этом подразумевается, что алгоритмы выполняет Исполнитель (Интерпретатор ) - некоторое устройство, однозначно распознающее и точно выполняющее (интерпретирующее) каждую команду алгоритма.

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

Представим себе, что в нашем распоряжении находится Исполнитель, интерпретирующий команды - операции целочисленной арифметики - сложение, вычитание, умножение, вычисление неполного частного (div) и остатка (mod), вычисление НОД и НОК с запоминанием результатов и умением переходить к следующей команде. Тогда для этого Исполнителя можно составлять самые разнообразнные алгоритмы арифметических вычислений - т.е. вычислений, заданных формулами типа X = НОД((A + B) div 100, (A * B - 7) mod 10) используя команды, аналогичные командам алгоритма из примера 1.

Пример 2. Алгоритм деления отрезка пополам с помощью циркуля и линейки.

Построить окружность O 1 с центром A и радиусом AB;

Построить окружность O 2 с центром B и радиусом AB;

Найти точки С и D пересечения окружностей O 1 и O 2 ;

Построить отрезок CD;

Найти точку Е пересечения AB и CD.

Выход : Точка Е - середина отрезка AB.

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

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

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

Пример 3. Алгоритм решения приведенного квадратного уравнения x 2 + px + q = 0;

Вычислить D = p 2 - 4q;

Вычислить x 2 = (-p-(D))/2);

Выход “Решений нет” или корень x или корни x 1 , x 2 .

В этом примере используется команда вида

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

Второй характерной командой, используемой в примере, является команда перехода. Она имеет вид Перейти к , причем число N используется в записи алгоритма как специальная отметка некоторой команды. В примере используются команды перехода Перейти к 1, а числом 1 отмечена команда 1:Закончить работу.

Выполнение команды перехода заключается в том, что Исполнитель переходит к выполнению команды, отмеченной отметкой N (нарушая при этом естественную последовательность выполнениия команд).

2. Характерные свойства алгоритмов.

Понятию алгоритма присущи следующие свойства:

1. Элементарность. Каждая команда из набора команд Исполнителя содержит указание выполнить некоторое элементарное (не детализируемое более подробно) действие, однозначно понимаемое и точно выполняемое Исполнителем.

Понятие элементарности поэтому относительно. Так, в алгоритме примера 1 содержится команда вычисления НОД двух чисел. Это означает, что Исполнитель умеет находить НОД, причем алгоритм вычисления (алгоритм Евклида или какой нибудь другой) скрыт от человека, составляющего алгоритмы для этого Исполнителя. Если набор команд Исполнителя не содержит команды вычисления НОД, вычисление НОД должно быть определено в виде алгоритма.

Пример 4 . Алгоритм Евклида вычисления наибольшего общего делителя целых положительных чисел A и B: НОД(A, B).

Пока U <> V выполнять

Если U Выход : D - наибольший общий делитель A и B.

В этом примере использована команда повторения.Она имеет вид

Выполняя эту команду, Исполнитель проверяет истинность Условия. Если Условие истинно, Исполнитель выполняет Команду, указанную после слова выполнять и повторяет проверку Условия. Выполнение Команды и проверка Условия повторяются до тех пор, пока Условие истинно. Если Условие ложно, Исполнитель переходит к выполнению команды, следующей за командой повторения. В этом же примере использована еще одна разновидность команды ветвления - команда вида

Выполняя эту команду, Исполнитель проверяет Условие. Если Условие выполнено, выполняется Команда 1, в противном случае выполняется команда 2. Далее Исполнитель переходит к следующей команде. Заметим, что команда повторения, как и команды ветвления, содержат в себе другие команды.

2. Определенность . Исполнение алгоритма строго определено. Это означает, что на каждом шаге Исполнитель не только точно выполняет команду, но и однозначно определяет следующую исполняемую команду. Поэтому повторное выполнение алгоритма для одних и тех же исходных данных в точности повторяет первое его выполнение.

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

Так, в примере 2 описан алгоритм сложения любых двух дробей. Одна-единственная задача, решаемая Исполнителем в данный момент, определена значениями исходных данных A, B, C, D. Изменение исходных данных означает решение другой задачи из этого же класса задач.

Аналогично, алгоритм примера 2 строит середину любого отрезка, заданного его концами, а в примере 3 с помощью алгоритма решается любое приведенное квадратное уравнение.

4. Результативность . Исполение любого алгоритма должно быть закончено через конечное число шагов (т.е. выполнение конечного числа команд) с некоторым результатом.

Так, в примере 2 результат - точка E - середина отрезка AB. Алгоритм примера 3 выдает результат “Решений нет “ даже в том случае, когда уравнение не имеет действительных корней, поскольку его дискриминант меньше нуля.

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

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

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

3. ЭВМ как универсальный Исполнитель.

На рис 1 представлена блок-схема ЭВМ .

Внешние устройства ЭВМ.

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

Устройства вывода информации предназначены для вывода информации (результатов) в форме, предназначенной для пользователя - в виде чисел, текстов, рисунков и т.д.

Характерными для персональной ЭВМ устройствами вывода являются монитор (дисплей), принтер, плоттер.

Внешние запоминающие устройства (ВЗУ) предназначены для длительного (при выключенной ЭВМ) хранения информации. В настоящее время наиболее распространены накопители на гибких магнитных дисках (НГМД), накопители на жестких магнитных дисках (НМД), накопители на магнитных лентах (НМЛ).

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

Центральные устройства ЭВМ.

Ядро ЭВМ составляют так называемые центральные устройства - центральный процессор и оперативное запоминающее устройство (ЦП и ОЗУ).

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

Вся информация, необходимая для исполнения алгоритма - исходные, промежуточные и выходные данные, а также сам алгоритм, хранится в ОЗУ в закодированном виде.

ОЗУ представляет из себя совокупность специальных ячеек, каждая из которых предназначена для хранения двоичного кода информации фиксированного объема. Каждая ячейка памяти имеет свой номер, называемый адресом. В современных ПЭВМ ячейка ОЗУ хранит 1 байт информации - 8 двоичных цифр, называемых битами.

Байт 0 1 2 3 4 5 6 7

Характерной особенностью ОЗУ является то, что доступ к данным, хранящимся там, осуществляется по их адресам. Время доступа к данному не зависит от адреса ячейки, в которой оно хранится. Поэтому ОЗУ называют памятью с прямым (случайным) доступом. Размером (объемом) ОЗУ называют количество ее ячеек. Размер ОЗУ выражают в байтах, килобайтах (Kb) и мегабайтах (Mb). 1 килобайт = 1024 байта, 1 мегабайт = 1024 килобайта. И данные, и команды как правило, занимают в ОЗУ несколько подряд адресованных байтов.

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

Понятие о машинном языке.

Набор команд процессора содержит:

арифметико-логические команды - команды арифметических действий над двоичными числами и логических действий над двоичными векторами;

команды управления - команды перехода, ветвлений, повторений, и некоторые другие команды;

команды пересылки данных - команды, с помощью которых обмениваются данными ОЗУ и ЦП;

команды ввода-вывода данных - команды, с помощью которых обмениваются данными ЦП и внешние устройства.

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

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

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

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

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

Алгоритмы. Императивный подход. О понятии алгоритма. Декларативный подход

Методика организации учебного процесса по разделу Алгоритмы

. и циклические программы; создавать несложные программы обработки одномерных . понятий, закономерностей, умение выделять характерные признаки . ошибки т п 1 Понятие алгоритма и его свойства 2 - Изучение понятия алгоритма, и его свойства - Лекция Конспект лекции .

Понятие об информации

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

Понятие и сущность мировоззрения. Основные типы мировоззренческих систем

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

Понятие и методы контроля финансовых рисков

. риска § 1.1. Понятие риска и его классификация § 1.2. . в организациях § 2.1. Алгоритм и принципы управления риском . о структуре, свойствах объекта и . характерны целевое назначение создаваемого денежного фонда, расходование его . другой программой, .

Читайте также:

Алгоритмы и программы реферат

Введение

Типы алгоритмов

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

Заключение

Список литературы

Похожие страницы:

Алгоритмы. Императивный подход. О понятии алгоритма. Декларативный подход

Методика организации учебного процесса по разделу Алгоритмы

Понятие об информации

Понятие и сущность мировоззрения. Основные типы мировоззренческих систем

Понятие и методы контроля финансовых рисков