Структурное программирование. 2

                                                          ПЛАН 

1. Введение ………………………………………………………………… 2
2. Алгоритм и программа: ………………………………………………… 2

а. свойства алгоритма; ………………………………………………….. 2

б. форма  алгоритма: …………………………………………………….. 3

3. Способы  представления в алгоритмы: …………………………………. 3

а. графический; ………………………………………………………….. 4

б. неформальный; ……………………………………………………….. 4

в. запись на алгоритмическом языке: ………………………………….. 4

   4. Сложность алгоритмов ………………………………………………….. 5

   5. Жизненный цикл программного обеспечения …………………………. 7

   6. Заключение ……………………………………………………………..... 9

   7. Список литературы ……………………………………………………… 10 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

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

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

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

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

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

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

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

2. Результативность: алгоритм должен приводить к  получению результата за конкретное  число шагов ( при делении 1 на 3 получается периодическая дробь  0,3333(3), для достижения конечного  результата надо оговорить точность получения этой дроби, например, до 4 знака после запятой). 

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

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

Алгоритмы можно представить в следующих  формах: 

1) словесное  описание алгоритма. 

2) графическое  описание алгоритма. 

3) с  помощью алгоритмического языка  программирования 

СПОСОБЫ ПРЕДСТАВЛЕНИЯ АЛГОРИТМОВ  

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

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

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

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

Существует  три основных способа представления  алгоритмов:

1) графический; 

2) неформальная  языковая (алгоритмическая) нотация  (запись);

3) запись  на алгоритмическом языке.  

Любая форма записи (представления) алгоритма должна обеспечивать свойства алгоритма: дискретности, конечности, определенности, массовости.  

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

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

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

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

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

Очевидно, способ представления алгоритмов на алгоритмических языках/языках программирования играет ведущую роль. Существует большое  количество языков программирования. Одни из них широко распространены: Basic, Pascal, C/C++, Modula, Fortran. Другие же имеют специальное назначение: Prolog, Forth, Lisp. Некоторые языки сыграли заметную роль в программирования, но сейчас не используются. Примером является язык Algol. Именно этот язык послужил основой для разработки более совершенных языков, таких как Паскаль, Си и других. Алгол использовался также как алгоритмический язык для записи алгоритмов, в том числе в качестве автокода. Можно также отметить такой важный язык программирования для научно-технических расчетов: Фортран.

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

В 1985 году основатель школьной информатики академик А.П.Ершов предложил для записи алгоритмов новый алгоритмический  язык, который назвали школьным алгоритмическим  языком. Иногда этот язык называют Е-языком, в честь его создателя. Но это  называние является неформальным. 

Сложность алгоритмов 

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

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

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

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

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

Пример 1. Оценим временную сложность алгоритма  вычисления факториала целого положительного числа.  

Function Factorial(x:Integer): Integer;  

Var m,i: Integer;  

Begin m:=l;  

For i:=2 To x Do m:=ro*i;  

Factorial:=m  

End;  

Подсчитаем  общее число операций, выполняемых программой при данном значении x. Один раз выполняется оператор m:=1; тело цикла (в котором две операции: умножение и присваивание) выполняется х — 1 раз; один раз выполняется присваивание Factorial:=m. Если каждую из операций принять за единицу сложности, то временная сложность всего алгоритма будет 1 + 2 (x — 1) + 1 = 2х Отсюда понятно, что в качестве параметра следует принять значение х. Функция временной сложности получилась следующей:  
 

Tα(V)=2V.  

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

Пример 2. Вычисление скалярного произведения двух векторов А = (a1, a2, …, ak), В = (b1, b2, …, bk).  

АВ:=0;  

For i:=l To k Do AB:=AB+A[i]*B[i];  

В этой задаче объем входных данных п = 2k. Количество выполняемых операций 1 + 3k = 1 + 3(n/2). Здесь можно взять V= k= п/2. Зависимости сложности алгоритма от значений элементов векторов А и В нет. Как и в предыдущем примере, здесь можно говорить о линейной зависимости временной сложности от параметра данных.  

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

Вторая  проблема связана с классификацией алгоритмов по временной сложности. Функция Tα(V) обычно растет с ростом V. Как быстро она растет? Существуют алгоритмы с линейной зависимостью Тα от V (как это было в рассмотренных нами примерах), с квадратичной зависимостью и с зависимостью более высоких степеней. Такие алгоритмы называются полиномиальными. А существуют алгоритмы, сложность которых растет быстрее любого полинома. Проблема, которую часто решают теоретики — исследователи алгоритмов, заключается в следующем вопросе: возможен ли для данной задачи полиномиальный алгоритм? 

 Жизненный  цикл программного обеспечения 

       Жизненный цикл программного обеспечения включает в себя шесть этапов:

     1) Анализ требований,

     2) Определение спецификаций,

     3) Проектирование,

     4) Кодирование,

     5) Тестирование,

     6) Сопровождение. 

       Анализ требований. На этом этапе  должны быть получены четкие  ответы на следующие вопросы:

            Что представляют собой входные  данные ?

            Что должна делать программа  ?

            Какими должны быть выходные  данные ?

       Часто при этом строится математическая  модель объекта или явления. Модель отражает лишь существенные стороны объекта, но не тождественна ему. Степень соответствия модели объекту проверяется практикой, экспериментом. В случае необходимости модель уточняется. Примером простейшей модели является модель равноускоренного движения S=vt. 

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

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

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

программирования  конструкций алгоритма. Во время  кодирования могут

быть, чисто  визуально, обнаружены ошибки, неточности в алгоритме, что

может потребовать уточнения алгоритма.

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

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

       Процесс отладки имеет 3 основные  цели:

      1) обнаружение ошибок,

      2) локализация ошибок,

      3) исправление ошибок.

       Всегда надо помнить золотое  правило программистов: «Каждая программа содержит как минимум одну ошибку».  

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

      1) алгоритмические,

      2) ошибки программирования,

      3) синтаксические ошибки кодирования. 

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

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

Заключение  

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

Список  литературы. 

1. Нестеренко А. В. ЭВМ и профессия программиста.

М., Просвещение, 1990.

2. Брудно А. Л., Каплан Л. И. Московские олимпиады по программированию.

М., Наука, 1990.

3. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера.

М., Энергоатомиздат, 1988.

4. Галин А.Б., Панов Ю.В. Информатика. Феникс - 2009 г.

5. Егоров А., Котов Э. Информационные системы в юриспруденции. Феникс - 2008 г.
6. Юнита.,Москва2008 г. Информатика.