Основы алгоритмизации задач

Теоретический блок

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

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

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

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

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

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

Эти трудности привели к созданию так называемых языков программирования «высокого уровня».

Третье поколение – самое «обширное» поколение языков. Это универсальные языки высокого уровня, с помощью которых удается решать задачи из любых областей. Начало оно ведет с 1955 года с появлением языка ФОРТРАН (FORmulaTRANslator – переводчик формул), первого компилируемого языка, созданного Джимом Бэкусом в 50-е годы. ФОРТРАН продолжает активно использоваться во многих организациях и в сегодняшние дни.

В 1960 году появился АЛГОЛ (ALGOritmicLanguage- алгоритмический язык). Он был призван заменить Фортран, но из-за более сложной структуры не получил широкого распространения.Однако он долгое время пользовался определенной популярностью в программистских кругах.

1965 году был создан один из наиболее популярных и поныне языков программирования – БЭЙСИК (BASIC – Beginner’sAllpurposeSymbolicInstructionCode – дословно: «многоцелевой код символической инструкции для начинающих»). Широкое распространение БЭЙСИК получил на персональных компьютерах. Он создавался в качестве учебного языка и очень прост в изучении. На нынешний день существует несколько достаточно мощных версий этого языка.

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

В 1980 году появился язык ADA (Ада) – один из самых мощных языков программирования. Он принят в качестве основного языка на вычислительных центрах министерства обороны США. Структура самого языка похожа на Паскаль. В нем имеются средства разграничения доступа к различным уровням спецификаций, доведена до предела мощность управляющих конструкций. Назван по имени леди Огасты Ады Байрон, дочери английского поэта Байрона.

В настоящее время используется еще один мощный язык программирования – С (Си). Данный язык был создан в лаборатории Bellи первоначально не рассматривался как массовый. Он планировался для замены ассемблера, чтобы иметь возможность создавать столь же эффективные и компактные программы и в то же время не зависеть от конкретного типа процессора.

Четвертое поколение языков – это языки управления программным обеспечением, или, как их еще называют, «генераторы программ». Для примера можно привести такие языки, как Clipper, dBase, SuperCalc.

Все названные языки являются процедурными, в противоположность языкам «Пятого поколения», которые являются декларативными. Основные языки этого поколения – LISP – язык обработки списков /ЛИСП/ и PROLOG – программирование в терминах логики /ПРОЛОГ/.

ЛИСП появился в 1961 году. Он ориентирован на структуру данных в форме списка и позволяет организовывать эффективную обработку больших объемов текстовой информации. LISP является очень мощным и многообразным языком, но он может оказаться достаточно большим и громоздким. ПРОЛОГ создан в 1973 году Аланом Колмероэ. Программа на этом языке строится из последовательности фактов и правил, а затем формулируется утверждение, которое Пролог будет пытаться доказать с помощью введенных правил. При решении задач на этих языках от программиста требуется описать, ЧТО надо сделать, а не КАК это следует делать. Об этом позаботится сама система (ЛИСП или ПРОЛОГ).

Таким образом, все языки программирования можно разделить на три категории: языки НИЗКОГО уровня – машинные языки и языки Ассемблера, то есть языки первого и второго поколения; ВЫСОКОГО уровня – все процедурные языки, то есть языки третьего и четвертого поколений и СВЕРХВЫСОКОГО уровня – языки пятого поколения.

Говорят, что программирование – это искусство получения ответов от машины, и, если мы решили применить компьютер, нам предстоит пройти три основных этапа:

1. Ясно и точно установить, что же должно быть сделано.

2. Установить точно определенную последовательность действий, ведущую к желаемому результату, то есть, предложить алгоритм.

3. Выразить алгоритм в виде понятном для машины.

Первый этап носит название СИСТЕМНЫЙ АНАЛИЗ. Второй этап – КОНСТРУИРОВАНИЕ ПРОГРАММЫ. Третий этап – ПРОГРАММИРОВАНИЕ.

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

Чтобы не было недоразумений, введем термины, которые будем применять в дальнейшем.

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

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

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

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

Процесс (вычисление) – действие, которое можно разложить на составные части. Если эти части во времени следуют строго друг за другом и никакие две части не выполняются одновременно, то процесс называется последовательным.

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

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

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

Каждое такое предписание называется командой. Порядок команд в алгоритме очень важен.

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

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

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

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

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

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

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

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

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

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

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

Каждый исполнитель должен однозначно понимать правило выполнения каждого действия алгоритма. Это называется свойством однозначности алгоритма.

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

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

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

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

· На алгоритмическом языке (псевдокод) – то есть на специальном языке.

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

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

<имя переменной>:=<выражение>;

Оператор присваивания выполняет изменение значения переменной. При операторе присваивания вычисляется <выражение> в правой части, результат записывается в <переменную>.Тип выражения должен быть совместим по присваиванию с переменной.

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

· В виде программ для ЭВМ – значит на любом алгоритмическом языке, понятном для машины, когда исполнителем является компьютер. Широко известны такие языки программирования как Паскаль, Дельфи, Пролог, Си и т.д.

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

 

Элементы блок-схем

Название процесса Вид блок-схемы Описание действия
  Терминатор  
 
 

 

 

   Начало, конец алгоритмов
  Данные
 

 

 

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

 

Классификация алгоритмов

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

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

 
 

 

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

 

Разветвляющийся алгоритм – это алгоритм, в котором последовательность операций определяется проверкой условия.

 
 

 

 

   Если условие A>Bверно, то выполняется группа операторов ОПЕРАТОР 1, в противном случае – группа операторов ОПЕРАТОР 2(условный оператор)  

Циклический алгоритм – это алгоритм, в котором неоднократно повторяются одни и те же предписания.

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

 
 

 

 Пока будет выполненоI£N, выполняется группа операторовОП.1. Оператор цикла с предусловием выполняется до тех пор, пока остается истинным условие цикла. Как только значение условия становится ложным, цикл прекращает выполняться.  
    Выполняется группа операторов ОП.1до тех пор, пока не будет выполнено условие I>N. В отличие от цикла с предусловием, выход из цикла с постусловием осуществляется при истинности условия. Этот цикл должен выполниться хотя бы один раз. Данный оператор цикла выполняется до тех пор, пока не станет истинным условие.  
  Для каждого I от 1 до N выполняется группа операторов ОП.1 Если число повторений цикла известно, используется цикл, для которого нет необходимости принудительно увеличивать значение параметра цикла. Такое увеличение при цикле с параметром производится автоматически

Примеры:

Линейный алгоритм

Вычислить функциюzпо формуле z=ax2+b+cos(ax2+b)-tg(ax2+b)

1) Cоставить математическое уравнение данной задачи:

z=t+cos-tgt, где t=ax2+b

2) Составление алгоритма:

 

На алгоритмическом языке Графический вид алгоритма
алг вычисление функции z аргa, b, x   резz   нач ввод a, b, x t:=ax2+b z:=t+cost-tgt выводx, z кон  

Разветвляющийся алгоритм

Вычислитьфункцию У по формуле:

1) Составить математическое уравнение задачи:

если , тогда

если , тогда

 

2) Составление алгоритма:

На алгоритмическом языке Графический вид алгоритма
алг вычисление функции у аргx   рез у   нач если то иначе все кон  

 

Циклический алгоритм

Вычислить (n=1,…,10).

Составление алгоритмов:

На алгоритмическом языке Графический вид алгоритма
  алг сумма   цикл аргn резS дляn:=1 до 10 шаг 1 нц S:=S+sqr(n) кц кон  

 

В графическом виде алгоритма представлена блок-схема цикла с параметром. Блок-схему цикла с предусловием и постусловием попытайтесь построить сами на уроках СРСП.

Основы алгоритмизации задач

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

Транслятор(англ. translator - переводчик) – это программа-переводчик. Она преобразует программу, написанную на одном из языков высокого уровня, в программу, состоящую из машинных команд.

Трансляторы реализуются в виде компиляторов или интерпретаторов. С точки зрения выполнения работы компилятор и интерпретатор существенно различаются.

Компилятор (англ. compiler – составитель, собиратель) читает всю программу целиком, делает ее перевод и создает законченный вариант программы на машинном языке, который затем и выполняется (файл с расширением .ЕХЕ).

Интерпретатор(англ. interpreter – истолкователь, устный переводчик) переводит и выполняет программу строка за строкой.

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

Turbo Pascal ориентирован либо на компиляцию, либо на интерпретацию. Для разработки тестирования программы можно воспользоваться интерпретатором, а затем откомпилировать, а затем откомпилировать отлаженную программу, чтобы повысить скорость ее выполнения.

Язык программирования Паскаль получил свое название в честь великого французского математика и физика Блеза Паскаля, который в 1642 году изобрел машину для арифметических операций, так называемое «паскалево колесо». В конце 1968 г. профессор Никлаус Вирт и его сотрудники из швейцарского федерального института технологии в Цюрихе разработали первую версию языка Паскаль. Спустя два года – первый вариант компилятора. В 1971 г. Н.Вирт выпустил описание языка.

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

Запуск языка «Паскаль»

Запуск интегрированной среды версии компилятора BorlandPascal 7.0, которая работает в защищенной режиме DOS, осуществляется следующим образом:

а) если среда программирования инсталлирована в системе Windows:

Пуск→Программы→ Borland Pascal→ BP(Borland Pascal)

б) если среда программирования не инсталлирована в системе Windows или вы работаете в системе DOS: