Questions-2013

1. Функциональное и логическое программирование. Особенности и отличия от императивного программирования. Понятие функции в функциональном программировании. Лямбда-функции. Рекурсия.

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

Императивные

Декларативные

Объектно-ориентированные	Процедурные	Логические	Функциональные
(Java, C#)	(C, Pascal)	(Prolog, Mercury)	(Haskell, F#, LISP)

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

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

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

Основным элементом функционального программирования является функция. Математические функции выражают связь между параметрами (входом) и результатом (выходом) некоторого процесса. Так как вычисление — это тоже процесс, имеющий вход и выход, то функция является вполне подходящим и адекватным средством описания вычислений. Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования. Функциональная программа представляет собой набор определений функций. Функции определяются через другие функции или рекурсивно — через самих себя. В процессе выполнения программы функции получают параметры, вычисляют и возвращают результат, в случае необходимости вычисляя значения других функций. Программируя на функциональном языке, программист не должен описывать порядок вычислений. Ему необходимо просто описать желаемый результат в виде системы функций.

Свойства функциональных языков, отличия от императивных языков:

1 из 14

краткость и простота;

quickSort [] = []

quickSort (h : t) = quickSort [y | y <- t, y < h] ++ [h] ++ quickSort [y | y <- t, y >= h]

строгая типизация;

обеспечивает безопасность;

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

модульность (есть в императивных языках тоже);

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

функции — это значения;

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

чистота (отсутствие побочных эффектов);

в чистом функциональном программировании оператор присваивания отсутствует;

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

О ненужных объектах позаботится встроенный в язык сборщик мусора.

Все функции свободны от побочных эффектов и их вычисления можно распараллелить;

отложенные (ленивые) вычисления.

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

строгим.

Функция в функциональном языке программирования не имеет побочных эффектов. Нотация определения функции:

<имя_функции>::<тип_параметра1>→…→<тип_параметраN>→<тип_результата>

Нотация описания функции:

<имя_функции> <параметр1> <параметр2> = <определение_вычисления>

Пример:

add::Int->Int->Int add x y = x + y

Вызов функции:

add 5 6

Вызывать функции можно и в инфиксной нотации

5 `add` 6

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

2 из 14

абстракции можно определять анонимные функции (например, для единичного вызова). Ниже показан пример определения функций add и inc именно при помощи λ-исчисления.

add = \x y -> x + y inc = \x -> x + 1

Понятие λ-функции в функциональном языке программирования соответствует понятию анонимной функции в императивном языке программирования.

Каррирование и частичное применение функции. Если функция f имеет тип A1 (A2 ( ... (An B) ... )), то чтобы полностью вычислить значение f (a1, a2, ..., an) необходимо последовательно провести вычисление ( ... (f (a1) a2) ... ) an. И результатом вычисления будет объект типа B.

Соответственно выражение, в котором все функции рассматриваются как функции одного аргумента, а единственной операцией является аппликация (применение), называются выражениями в форме «оператор – операнд». Такие функции получили название «каррированные», а сам процесс сведения типа функции к виду, приведенному в предыдущем абзаце — каррированием (по имени Карри Хаскелла).

Ведь если традиционно считалось, что выражение f (5) обозначает «применение функции f к значению аргумента, равному 5» (т.е. вычисляется только аргумент), то в функциональном программировании считается, что значение функции также вычисляется. Функцию add можно записать как (add (x)) y, а когда аргументы получают конкретные значения (например, (add (5)) 7), сначала вычисляются все функции, пока не появится функция одного аргумента, которая применяется к последнему.

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

len :: [a] -> Int len [] = 0

len (_:xs) = 1 + len xs –- голова + длина хвоста через рекурсию

Заметим что:

Функция работает со списками любых типов данных;

Используется вариант определения функции в случае совпадения по образцу, и конструкция разбиения на голову и хвост списка;

Длина пустого списка равна 0;

Вычисление длины списка выполняется рекурсивно;

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

2.Разработка ПО. Жизненный цикл. Концептуальное, логическое и техническое проектирование.

Специфика разработки программного обеспечения:

3 из 14

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

•Носит творческий характер;

•Статический текст программы выражается путем запуска программы на исполнение, т.е. является динамическим;

•ПО при использовании не расходуется.

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

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

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

Стратегии разработки ПО:

Однократная

oОпределены все требования

oОдин цикл конструирования

oПромежуточных версий нет

Инкрементная

oОпределены все требования

o Множество циклов конструирования

oПромежуточные версии могут распространяться

Эволюционная

oОпределены не все требования

o Множество циклов конструирования

4 из 14

oПромежуточные версии могут распространяются Адаптивность к изменениям:

Тяжеловесные (прогнозирующие)

oФиксированные требования

o Большая команда

oРазная квалификация разработчиков

Адаптивные (облегченные)

oПостоянно меняющиеся требования

oМаленькая команда

oВысококвалифицированные разработчики

Виды процессов:

Водопадная (однократная) стратегия

o Классическая (каскадная) модель

oMSF*

Инкрементная стратегия

oИнкрементная модель

o Быстрая разработка приложений (RAD)

oRUP*

Эволюционная стратегия

oПрототипирование (Макетирование)

o Спиральная модель

o RUP*

o MSF*

o Экстремальное программирование (XP)

o SCRUM

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

5 из 14

Сбор и анализ Сбор и анализ требований требований

Проектирование Проектирование

Детальное проектирование Разработка архитектуры

Кодирование Кодирование

рис. Место проектирования в процессе разработки

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

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

Тип проектирования	Цель			Результат
Концептуальное	Учет	требований	пользова-	Описание задачи и ее решение в
	телей и бизнеса			терминах сценариев
Логическое	Учет	требований	проектной	Описание решения в виде набора
	группы			взаимодействующих сервисов
Техническое	Учет	требований	разработ-	Описание сервисов и технологий,
	чиков			необходимых	для	реализации
				решения

Концептуальное представление наиболее абстрактно и обычно описывается в терминах, знакомых обычным пользователям (не ИТ-специалистам). Концептуальное представление используется для определения функциональных требований и представления приложения с точки зрения бизнес-пользователей в процессе создания бизнес-модели.

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

6 из 14

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

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

Логическое проектирование — это процесс описания решения в терминах организации, структуры, синтаксиса и взаимодействие его частей с точки зрения проектной группы.

Результат данной стадии — набор бизнес-объектов с соответствующими сервисами, атрибутами и взаимосвязями; детальный проект пользовательского интерфейса и логический проект базы данных.

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

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

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

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

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

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

7 из 14

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

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

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

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

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

1. Вариант

2. Наследуемые классы

3. Архитектура

Трос

использования

Автомобиль

(часть требований)

"Необходимо, чтобы

Дорога

машины смогли

проехать с вершины

Опора

холма Смита со

скоростью 100 км/ч

(для детального

Обеспечение варианта использования

по прямой линии до

проектирования)

Трос

Долины Джонса за 3

Перила

Автомобиль

минуты"

Дорога

4. Детальное проектирование

Холм Смита	Опора	Долина Джонса

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

8 из 14

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

3. Понятие теста. Модульное тестирование ПО. Типы тестов.

Уровни тестирования

По уровню охвата в тестировании выделяются три основных уровня:

1.Модульное тестирование.

2.Интеграционное тестирование.

3.Системное тестирование.

Модульное тестирование

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

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

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

Модульное тестирование целесообразно осуществлять в четыре последовательно выполняемых шага.

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

9 из 14

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

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

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

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

Интеграционное тестирование

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

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

рис. Пример структуры комплекса программ

На рисунке выше приведена структура комплекса программ K, состоящего из оттестированных на этапе модульного тестирования модулей M1, M2, M11, M12, M21, M22. Задача, решаемая методом интеграционного тестирования, - тестирование межмодульных связей, реализующихся при исполнении программного обеспечения комплекса K. Интеграционное тестирование использует модель "белого ящика" на модульном уровне. Поскольку тестировщику текст программы известен

10 из 14