Файл: Алгоритмизация как обязательный этап разработки программы (Алгоритмизация).pdf
Добавлен: 29.03.2023
Просмотров: 277
Скачиваний: 2
ВВЕДЕНИЕ
Сегодня при решении той или иной задачи на компьютере сначала следует попытаться подобрать одно из существующих программных средств (например, математические либо статистические пакеты, электронные таблицы, системы управления базами данных и др.) и только в том случае, если эти средства не позволяют решить поставленную задачу, использовать универсальные языки программирования. Для этого необходимо освоить основы алгоритмизации и программирования. Процесс создания программного продукта весьма трудоемок, так на сегодняшний день существует значительный объем программного обеспечения, имеющий сотни тысяч операторов. Современному специалисту, работающему в данной области необходимо иметь четкое понимание существующих методов, принципов и технологий проектирования, реализации, анализа и тестирования программных систем. Совершенствование руководства и повышение качества управления во всех сферах деятельности являются проблемами, важность и актуальность которых по мере развития общества и научно-технического прогресса все в большей степени возрастают. Основной путь решения этих проблем состоит в автоматизации различных видов деятельности на основе применения компьютерной техники и создание автоматизированных систем, в том числе автоматизированных систем управления (АСУ) различных иерархических уровней. Появление средств автоматизации немыслимо без разработки соответствующего математического обеспечения, важнейшую составную часть которого представляют алгоритмы прикладных задач. Являясь результатом труда огромной армии алгоритмистов, в настоящее время алгоритмы стали не только объектом непосредственной разработки и реализации в конкретных технических и информационных системах, но и предметом изучения во многих учебных заведениях, объектом продолжающихся с момента появления первых ЭВМ исследований и научных публикаций. Благодаря бурному развития компьютерной техники, внедрению ее в разнообразные области человеческой деятельности, резкому повышению уровня компьютерной грамотности населения и появлению огромного количества персональных ЭВМ, используемых не только в офисах, но и в быту, алгоритмизация прикладных задач перестала быть уделом профессиональных математиков, и сейчас в роли алгоритмистов выступают специалисты самых разных, практически любых профессий. Сталкиваясь с необходимостью разработки алгоритмов, эти специалисты ощущают потребность в литературе методического характера. В процессе поиска методических материалов обнаруживается, что в имеющейся литературе по алгоритмизации прикладных задач.
1. АЛГОРИТМИЗАЦИЯ
В современном мире человеку приходится решать задачи с использованием компьютера. Решение любой задачи предполагает наличие алгоритма, т.е. точного предписания последовательности действий, приводящих к получению результата. На основе алгоритма составляется программа, т.е. запись алгоритма решения задачи в виде, пригoдном для исполнения его на компьютере. Отсюда следует, что сущность процесса решения задачи с помощью компьютера — это разработка алгоритма. Процесс составления алгоритмических предписаний называется алгоритмизацией. Роль алгоритмизации в жизни современного общества определяется не только техническими аспектами ее использования. Алгоритмический подход невозможно отделить от повседневной жизни людей, от их обычной работы. В подавляющем большинстве случаев результат деятельности человека зависит от того, насколько четко он знает алгоритмическую сущность своих действий: что делать в каждый момент, в какой последовательности, каким должен быть итог действий. Это в определенной степени зависит от его умения составлять и использовать алгоритмы. Алгоритмизация учебного процесса, разработка и реализация алгоритмов для учащихся и алгоритмов для обучающих лиц (или обучающих машин). Алгоритм — одно из важнейших понятий информатики. Алгоритм — точное, однозначно понимаемое предписание о выполнении в указанной последовательности операций (действий), приводящих к решению любой из задач, принадлежащих к некоторому классу (или типу). Предписываемые операции (действия) должны быть доступны адресату. Они могут быть как элементарными (простейшими), так и сложными, основанными на элементарных. К алгоритмам предъявляются требования определённости (конструктивности), т.е. однозначности предписываемых действий и операций; результативности, предполагающей, что при выполнении конечного числа операций будет получен искомый результат; массовости, означающей, что алгоритм применим к решению целого класса задач. В процессе решения задачи по алгоритму должны присутствовать: само предписание, состоящее из указаний (команд) о выполнении действий или операций над определёнными объектами и обычно фиксированное на тех или иных материальных носителях; некоторая система-исполнитель (человек или машина), к которой эти указания адресованы и которая их выполняет; объекты, на которые направлены действия или операции и которые под их воздействием преобразуются. Примером алгоритма может служить известный арифметический способ сложения двух положит, чисел «столбиком». Этот алгоритм можно представить в виде след. системы указаний: выделить в слагаемых разряды единиц и сложить единицы, если полученная сумма меньше 10, записать её в разряде единиц под нижним числом, если сумма больше или равна 10, записать в разряде единиц только кол-во единиц; выделить в слагаемых разряд десятков и записать полученный при сложении единиц десяток над разрядом десятков 1-го (верхнего) слагаемого; сложить десятки и т. д. Аналогичные указания даются для сложения единиц др. разрядов числа. Системой-исполнителем данного алгоритма может быть, как ЭВМ, так и человек. В теорию и практику обучения понятие алгоритма вошло в кон. 50-х гг. в связи с развитием программированного обучения и применением обучающих машин. Участие человека в учебном процессе накладывает ряд ограничений на использование алгоритмов. При создании алгоритма для ЭВМ составителю алгоритма точно известен набор доступных ей операций. Возможности человека определяются его предыдущим приобретённым учебным опытом, творческими данными и др. индивидуальными факторами, которые полностью учесть практически невозможно. Поэтому при разработке алгоритмов для человека требования конструктивности и результативности алгоритмов выполняются с известным приближением. Алгоритмы, предназначенные для использования их человеком, иногда называют предписаниями алгоритмического типа, а чаще — просто предписаниями. Возможность решения задач с помощью таких предписаний носит вероятностный характер и зависит от целого ряда индивидуальных особенностей исполнителя (его интеллектуального уровня, внимания, эмоционального состояния и др.). В математике для решения типовых задач мы используем определенные
правила, описывающие последовательности действий. Например, правила сложения дробных чисел, решения квадратных уравнений и т. д. Обычно любые инструкции и правила представляют собой последовательность действий, которые необходимо выполнить в определенном порядке. Для решения задачи надо знать,что дано, что следует получить и какиедействия и в каком порядке следует для этого выполнить. Предписание, определяющее порядок выполнения действий над данными с целью получения искомых результатов, и есть алгоритм. Алгоритм заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов. Это не определение в математическом смысле слова, а, скорее, описание интуитивного понятия алгоритма, раскрывающее его сущность. Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком", знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе. Понятие алгоритма является не только одним из главных понятий математики, но одним из главных понятий современной науки. Более того, с наступлением эры информатики алгоритмы становятся одним из важнейших факторов цивилизации. Исполнитель алгоритма это некоторая абстрактная или реальная(техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом. Исполнителя характеризуют: • среда; • элементарные действия; • система команд; • отказы. Среда (или обстановка) это "место обитания" исполнителя. Например, для исполнителя Робота из школьного учебника среда — это бесконечное клеточное поле. Стены и закрашенные клетки тоже часть среды. А их расположение и положение самого Робота задают конкретное состояние среды. Система команд. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды. Например, команда Робота "вверх" может быть выполнена, если выше Робота нет стены. Ее результат смещение Робота на одну клетку вверх. После вызова команды исполнитель совершает соответствующее элементарное действие. Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды. Обычно исполнитель ничего не знает о цели алгоритма. Он выполняет все полученные команды, не задавая вопросов "почему» и "зачем". В информатике универсальным исполнителем алгоритмов является компьютер.
2. ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВА И ВИДЫ АЛГОРИТМОВ
Оснoвным в процессе программирования является разработка алгоритма. Это один из наиболее сложных этапов решения задачи с использованием ЭВМ. Алгоритм — описанная на некотором языке точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение поставленной задачи. Слово «Алгоритм» происходит от algorithmi - латинского написания имени аль-Хорезми, под которым в средневековой Европе знали величайшего математика из Хорезма (город в современном Узбекистане) Мухаммеда бен Мусу, жившего в 783-850 гг. В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных. Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Сoздание алгоритма, пусть даже самого простого, - процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. Другое дело - реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в существо дела, а возможно, и не способен его понять. Такой субъект или объект принято называть формальным исполнителем. Примером формального исполнителя может служить стиральная машина-автомат, либо мультиварка, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее необходимые компоненты. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являются различные автоматические устройства, и компьютер в тoм числе. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совершать исполнитель, называются его допустимыми действиями. Совокупность допустимых действий образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя. Данное выше определение алгоритма нельзя считать строгим - не вполне ясно, что такое «точное предписание» или «последовательность действий, обеспечивающая получение требуемого результата». Поэтому обычно формулируют несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций.
Алгоритм решения задачи имеет ряд обязательных свойств:
1. Дискретность - алгоритм должен представлять процесс решения задачи как последовательное выполнение простых или ранее определенных шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
2. Определеннoсть - каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря именно этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
3. Результативность или конечность - алгоритм должен приводить к решению задачи за конечное число шагов.
4. Массовость - алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
5. Формализoванность – предписания алгоритма должны быть записаны на некотором формальном (искусственном) языке. В алгоритме отражаются логика и способ формирования результатов решения с указанием необходимых расчетных формул, логических условий, соотношений для контроля достоверности выходных результатов. В алгоритме обязательно должны быть предусмотрены все ситуации, которые могут возникнуть в процессе решения комплекса задач. Алгоритм решения комплекса задач и его программная реализация тесно взаимосвязаны. Специфика применяемых методов проектирования алгоритмов и используемых при этом инструментальных средств разработки программ может повлиять на форму представления и содержание алгоритма обработки данных. Алгоритм применительно к вычислительной машине – точное предписание, т.е. набор операций и правил их чередования, при помощи которого, начиная с некоторых исходных данных, можно решить любую задачу фиксированного типа. Виды алгоритмов как логико-математических средств отражают указанные компоненты человеческой деятельности и тенденции, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом: 1) Механические алгоритмы, или иначе детерминированные, жесткие (например алгоритм работы машины, двигателя и т.п.); 2) Гибкие алгоритмы, например стохастические, т.е. вероятностные и эвристические. Механический алгоритм задает определенные действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый или искомый результат, если выполняются те условия процесса, задачи, для которых разработан алгоритм. 3) Вероятностный или стoхастический алгоритм дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата. 4) Эвристический алгoритм (в переводе с греческого слова «эврика») – это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений. 5) Линейный алгоритм – набор команд или указаний, выполняемых последовательно во времени друг за другом. 6) Разветвляющийся алгоритм – алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов. 7) Циклический алгоритм – алгоритм, предусматривающий многократное повторение одного и того же действия либо одних и тех же операций над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Цикл программы – последовательность команд (серия, тело цикла), которая может выполняться неоднократно (для новых исходных данных) до выполнения некоторого условия. Вспомогательный (подчиненный) алгоритм (процедура) – алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях при наличии подобных последовательностей указаний или команд для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм. Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Например, записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида). Алгоритм может быть следующим: