Разработка алгоритмов

 

 

 

Оглавление

Введение            3

Глава 1. Представление о алгоритмах       5

1.1 Что такое алгоритм?        6

1.2 Свойства и виды алгоритмов       7

Глава 2. Разработка алгоритмов                 8

2.1 ЭВМ - исполнитель алгоритмов                8

2.2 Формы представления                9

2.3 Оптимизация  алгоритмов 11

Глава 3. Практическое задание               15

3.1 Описание программы              15

3.2 Код программы                14

Заключение                 19

Литература                  20

 

Введение

 

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

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

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

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

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

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

«Провести исследование на тему Алгоритмы, их способы записи и формы представления».

Исходя из поставленной цели, автор выдвинул следующие задачи:

• Познакомиться с понятием «алгоритм»;
• Узнать о свойствах алгоритма, его виды;
• Узнать где применяются алгоритмы;
• Научить записывать, строить алгоритм, определять наличие алгоритмов;
• Узнать о формах представления алгоритмов;
• Научиться использовать алгоритмы на практике. Для этого выполним практическое задание: написать программу в компиляторе Pascal, используя способы алгоритмизации.

 

 

 

Глава 1. Представление об алгоритмах

1.1 Что  такое алгоритм?

 

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

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

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

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

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

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

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

 

1.2 Свойства и виды алгоритма

Общие свойства, которыми обладает любой алгоритм:

Понятность - исполнитель алгоритма должен знать, как его выполнять;

Конечность - выполняемый алгоритм должен приводиться к результату за конечное число шагов;

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

Массовость - один и тот же алгоритм можно использовать с различными исходными данными.

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

Однако разъясняя понятие  алгоритма, часто приводят примеры “бытовых алгоритмов”: вскипятить воду, открыть дверь ключом, перейти улицу и.т.д.: рецепты приготовления какого-либо лекарства или кулинарные рецепты являются алгоритмами. Но для того, чтобы приготовить лекарство по рецепту, необходимо знать фармакологию, а для приготовления блюда по кулинарному рецепту нужно уметь варить. Между тем исполнение алгоритма – это бездумное, автоматическое выполнение предписаний, которое в принципе не требует никаких знаний. Если бы кулинарные рецепты представляли собой алгоритмы, то у нас просто не было бы такой специальности – повар.

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

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

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

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

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

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

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

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

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

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

 

Глава 2. Разработка алгоритмов

2.1 ЭВМ - исполнитель  алгоритмов

Обсуждение методических вопросов изучения темы «Алгоритмы работы с величинами» будем проводить  в программистском аспекте. Составление  любой программы для ЭВМ начинается с построения  алгоритма. Как известно, всякий алгоритм (программа) составляется для конкретного исполнителя, в рамках его системы команд. О каком же исполнителе идет речь в теме «программирование для ЭВМ»? Ответ очевиден: исполнителем является компьютер. Точнее говоря, исполнителем является комплекс «ЭВМ, + система программирования и (СП)». Программист составляет программу на том языке, на который ориентирована СП. Иногда в литературе по программированию такой комплекс называют «виртуальной ЭВМ». Например, компьютер с работающей системой программирования на Бейсике называют «Бейсик-машина»; компьютер с работающей системой программирования на Паскале называют «Паскаль-машина и т. п. Схематически это изображено на рис. 1.

Рис. 1. Взаимодействие программиста с компьютером

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

Процесс программирования делится на три этапа:

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

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

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

 

2.2 Формы представления

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

• словесной;
• графической;
• программной.

Рассмотрим  их:

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