Реферат на тему: «Алгоритмы и его свойства»
Скачать 142.88 Kb.
|
 Государственное бюджетное общеобразовательное учреждение «Средняя общеобразовательная школа № 717 г. Москвы» Реферат на тему: «Алгоритмы и его свойства» Выполнила: ученица 9 «А» класса Трынина Татьяна Проверил: учитель информатики Воронин Сергей Анатольевич г. Москва, 2013 г. Содержание Введение 4 1. Способы описания алгоритмов 8 2. Стадии создания алгоритма: 9 3. Определения 11 Заключение 17 Список используемой литературы 18 Приложения 19 ВведениеЗнакомство с понятием алгоритма и возможностью его изображения в виде блок-схемы. Приобретение навыков построения алгоритмов линейной и разветвляющейся структуры. Решение любой задачи на ЭВМ необходимо разбить на следующие этапы: разработка алгоритма решения задачи, составление программы решения задачи на алгоритмическом языке, ввод программы в ЭВМ, отладка программы (исправление ошибок), выполнение программы на ПК, анализ полученных результатов. Рассмотрим первый этап решения задачи - разработку алгоритма Алгоритм – описание последовательности действий (план), строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов. Вы постоянно сталкиваетесь с этим понятием в различных сферах деятельности человека (кулинарные книги, инструкции по использованию различных приборов, правила решения математических задач...). Обычно мы выполняем привычные действия не задумываясь, механически. Например, вы хорошо знаете, как открывать ключом дверь. Однако чтобы научить этому малыша, придется четко разъяснить и сами эти действия и порядок их выполнения: 1. Достать ключ из кармана. 2. Вставить ключ в замочную скважину. 3. Повернуть ключ два раза против часовой стрелки. 4. Вынуть ключ. Если вы внимательно оглянитесь вокруг, то обнаружите множество алгоритмов, которые мы с вами постоянно выполняем. Мир алгоритмов Понятность – каждая команда должна входить в систему команд исполнителя. Дискретность (от лат. discretus — разделенный, прерывистый) – это разбиение алгоритма на ряд отдельных законченных действий (шагов). В приведенных выше алгоритмах общим является необходимость строгого соблюдения последовательности выполнения действий. Попробуем переставить в первом примере второе и третье действия. Вы, конечно, сможете выполнить и этот алгоритм, но дверь вряд ли откроется. А если поменять местами, предположим, пятое и второе действия во втором примере, алгоритм станет невыполнимым. Детерминированность (от лат. determinate — определенность, точность) – любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае. Например, если к остановке подходят автобусы разных маршрутов, то в алгоритме должен быть указан конкретный номер маршрута — 5. Кроме того, необходимо указать точное количество остановок, которое надо проехать, — скажем, три. Конечность – каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения. В приведенных примерах каждое описанное действие реально и может быть выполнено. Поэтому и алгоритм имеет предел, то есть конечен. Результативность. В алгоритме должны быть предусмотрены все возможные пути решения, в том числе альтернативные. Пример: алгоритм нахождения большего из двух заданных чисел. А и. В: 1. Из числа. А вычесть число В. 2. Если получилось отрицательное значение, то сообщить, что число. В больше. 3. Если получилось положительное значение, то сообщить, что число. А больше. При всей простоте и очевидности алгоритма, не каждый сразу поймет его ошибочность. Ведь если оба числа равны, то не получится никакого сообщения. Значит, надо обязательно предусмотреть это вариант, например: 1. Из числа. А вычесть число В. 2. Если получилось отрицательное значение, то сообщить, что число. В больше. 3. Если получилось положительное значение, то сообщить, что число. А больше. 4. Если получился ноль, то сообщить, что числа равны. Массовость – один и тот же алгоритм можно использовать с разными исходными данными. Например: алгоритм приготовления любого бутерброда. 1. Отрезать ломтик хлеба. 2. Намазать его маслом. 3. Отрезать кусок любого другого пищевого продукта (колбасы, сыра, мяса). 4. Наложить отрезанный кусок на ломоть хлеба. Возможность автоматизации деятельности человека. Выполняя алгоритм, исполнитель может не вникать в смысл того, что он делает, и вместе с тем получать нужный результат. В таком случае говорят, что исполнитель действует формально (механически), т. е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции. Построение алгоритма для решения задачи из какой-либо области требует от человека глубоких знаний в этой области, бывает связано с тщательным анализом поставленной задачи, сложными, иногда очень громоздкими рассуждениями. На поиски алгоритма решения некоторых задач ученые затрачивают многие годы. Но когда алгоритм создан, решение задачи по готовому алгоритму уже не требует каких-либо рассуждений и сводится только к строгому выполнению команд алгоритма. В этом случае исполнение алгоритма можно поручить не человеку, а машине. Действительно, простейшие операции, на которые при создании алгоритма расчленяется процесс решения задачи, может реализовать и машина, специально созданная для выполнения отдельных команд алгоритма и выполняющая их в последовательности, указанной в алгоритме. Это положение и лежит в основе работы автоматических устройств, автоматизации деятельности человека. 1. Способы описания алгоритмовСловесный (для записи используются специальные формальные языки с ограниченным набором слов и строгими правилами записи. Представляет собой описание последовательных этапов обработки данных), Формульный, Словесно-формульный, Графический (изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий – Блок-схемы). Блок-схемы позволяют описать алгоритм с использованием минимального количества слов и независимо от выбранного процедурного языка. Порядок действий указывается с помощью стрелок. 2. Стадии создания алгоритма:1. Алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает (определить цель, наметить план действий). 2. Алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия (выбрать среду и объект алгоритма, детализировать алгоритм). Объект, который будет выполнять алгоритм, обычно называют исполнителем. Исполнитель - объект, который выполняет алгоритм. Назначение исполнителя точно выполнить предписания алгоритма, подчас не задумываясь о результате и целях, т.е. формально. Идеальными исполнителями являются машины, роботы, компьютеры. Компьютер – автоматический исполнитель алгоритмов. Алгоритм, записанный на «понятном» компьютеру языке программирования, называется программой. Условие – это высказывание, которое может быть либо истинно, либо ложно. Еще раз обратим внимание, что существует две формы ветвления – неполная (когда присутствует только одна ветвь, т.е. в зависимости от истинности условия либо выполняется, либо не выполняется действие) и полная (когда присутствуют две ветви, т.е. в зависимости от истинности условия выполняется либо одно, либо другое действие). Для более наглядного представления алгоритма широко используется графическая форма – блок-схема, которая составляется из стандартных графических объектов. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура. Виды алгоритмов: • Механические алгоритмы, или иначе детерминированные, жесткие (например, алгоритм работы машины, двигателя и т.п.); • Гибкие алгоритмы, например стохастические, т.е. вероятностные и эвристические. Механический алгоритм задает определенные действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый или искомый результат, если выполняются те условия процесса, задачи, для которых разработан алгоритм. • Вероятностный (стохастический) алгоритм дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата. • Эвристический алгоритм (от греческого слова “эврика”) – это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и прошлом опыте решения схожих задач. 3. Определения1. Линейный алгоритм (описание действий, которые выполняются однократно в заданном порядке); Линейный алгоритм – это алгоритм, в котором блоки выполняются последовательно сверху вниз от начала до конца. На Приложении №1 приведен пример блок-схемы алгоритма вычисления периметра Р. и площади S квадрата со стороной длины A. Блок-схема алгоритма состоит из шести блоков. Выполнение алгоритма начинается с блока 1 «Начало». Этот блок символизирует включение автомата, настройку его на выполнение алгоритма и выделение памяти под все переменные, которые задействованы в алгоритме. В алгоритме рис. 3 таких переменных три: A, Р, S. Следовательно, под каждую из них алгоритмом будет выделено по одной ячейке памяти. На этом блок 1 будет отработан. Как видно из Приложение №1, блок 1 связан вертикальной линией потока с блоком 2. Эта линия не имеет стрелки, указывавшей направление потока. Следовательно, этот поток направлен вниз. Таким образом, после выполнения блока 1 управление будет передано на блок 2. Блок 2 «Перфокарта» (см. табл. 1) показывает, что переменной A следует присвоить значение. Это означает, что в ячейку, отведенную автоматом под эту переменную, нужно поместить константу. На реальной компьютере эта константа может быть введена самыми разными способами. Способ зависит от того, как запрограммирован данный фрагмент. Можно, например, потребовать ввод константы с клавиатура или получить его из заранее подготовленного файла. Возможно, эта константа будет получена через внешние источники данных, например, от физической установки, подключенной к компьютеру. Для данного примера способ передачи константы не имеет значения, важно лишь то, что при выполнении блока 2 в ячейку с адресом А будет занесена конкретная константа. Пусть такой константой является число 5. Далее управление по линии потока передается к блоку 3 "Процесс". В этом блоке при выполнении размещенной в ней команды число 4 умножается на константу, помещенную в ячейку А (т. е. 5), и результат (т. е. 20) присваивается переменной Р (т. е. константа 20 записывается в ячейку по адресу Р). После выполнения этих операций управление передается к блоку 4. В блоке 4 аналогичным образом производится умножение значений переменной А и результат (константа 25) присваивается переменной S (в ячейку по адресу S будет занесена константа 25). После этого выполняется переход к блоку 5. При выполнении команд блока 5 выводятся (например, на экран, бумагу, во внешний файл и т. д.) значения переменных А, Р, S, которые сохранились в соответствующих ячейках к этому моменту. Понятно, что для конкретного примера А = 5 будут выведена константы 5, 20, 25, т. е. длина сторона квадрата, его периметр и площадь. Далее управление передается последнему блоку 6. В блоке б «Конец» производится освобождение ячеек памяти, которые были зарезервированы под переменные А, P, S, и алгоритм заканчивает работу. Понятно, что при новом запуске этого же алгоритма можно получить совсем другие числа. Так, если в блоке 2 переменной А присвоить значение 20, то алгоритм выдаст в блоке 5 константы 20, 80, 400. Детальное описание алгоритма рис. 3 приведено для того, чтобы показать, в какой последовательности автомат выполняет предписанные операции и как при этом меняется состояние памяти автомата, т. е. для того, чтобы объяснить суть происходящих в автомате процессов. Из сказанного нужно уяснить, что автомат выполняет предписанную ему работу шаг за шагом. Всякий шаг обрабатывается процессором. Помимо вычислений процессор при необходимости отдает команды считывавшей/записывавшей головке, что и куда записывать, откуда читать. Конечный результат следует искать в ячейках памяти, каждая из которых до окончания алгоритма имеет известный адрес и хранит записанную в нее константу. При выполнении контрольной или курсовой работы нет нужды давать столь подробное описание алгоритма. Тем не менее, описание должно быть выполнено с той степенью полноты, которая позволяет дать ясное представление о всех сторонах и особенностях алгоритмического процесса. 2. Циклический алгоритм (описание действий, которые должны повторятся указанное число раз или пока не выполнено заданное условие); Часто при решении задач приходится повторять выполнение операций по одним и тем же зависимостям при различных значениях входящих в них переменных и производить многократный проход по одним и тем же участкам алгоритма. Такие участки называются циклами . Алгоритмы, содержащие циклы, называется циклическими . Использование циклов существенно сокращает объем алгоритма. Различают циклы с наперед известным и наперед неизвестным количеством проходов. Пример 1. Рассмотрим пример алгоритма с циклом, имеющим наперед неизвестное количество проходов. Для этого решим следующую задачу. Указать наименьшее количество членов ряда натуральных чисел 1, 2, 3, ..., сумма которых больше числа К. Ссылаться на приложение в конце работы(№2) Блок-схема алгоритма решения этой задачи приведена на рис. 5. Она состоит из восьми блоков. После начала работы в блоке 2 вводится значение числа К. Далее в блоке 3 переменная i получает значение 1, т. е. значение, с которого начнется отсчет натуральных чисел. Переменная S, предназначенная для накопления сумма этих чисел, перед началом суммирования получает значение 0. После этого управление передается блоку 5. В нем при выполнении команды S = S + i производится сложение содержимого ячеек S и i, а результат записывается в ячейку S. Поскольку до операции сложения было S = 0, i = 1, то после операции будет S = 1. При записи нового значения старое содержимое ячейки S (нуль) стирается, а на его место записывается число 1. Нужно обратить внимание на то, что если бы до этой операции в блоке 3 не была выполнена команда S = 0 (записать нуль в ячейку S ), то при нахождении суммы S + 1 возникла бы ошибка, поскольку из ячейки S была бы извлечена константа, которая оказалась там после распределения памяти. После суммирования первого члена последовательности в блоке 6 выполняется проверка условия о превышении суммы S заданного числа К. Если условие 6 не выполнится, то производится переход к блоку 4, где при выполнении операции значение переменной увеличивается на 1 и становится равным 2. Теперь алгоритм вновь вернется к блоку 5 и к старому значении суммы добавит новый член 2. После этого сумма станет равной 3. В блоке б вновь проверяется условие получения требуемой суммы и т. д. Цепочка блоков 5-4 будет обрабатываться вновь и вновь до того момента, когда однажды при определенном значении переменной i, наконец, выполнится условие S > К, т. е. когда накапливаемая в таком цикле сумма впервые превысит заданное значение К. Переменная i, значение которой при очередном проходе цепочки этих блоков увеличивается на 1, играет роль счетчика этого цикла. Далее производится переход к блоку 7, где отпечатается значение количества членов ряда (извлечено и отпечатано число из ячейки i, которое там хранится в момент выполнения условия), суммы S и в блоке 8 алгоритм закончит работу. 3. Разветвляющиеся алгоритм (алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий); На практике алгоритмы линейной структуры встречается крайне редко. Чаще необходимо организовать процесс, который в зависимости от каких-либо условий проходит по той либо иной ветви алгоритма. Такой алгоритм называется разветвляющимся. В блок-схемах ветвление начинается на выходах элемента "Решение", с помощью которого в алгоритме выполняется проверка какого-либо условия. Количество ветвей тем больше, чем больше проверяемых условий. Для пояснения рассмотрим решение задачи нахождения значения функции z = y/x. На первый взгляд представляется, что алгоритм решения этой задачи имеет линейную структуру. Однако, если учесть, что делить на нуль нельзя из-за переполнения ячейки, то, во-первых, нужно из вычислений исключить вариант х = 0 и, во-вторых, проинформировать пользователя алгоритма о возникшей ошибке. Если этого не сделать, то при вычислениях может возникнуть аварийный выход до получения результата. В профессиональной практике аварийные завершения крайне нежелательны. т. к. к этому моменту уже может быть накоплено определенное количество результатов, которые окажутся необработанными и попросту пропадут. Можно привести другие примеры, когда аварийный останов компьютера может повлечь куда более серьезные последствия. Решение задачи представлено блок-схемой Ссылаться на приложение в конце работы(№3) Она состоит из 7 блоков. После начала работы алгоритм в блоке 2 требует ввода аргументов X и Y. Затем в блоке 3 производится проверка условия X = 0. Здесь автомат проверяет равна ли нули константа, введенная в ячейку с адресом X. Результатом такой проверки является ответ "Да" или «Нет». В зависимости от этого ответа выполнение алгоритма пойдет по одной или другой ветви. Если результат проверки окажется отрицательным, то на х можно делить и управление передается блоку 4. В блоке 4 будет получен результат Z, затем в блоке б значения всех трех переменных будут отпечатаны и в блоке 7 алгоритм закончит работу. Если же ответ окажется положительным, то управление будет передано блоку 4. Выполняя команду блока 4, автомат выведет сообщение "Ошибка" и затем закончит работу в том же блоке 7. 4.Вспомогательный алгоритм (подчиненный) алгоритм (процедура) – алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм. На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма. ЗаключениеПонятие алгоритма является не только центральным понятием теории алгоритмов, не только одним из главных понятий математики вообще, но одним из главных понятий современной науки. Более того, сегодня, с наступлением эры информатики, алгоритмы становятся одним из важнейших факторов цивилизации Таким образом, алгоритм - это четкая последовательность действий, направленная на достижение поставленной цели или решения задачи. Существуют несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций: это дискретность, определенность, результативность, массовость. К понятию алгоритма примыкает понятие исполнителя алгоритма, то есть, кто (что) будет осуществлять выполнения алгоритма. Исполнитель алгоритма - это человек и автомат, и животное в клетке, и станок с программным управлением, и робот-манипулятор, умеющий выполнять некоторый вполне определенный набор действий. Исполнителя характеризуют: среда; элементарные действия; система команд; отказы. Список используемой литературы1. Емельченков Е.П., Емельченков В.Е. Вычислимость. Введение в теорию алгоритмов, 2000 г.(понятие и свойства алгоритма) 2. http://wikiversity.org/wiki/Теория_алгоритмов (введение) 3. http://teacher.dn-ua.com/old_version/algoritm (приложения) 4. Основы информатики и вычислительной техники. Пробное учебное пособие для средних учебных заведений. Ч. 1. Под ред. А. П. Ершова и В. М. Монахова. - М: Просвещение, 1985.(алгоритмы) ПриложенияПриложения №1. Линейный алгоритм.  Приложение №2. Разветвляющийся алгоритм.  Приложение №3. Разветвляющийся алгоритм.  |
Добавить документ в свой блог или на сайт
Похожие:
 | Реферат по информатике и икт по теме: «Алгоритмы» Я выбрал тему учебно-методического комплекса «Алгоритмы», так как она является одной из главной тем в информатике | | Реферат по информатике и икт по теме: “ Разветвляющиеся алгоритмы” Я выбрал тему: «Разветвляющиеся алгоритмы», потому что они очень часто применяются в алгоритмизации и программировании. Без знания... |
| Реферат на тему: Нечетко-логические модели и алгоритмы | | Урок на тему: Алюминий, его физические и химические свойства (9 класс) А группы на примере алюминия. Продолжить формировать умения давать характеристику элемента по его положению в периодической системе... |
 | Реферат по дисциплине “Оценка недвижимости” на тему “Алгоритмы экономической... Алгоритмы экономической (кадастровой) оценки городских земель и территориально-экономического зонирования” | | Конспект урока по теме: «Алгоритмы» На прошлом уроке мы изучили, что такое алгоритм, исполнитель, ски, его свойства. Теперь напомните мне, что такое алгоритм… |
| Конспект урока по теме: «Алгоритмы» На прошлом уроке мы изучили, что такое алгоритм, исполнитель, ски, его свойства. Теперь напомните мне, что такое алгоритм… | | Реферат по Химии на тему: «Кремний, его свойства и аллотропные изменения.... Более 200 лет кремний используется в классической гомеопатии, очень популярен он в современной косметологии и широко используется... |
| Еще с девятого класса мы изучаем алгоритмы. И вот перейдя из десятого... Целью нашей работы является раскрыть, что такое алгоритмы, их виды и назначения, в чем заключается смысл работы с алгоритмом | | Реферат по курсу материаловедение на тему «Свойства алюминия и его сплавов» С. Алюминий имеет решётку гранецентрированного куба, устойчив при температурах от -269 С до точки плавления (660 С). Алюминий не... |
| Программа по формированию навыков безопасного поведения на дорогах... Цели урока изучить нахождение азота в природе и его свойства, вскрыть причинно-следственные связи “строение–свойства” и “свойства–применение”,... | | Реферат по дисциплине 'Гражданская оборона' на тему: «Современные средства поражения» Вс РФ и т д мы, как защитники своей Родины, должны быть готовы к ведению боевых действий в условиях применения оружия массового поражения.... |
| Реферат по дисциплине 'Гражданская оборона' на тему: «Современные средства поражения» Вс РФ и т д мы, как защитники своей Родины, должны быть готовы к ведению боевых действий в условиях применения оружия массового поражения.... | | Программа по формированию навыков безопасного поведения на дорогах... Алгоритмы и их свойства. Способы записи алгоритма(алгоритмический язык, блок-схема) |
| Конспект по теме «Алгоритмы» Цель урока: дать учащимся понятие алгоритма, изучить свойства алгоритмов, применение алгоритмов в жизнедеятельности человека | | Планирование изучения темы «Обобщение понятия степени» 13 уроков... Обобщить понятие квадратного корня на корень n-й степени и рассмотреть его свойства |
