Нижнекамский химико-технологический институт (филиал)

Нижнекамский химико-технологический институт (филиал)

Государственного образовательного учреждения

высшего профессионального образования

«Казанский государственный технологический университет»

Технологии программирования

Текст лекций

2007

Федеральное агентство по образованию

Нижнекамский химико-технологический институт (филиал)

Государственного образовательного учреждения

высшего профессионального образования

«Казанский государственный технологический университет»

Технологии программирования

Текст лекций

Нижнекамск 2007

Составители:

О.В. Ибушева, А.Р. Нигматуллина, Н.Н. Саримов.

Технологии программирования: Текст лекций / Нижнекамский рег. уч.-мет. центр; Сост.: О.В.Ибушева, А.Р.Нигматуллина, Н.Н.Саримов. Нижнекамск, 2007.

 

Пособие предназначено для обеспечения курса лекций по дисциплине «Технологии программирования» для студентов, обучающихся по специальности 230102 - Автоматизированные системы обработки информации и управления и по направлению подготовки бакалавров 230100 – Информатика и вычислительная техника.

 

 

Подготовлено на цикле информационных технологий при кафедре АТПП Нижнекамского химико-технологического института.

Печатается по решению методической комиссии по циклу дисциплин автоматизации и электропривода.

 

 

Рецензенты: д. ф.-м. н., профессор КазГУ И.Б.Бадриев,

                     к. ф.-м. н., доцент КазГУ О.А.Задворнов.

введение

Цели и задачи курса «Технология программирования»

1. Умение формулировать требования к программным средствам.

2. Оценивать качество и эффективность программного изделия.

3. Выбирать программные средства, наиболее соответствующие запросам пользователя.

4. Научиться современным методам и навыкам проектирования, тестирования, а также сопровождению программного обеспечения.

Классификация программного обеспечения

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

Различают системное (общее) и прикладное (специальное) ПО.

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

По функциональному назначению в системном ПО выделяют:

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

2.

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

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

4. Средства контроля и диагностики – служат для проверки исправности отдельных устройств и локализации выявленных неисправностей.

· Прикладное ПО разрабатывается и используется для решения конкретных задач пользователей ЭВМ.

Обеспечение целей создания программных изделий

Тема 3. Внутреннее проектирование программных изделий

Методы проектирования программ

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

Тема 4. Структурированные программы

Теорема о структурировании

Теорема. Любая простая программа функционально эквивалентна программе, составленной из элементов базисного множества: последовательность, if then else, whilе do с использованием функций и предикатов исходной программы, а также присваиваний и тестов над дополнительным счетчиком.

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

Далее для каждого функционального узла h, имеющего номер i и выходную линию j, составим в соответствие новую элементарную программу (последовательность) g_i с номером входной линии i.

Здесь в новом функциональном узле производится присваивание номера выходной линии переменной L, называемой программным счетчиком. Далее для каждого предикатного узла с номером i и выходными линиями j и k поставим в соответствие элементарную программу g_i  вида:

Теперь построим программу типа « whilе do» следующего вида:

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

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

Элементарные программы g_i для нее будут иметь вид:

Подставив g₁ – g₄ в схему, сконструированную в доказательстве теоремы, получим блок-схему структурированной программы.

Принцип простой индукции

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

Согласно простой математической индукции для этого необходимо:

1) доказать, что справедливо высказывание .

2) Доказать, что если для справедливо высказывание , то справедливо и высказывание .

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

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

2) Предположим, что справедливо высказывание

Покажем, что справедлива формула и для .

 

Принцип обобщенной индукции

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

1. доказать, что справедливо ;

2. доказать, что если справедливо , , то имеет место и .

 

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

Пусть имеется следующая программа поиска максимального значения среди элементов х_i,j.

1-8 – это точки, в которых предположительно имеют место следующие утверждения:

· А₁ : х – массив чисел, состоящий из m строк и n столбцов,

(исходная предпосылка);

 

· А₂ : , кроме того

· А₃: , , при этом .

 

· А₈ : .

 

Доказательство.

1) Путь 1→2: , и т.к. из , то , т.е. утверждение А₂ справедливо.

2) Путь 2→3: Дано утверждение А₂. Требуется доказать А₃. При первом вхождении в точку 3 ,следовательно, , т.к. . Из утверждения А₂, т.к. i не менялось, имеем , но в силу ограничения цикла в точке 2 в точке 3 получаем . Если , то из утверждения А₂ следует , иначе, когда , из утверждения А₂ получаем, что . Более того, можно утверждать, что , т.к. . Таким образом, видно, что при переходе из точки 2 в точку 3 утверждение А₃ оказывается справедливым.

3) Путь 3→4→5→3. Пусть справедливо утверждение А₃. Покажем, что оно остается справедливым при переходе по данному пути. Пусть в точке 3 в какой-то момент времени , для которых выполняются неравенства: , . Тогда при переходе по пути 3→4→5→3 получаем , где . Так как мы двигались по указанному выше пути, то проверка  в цикле была истинной, следовательно, . Значение  не менялось, кроме того, мы приходим в точку 3 с условием , следовательно,  остается максимальным и для нового значения j, т.е. утверждение А₃ остается справедливым.

4) Путь 3→4→6→3. Доказательство аналогично пункту 3 за исключением того, что здесь нашлось , и переменной  присвоено это значение. Таким образом, утверждение А₃ остается также справедливым.

5) Путь 3→7→2. Пусть справедливо утверждение А₃. Покажем, что при прохождении пути 3→7→2 будет справедливо утверждение А₂. Из точки 3 в точку 2 мы попадаем, когда ложна проверка , но из А₃ известно, что . Отсюда следует, что  или . Тогда утверждение A₃ относительно  перепишется в виде . Но при прохождении пути 3→7→2 , поэтому , . Утверждение А₂ справедливо.

6) Путь 2→8. Так как мы вышли из точки 2 в точку 8 проверка неравенства  оказалась ложной, следовательно,  и утверждение A₂ , что , преобразуется в утверждение A₈ о частичной правильности программы: .

. . . .

                              if <условие N> then <выражениеN>

else <выражение N+1>

В данном выражении последовательно проверяются условия. Если i-ое условие выдает истину, то функция F выдает значение выражения i. Если ни одно из условий не выдает истину, то функция выдает значение выражения N+1. Рекурсия вводится в этот язык следующим образом: функция F может входить как часть в любом из выражений или условий в программе. Такое появление F называется рекурсивным обращением к этой функции. Дополнительно для каждой такой рекурсивной программы необходимо указать область определения, т.е. указать для каких аргументов х₁,…х_n применима программа.

Примеры рекурсивных программ

1. Рассмотрим программу, применимую  целого:

F ( x) = if х=0 then 1

else х·F(х-1)

Для иллюстрации работы данной программы выполним ее, например, для х=4:

2. Функция Аккермана. Эта функция применима  целых.

А(х,у) = if х=0 then у+1

else if y=0 then A(x-1,1)

else A(х -1, A(x, y-1))

Проследим, каким образом выполняется эта программа для х=1, у=2.

А(1,2)=А(0, А(1,1))=А(0, А(0, А(1,0)))=

=А(0, А(0, А(0,1)))=А(0, А(0,2))= А(0,3) =4

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

А(1, 2) = А(0, А(1,1)) = А(1,1) + 1 =

= А(0, А(1,0)) + 1= (А(1,0) +1) + 1 =

= А(0,1) + 2 = 2 + 2 = 4

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

Рассмотрим следующую функцию, применимую  целых:

F ( x,у) = if х=0 then 0

else F(0, F(х,у))

Проследим за вычислением F, используя два различных правила вычисления:

1) при предпочтении внешнему обращению

F (1,1) = F(0, F(1,1))=0;

2) при предпочтении внутреннему обращению.

F (1,1) = F(0, F(1,1))= F(0, F(0,F(1,1)))=…

Таким образом, в первом случае последовательность конечна и функция А=0, во втором случае вычисления не заканчиваются.

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

Списки и операции над ними

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

Список – это набор объектов, отделенных друг от друга пробелами и заключенных в квадратные скобки []. Объектами, входящими в такие списки, являются атомы (неделимые элементы) или другие списки.

Атом – это строка буквенно-цифровых символов, не содержащая пробелы.

Для того чтобы отличать атомы от переменных, будем считать, что переменные записываются строчными буквами, а атомы – прописными. Например, [А В С] – список из трех элементов, каждый из которых является атомом. [А [В А [С]]D] – список, в котором на верхнем уровне три элемента: второй элемент сам является списком из трех элементов, в котором третий элемент – это список из одного элемента С.

Для пустого списка, т.е. списка, не содержащего одного элемента, выделяется специальное имя nil.

Наиболее распространенными операциями над списками и атомами являются следующие.

1. Проверка на равенство:

[А В] = [А В] выдает true ,

[А В] = [В А] и во всех других случаях - false.

2. Проверка аtom(х) - применима к любым объектам: атомам или спискам. Выдает true, если х является атомом или пустым списком.

3. Саr(l) применима к любому непустому списку. В качестве результата выдается первый на верхнем уровне элемент этого списка:

Саr([А В С])=А;

Саr([[А В]С D])=[А В];

Саr(nil) и Саr (А) – не определены.

4. Cdr( l) – применима к любому непустому списку l; результатом является список, полученный из списка l путем исключения первого элемента: Cdr([А В С]) = [В С].

5. Соns(х,l) - объединяет элемент х со списком l:

Соns(А, [D E]) = [А D Е];

Соns([А В], [D E]) = [[А В] D E].

Примеры программ работы со списками

1. Программа, определяющая является ли х элементом списка l на верхнем уровне.

member (x,l) =

            if l=nil then false

            else if x=car (l) then true

                  else member (x,cdr (l))

2. Программа, присоединяющая список l₂ в конец списка l₁.

append (l₁, l₂) =

       if l₁ = nil then l₂

       else cons (car (l₁), append (cdr (l₁), l₂))

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

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

Пример 1. Докажем, что функция Аккермана (см. 6.1) конечна.

В качестве множества х выберем множество пар натуральных чисел, упорядоченных в лексикографическом порядке, т.е. (х,у) < ( ), если х < , иначе, когда х = , то должен быть у< . Очевидно, минимальным элементом этого множества будет элемент (0,0).

Для доказательства конечности функции Аккермана необходимо доказать:

1. А(0,0) – конечна.

Действительно, А(0,0) = 1 - конечна.

2. Доказать, что если А(х,y) конечна , то функция А конечна и для .

Докажем это. Для этого предположим, что  конечна  (гипотеза индукции).

Тогда получим:

а) если , то очевидно, что  конечна;

б) если , то  конечна, т.к. ;

в) если , то , где   конечна, т.к. . Следовательно, и  конечна, т.к. .

Пример 2. Рассмотрим рекурсивную программу, вычисляющую пересечение двух упорядоченных списков l₁ и l₂.

Intord (l₁,l₂) =

if l₁=nil then nil

else if l₂=nil then nil

  else if car(l₁) < car(l₂) then intord(cdr (l₁),l₂)

         else if car (l₂) < car (l₁) then intord(l₁, cdr(l₂))

               else cons (car(l₁), intord (cdr(l₁), cdr(l₂)))

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

Пусть d₁ = length (l₁), d₂ = length (l₂).

Для доказательства правильности покажем, что:

1. функция работает правильно для наименьшей пары длин, т.е. для ( d₁, d₂)=(0,0). Очевидно, что списки с длинами (0,0) – есть пустые списки, поэтому intord (nil,nil) = nil .

2. покажем, что если  функция работает правильно, то она работает правильно для .

Возможны следующие варианты.

а) l₁ =nil или l₂ =nil. Здесь intord( l₁, l₂)= nil – функция работает правильно.

б) car(l₁)<car(l₂). Здесь intord( l₁, l₂)= intord( cdr( l₁), l₂)), но , т.е. для  функция работает правильно.

в) car ( l₂) < car ( l₁), доказывается аналогично варианту б).

г) car(l₁)=car(l₂). Здесь  выдает объединение элемента, присутствующего в списках l₁ и l₂, с пересечением со списками меньшей длины, для которых функция работает правильно. Следовательно, функция в целом работает правильно.

Тема 7. Отладка программ

Задачи отладки программ

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

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

статическую проверку текстов разработанных программ и данных на выполнение всех заданных правил построения без исполнения объектного кода;

тестирование программы с ее исполнением в объектном ко­де и с разными уровнями детализации: детерминированное, стохастическое и тестирование в реальном времени;

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

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

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

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

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

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

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

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

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

Методы разработки тестов

Предположения об ошибках

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

Нижнекамский химико-технологический институт (филиал)

Государственного образовательного учреждения

высшего профессионального образования

«Казанский государственный технологический университет»

12345678910Следующая ⇒

Поделиться: