Lektsia_informatika_4

11

© Лекции доцента Черкезова С.Е. по учебному курсу “Информатика”

Лекция № 4

Основы алгоритмизации и программирования

Основные вопросы лекции:

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

2. Виды алгоритмов.

3. Основные понятия программирования.

4. Языки программирования.

5. Этапы разработки программного обеспечения.

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

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

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

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

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

2. Каждый алгоритм строится в расчете на некоторого исполнителя. Для того чтобы исполнитель мог решить задачу по заданному алгоритму, необходимо, чтобы он  был в состоянии понять и выполнить каждое действие, предписываемое командами алгоритма. Такое свойство алгоритмов называется определенностью (или точностью) алгоритма. (Например, в алгоритме указано, что надо взять 3—4 стакана муки. Какие стаканы, что значит 3—4, какой муки?)

3. Еще одно важное требование, предъявляемое к алгоритмам, - результативность (или конечность) алгоритма. Оно означает, что исполнение алгоритма должно закончиться за конечное число шагов.

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

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

Виды алгоритмов

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

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

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

Псевдокод – это язык со свободным синтаксисом, близким к естественному языку или языкам программирования, обладающий свойствами:

• краткости записи алгоритмов;

• понятности для ограниченного круга людей;

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

• возможности использования собственных символьных конструкций;

• возможности представления алгоритма с произвольной степенью детализации.

Графическая запись алгоритмов в виде блок-схем (схем алгоритмов) характеризуется следующими свойствами:

• использованием графических символов, математических записей и записей на естественном языке;

• наглядностью;

• пониманием записи алгоритма любым человеком, знакомым с алгоритмами;

• возможностью представления алгоритма с произвольной степенью детализации

• использованием простых правил описания последовательностей действий.

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

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

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

При графическом описании алгоритма принято использовать стандартные графические символы приведенные в таблице

№	Название блока	Вид блока	Описание блока
1.	Пуск, завершение		Начало, конец, вход и выход в подпрограммах.
2.	Действие		Вычислительное действие или их последовательность.
3.	Условие		Проверка условий, переход к действию по условию.
4.	Данные		Ввод данных, вывод результатов выполнения действий.

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

Линейный алгоритм при каждом исполнении предписывает однократное выполнение всех действий алгоритма в определенной последовательности.

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

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

Графические изображения различных видов алгоритмов приведены ниже

 

 

 

 

 

а) Линейный б) Ветвящийся в) Циклический

алгоритм алгоритм алгоритм

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

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

Команда ветвления, как и любая другая, может быть:

• Записана на естественном языке;

• Изображена в виде блок-схемы;

• Закодирована на языке программирования.

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

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

Цикл, как и любая другая алгоритмическая структура, может быть:

• Записан на естественном языке;

• Изображен в виде блок-схемы;

• Закодирован на языке программирования.

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

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

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

Основные понятия программирования

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

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

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

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

Компилятор (транслятор) – программа, производящая компиляцию.

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

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

Объектный код – запись программы в форме, которая может быть обработана аппаратными средствами. Имеет расширение .obj.

Исполняемый файл – программа (.exe), готовая к исполнению.

По способу получения машинных кодов языки программирования делятся на 3 типа:

1) Компилируемые. Например, Fortran, Pascal, Си. Этапы компиляции изображены на схеме.

2) Интерпретируемые. Например, Basic. Интерпретатор (программа) читает строку исходной программы, формирует машинные коды и сразу их исполняет.

3) Интерпретируемые с элементами компиляции. Например, Форт.

Языки программирования

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

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

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

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

Также система программирования может включать в себя:

• библиотеки стандартных подпрограмм,

• отладчик

• компоновщик

• и другие сервисные средства.

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

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

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

Языки программирования
Процедурные	Функциональные	Логические	Объектно-ориентированные

Ведущими разработчиками систем программирования в настоящее время являются фирмы Microsoft и Borland International.

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

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

Двоичный язык - в настоящее время программистами не применяется.

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

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

Язык Макроассемблера - расширение языка Ассемблера. Позволяет определять и использовать новые, более мощные команды.

Язык программирования C - разработан в начале 70-х. Сочетает достоинства современных высокоуровневых языков (в части структур данных и управляющих структур) и возможность доступа  к аппаратным средствам машины на уровне языка Ассемблера. Однако синтаксис языка таков, что затрудняет программирование и понимание составленных программ.

Язык Basic (Beginner’s All-purpose Symbolic Instruction Code-многоцелевой язык символических инструкций для начинающих). Разработан в 1964 г. для использования новичками. Первоначально работа велась только в режиме интерактивной (диалоговой) интерпретации. В смысле строгости и стройности является антиподом языка Pascal. Несмотря на это, Basic очень популярен, в особенности на ПК. Существует множество его диалектов, несовместимых между собой. Современные диалекты Basic’а весьма развиты и мало чем напоминают  своего предка.

Язык Fortran (Formula Translator) разработан в 1956 г. Считается “рабочей лошадью” научных работников за счет своей “приспособленности” к ведению сложных вычислений и широко используется до настоящего времени, несмотря на свою ограниченность и ”корявость”.

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

Язык  Modula-2 создан в 1979 г. также Норбертом Винером. По существу - развитие Паскаля. Его особенности состоят в высокой модульности программ и наличии средств описания параллельных процессов.

Язык Ada разработан в 1979 г. по заказу Министерства обороны США для использования во встроенных системах с управляющими ЭВМ, что требует режима поддержки режима реального времени. Назван в честь Августы Ады Лавлейс (дочери Байрона), которая была ассистентом Чарльза Бэббиджа и по праву считается первым в мире программистом. Рассматривается как универсальный язык программирования. Данный язык вводит строгую дисциплину программирования, что препятствует написанию “плохих программ”. Несмотря на достоинства, программистов отталкивает его громоздкость.

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

Существует ряд языков, некогда популярных, но утративших свои позиции в настоящее время:

• PL/1 - конгломерат языков Fortran, Algol Cobol –предназначен для больших ЭВМ и на ПК практически не используется. Язык достаточно сложен и имеет такие свойства, которые не стимулируют написание корректных, надежных и наглядных программ;

• Cobol - ориентирован на обработку коммерческой информации.

• Snobol - предназначен для обработки текстовых данных.

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

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

Примером функционального языка является язык LISP (List Processing-обработка списков) Разработан и реализован в Массачусетском технологическом институте в 1959 г. Рассматривается специалистами как основной язык программирования систем искусственного интеллекта.

Логическое программирование. Логика и программирование долгое время были непересекающимися областями исследований. Только в 1973 впервые было опубликовано описание языка PROLOG (PROgramming in LOGic- программирование в терминах логики) Центральным понятием в логическом программировании является отношение. Программа представляет собой совокупность определений отношений между объектами и цели. В логическом программировании нужно только специфицировать факты, на которых алгоритм основывается, а не определять последовательность шагов, которые требуется выполнить. Логические программы отличаются принципиально низким быстродействием. Так как вычисления осуществляются методом проб и ошибок (посредством поиска с возвратами). В настоящее время для ПК существует около двух десятков реализации PROLOG’а, некоторые из которых оформлены в виде интегрированных сред.

Объектно-ориентированное программирование. Корни объектного ориентирования уходят в одну из ветвей логики, в которой первичной является не отношение, а объект. Прототипом объектно-ориентированного программирования явился язык SIMULA-67. Но оформилось оно в самостоятельный стиль программ ирония с появлением языка (SMALLTALK-1972 г.), первоначально предназначенного для реализаций функций машинной графики. Этот стиль программирования характеризуется богатыми графическими возможностями и средой программирования, развитой модульной структурой программ. Именно модульность упрощает разработку сложных программных продуктов. Как пример объектно-ориентированного языка можно назвать Visual Basic  и Delfi.

Сейчас уже невозможно представить себе жизнь в мире ПК без Интернета. Язык гипертекстовой разметки - HTML (Hyper Text Markur Language) позволяет создавать программы, с помощью которых можно осуществлять навигацию по информационным ресурсам глобальных сетей.

Этапы разработки программного обеспечения

1 Формулирование задачи.

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

2 Физический и математический анализ.

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

3 Численный анализ.

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

4 Решение контрольного примера. 7

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

5 Построение принципиальной схемы алгоритма и структуры данных.

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

6 Детализация алгоритма и построение блок-схем.

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

7 Написание текста программы на алгоритмическом языке.

8 Отладка программы.

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

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

2) Семантические (смысловые, run-time error, ошибки выполнения) ошибки. Они связаны с неправильным содержанием действий или использованием недопустимых значений величин. Данные ошибки приводят к: прекращению выполнения программы и выдаче предупреждений; отсутствию признаков выполнения программы из-за ее “зацикливания”; появлению непредусмотренной формы или содержания печати результатов; потере точности вычислений; большому времени выполнения вычислений или других операций.

9 Тестирование программы.

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