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

Как правило, временная сложность алгоритма  зависит от исходных данных. Это  может быть зависимость как от величины исходных данных, так и  от их объема. Если обозначить значение параметра временной сложности  алгоритма αсимволом 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 г. Информатика.