Сортировка разделением (Quicksort)

Метод сортировки разделением был предложен Чарльзом Хоаром (он любит называть себя Тони) в 1962 г. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть "методом быстрой сортировки - Quicksort".

Основная идея алгоритма состоит в том, что случайным образом выбирается некоторый элемент массива x, после чего массив просматривается слева, пока не встретится элемент a[i] такой, что a[i] > x, а затем массив просматривается справа, пока не встретится элемент a[j] такой, что a[j] < x. Эти два элемента меняются местами, и процесс просмотра, сравнения и обмена продолжается, пока мы не дойдем до элемента x. В результате массив окажется разбитым на две части - левую, в которой значения ключей будут меньше x, и правую со значениями ключей, большими x. Далее процесс рекурсивно продолжается для левой и правой частей массива до тех пор, пока каждая часть не будет содержать в точности один элемент. Понятно, что как обычно, рекурсию можно заменить итерациями, если запоминать соответствующие индексы массива.

Алгоритм недаром называется быстрой сортировкой, поскольку для него оценкой числа сравнений и обменов является O(n?log n). На самом деле, в большинстве утилит, выполняющих сортировку массивов, используется именно этот алгоритм.

Вопрос 3. Проектирование программного обеспечения на основе структурного подхода. Диаграммы, используемые для создания проектной модели: функциональная, потоков данных (DFD), “сущность-связь” (ERD). Архитектура ПС.

Диаграммы, используемые для описания модели: функциональные (SADT), потоков данных (DFD), “сущность-связь” (ERD) Сущность структурного подхода к разработке ИС заключается в ее декомпозиции (разбиении) на автоматизируемые функции: система разбивается на функциональные подсистемы, которые в свою очередь делятся на подфункции, подразделяемые на задачи и так далее. Процесс разбиения продолжается вплоть до конкретных процедур. При этом автоматизируемая система сохраняет целостное представление, в котором все составляющие компоненты взаимоувязаны. При разработке системы "снизу-вверх" от отдельных задач ко всей системе целостность теряется, возникают проблемы при информационной стыковке отдельных компонентов. Все наиболее распространенные методологии структурного подхода базируются на ряде общих принципов. В качестве двух базовых принципов используются следующие:

• принцип "разделяй и властвуй" - принцип решения сложных проблем путем их разбиения на множество меньших независимых задач, легких для понимания и решения;

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

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

• SADT (Structured Analysis and Design Technique) модели и соответствующие функциональные диаграммы (подраздел 2.2);

• DFD (Data Flow Diagrams) диаграммы потоков данных (подраздел 2.3);

• ERD (Entity-Relationship Diagrams) диаграммы "сущность-связь" (подраздел 2.4).

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

• графическое представление блочного моделирования. Графика блоков и дуг SADT-диаграммы отображает функцию в виде блока, а интерфейсы входа/выхода представляются дугами, соответственно входящими в блок и выходящими из него. Взаимодействие блоков друг с другом описываются посредством интерфейсных дуг, выражающих "ограничения", которые в свою очередь определяют, когда и каким образом функции выполняются и управляются;

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

• ограничение количества блоков на каждом уровне декомпозиции (правило 3-6 блоков); -связность диаграмм (номера блоков);

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

• разделение входов и управлений (правило определения роли данных).

• отделение организации от функции, т.е. исключение влияния организационной структуры на функциональную модель.

Результатом применения методологии SADT является модель, которая состоит из диаграмм, фрагментов текстов и глоссария, имеющих ссылки друг на друга. Диаграммы - главные компоненты модели, все функции ИС и интерфейсы на них представлены как блоки и дуги. Место соединения дуги с блоком определяет тип интерфейса. Управляющая информация входит в блок сверху, в то время как информация, которая подвергается обработке, показана с левой стороны блока, а результаты выхода показаны с правой стороны. Механизм (человек или автоматизированная система), который осуществляет операцию, представляется дугой, входящей в блок снизу

Моделирование потоков данных (процессов)

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

• внешние сущности; -системы/подсистемы; -процессы; -накопители данных; -потоки данных.

Внешняя сущность представляет собой материальный предмет или физическое лицо, представляющее собой источник или приемник информации, например, заказчики, персонал, поставщики, клиенты, склад. При построении модели сложной ИС она может быть представлена в самом общем виде на так называемой контекстной диаграмме в виде одной системы как единого целого, либо может быть декомпозирована на ряд подсистем. Наиболее распространенным средством моделирования данных являются диаграммы "сущность-связь" (ERD). С их помощью определяются важные для предметной области объекты (сущности), их свойства (атрибуты) и отношения друг с другом (связи). ERD непосредственно используются для проектирования реляционных баз данных. Первый шаг моделирования - извлечение информации из интервью и выделение сущностей. Сущность (Entity) - реальный либо воображаемый объект, имеющий существенное значение для рассматриваемой предметной области, информация о котором подлежит хранению Связь (Relationship) - поименованная ассоциация между двумя сущностями, значимая для рассматриваемой предметной области. Связь - это ассоциация между сущностями, при которой, как правило, каждый экземпляр одной сущности, называемой родительской сущностью, ассоциирован с произвольным (в том числе нулевым) количеством экземпляров второй сущности, называемой сущностью-потомком, а каждый экземпляр сущности-потомка ассоциирован в точности с одним экземпляром сущности-родителя. Таким образом, экземпляр сущности-потомка может существовать только при существовании сущности родителя. Степень связи и обяза тельность графически изображаются следующим образом

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

Билет 11.

Вопрос 1. Обработка нечетких данных на прологе. Реализация на Прологе нечетких логических выводов. Применение логического и функционального программирования в задачах искусственного интеллекта. Основателем нечеткой логики можно считать профессора Калифорнийского университета Лотфи Заде. Его работа "Fuzzy Sets", появившаяся в 1965 году в журнале Information and Control, заложила основы моделирования интеллектуальной деятельности человека и явилась начальным толчком к развитию новой математической теории. Основанные на этой теории методы построения компьютерных нечетких систем существенно расширяют области применения компьютеров. Основные положения теории Заде:

• расширение классического понятия множества, с допущением, что характеристическая функция (функция принадлежности элемента множеству) может принимать любые значения в интервале (0;1), а не только значения 0 либо 1. Такие множества были названы нечеткими (fuzzy).

• Определение ряда операций над нечеткими множествами и обобщение известных методов логического вывода modus ponens и modus tollens.

• Введение понятия лингвистической переменной с допущением, что в качестве ее значений (термов) выступают нечеткие множества. Нечеткая логика - это непрерывная логика, в которой используются в виде высказываний лингвистические переменные (ЛП) с нечеткими квантификаторами, а логические формулы могут принимать значения истинности между «0» и «1». Для лингвистического описания истинности высказывания ЛП с нечеткими квантификаторами используется множество терминов или понятий, («очень истинный», «истинный», «скорее истинный, чем нет», «более или менее истинный», и.т.д.). Для формального описания термина «истинный» применяется числовая оценка в виде степени принадлежности t(u) при любом u E U. 0<=t(u)<=l. Значение степени принадлежности t(u) - это некоторое произвольное субъективное число на отрезке (0,1), не имеющее никакого вероятностно — статистического смысла. Для вычисления истинности композиции нечетких высказываний (фактов) а и b , при условии, что истинности самих высказываний известны t(a) и t(b), используются следующие правила: t(s) = t(a), если s = a

t(s) = 1 - t(a), если s = ???

t(s) = min(t(a),t(b)) если s= ?a ?b

t(s) = max(t(a),t(b)) если s = a ?b ? В нечеткой логике принято считать, что утверждение (факт, высказывание) является приближенно истинным, если t(s)>=0,5 при всех значениях аргумента. В противном случае высказывание считается приближенно ложным. При определении истинных значений ПП (правило продукции) применяются следующие зависимости. Если известны истинные значения t_x и t_y для условий X Y некоторого ПП, то истинное значение для условия t_yc в случае связей «И» и «ИЛИ» определяется следующим образом:

• при связи «И» t_yc = min(t_x ,t_y)

• при связи «ИЛИ» t_yc = max(t_x ,t_y) Постановка задачи. Экспертная система - это программа, которая ведет себя подобно эксперту в некоторой прикладной области. Считается, что поведение экспертной системы должно походить на поведение эксперта в заданной области и аккумулировать знания экспертов (высококвалифицированных специалистов) На практике знания эксперта не бывают категорическими (высказанными в терминах «истина» и «ложь»). Знания могут иметь свое внешнее выражение в форме следующих нечетких утверждений типа «возможно», «маловероятно», «скорее верно, чем неверно», и т.д. На практике степень уверенности эксперта в своих утверждениях может выражаться в форме действительного числа, заключенного в некотором интервале, например между 0 и 1. Такую числовую характеристику называют по-разному: «коэффициент определенности», «степень доверия», и т.д. Условимся впредь называть эту характеристику «достоверностью».

Вопрос 2. Определение, способы задания сетей Петри. Синтаксис и семантика сетей Петри. Сеть Петри С является четверкой, С=(P, T, I, O). P={p₁, p₂, …, p_n} – конечное множество позиций, n>=0. T={t₁, t₂, …, t_m} – конечное множество переходов, m>=0. Множество позиций и множество переходов не пересекаются. I – входная функция, О – выходная функция.

Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход t_j в множество позиций I(t_j), называемых входными позициями перехода. Выходная функция О отображает переход t_j в множество позиций О(t_j), называемых выходными позициями перехода.

C={P, T, I, O}

P={p₁, p₂, p₃, p₄, p₅}

T={t₁, t₂, t₃, t₄}

I(t₁)={p₁} O(t₁)={p₂, p₃, p₄}

I(t₂)={p₂, p₃, p₄} O(t₂)={p₂}

I(t₃)={p₄} O(t₃)={p₅}

I(t₄)={p₅} O(t₄)={p₃, p₄}

Для иллюстрации понятий теории сетей Петри чаще всего используют графическое представление. Граф сети Петри обладает двумя типами узлов: О – позиция и | - переход.

Ориентированные дуги соединяют позиции и переходы. Сеть Петри есть:

• мультиграф, т.к. он допускает существование кратных дуг от одной вершины графа к другой;

• ориентированный мультиграф, т.к. дуги направленные;

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

Рис. 3. Графическое представление сети Петри

Маркировка  есть присвоение фишек позициям сети Петри. Фишки используются для определения выполнения сети Петри.

Маркировка  сети Петри C=(P, T, I, O) есть функция, отображающая множество позиций Р в множество неотрицательных целых чисел N.

Маркировка  может быть определена как вектор, определяющий для каждой позиции p_i сети Петри количество фишек.

Маркированная сеть Петри есть совокупность структуры сети Петри и маркировки и может быть записана как M= (P, T, I, O, ). На рисунке выше изображена маркированная сеть Петри с маркировкой (1, 0, 0, 2, 1).

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

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

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

Запуск перехода в целом меняет маркировку  сети Петри на новую маркировку .

На рисунке 3 разрешены только три перехода – t₁, t₃, t₄. После запуска перехода t₄ получается маркировка рис. 4.

К огда не останется ни одного разрешенного перехода, выполнение прекращается.

Состояние сети Петри определяется ее маркировкой. Пространство состояний сети Петри, обладающей n позициями, есть множество всех маркировок, т.е. Nⁿ.

Рис. 4. Сеть Петри после срабатывания перехода t₄

Изменение в состоянии, вызванное запуском перехода, определяется функцией изменения , которая называется функцией следующего состояния.

Если переход t_j разрешен, то (, t_j)=.

При выполнении сети Петри получаются две последовательности: - Последовательность маркировок (⁰, ¹, ², …);

- Последовательность переходов, которые были запущены (t_j0, t_j1, t_j2, …). Эти две последовательности связаны следующим соотношением: (^k, t_jk)=^k+1. Для сети Петри C=(P, T, I, O) с маркировкой  маркировка  называется непосредственно достижимой из , если существует переход t_jT, такой что (, t_j)=. Множество достижимости R(C, ) сети Петри С с маркировкой  определяется как множество всех маркировок, достижимых из .

Вопрос 3. Процесс производства ПО. Технологический цикл разработки программных систем. Модели для оценки качества процесса разработки ПО (CMM, ISO/IEC 15504 и др.). Унификация процесса разработки ПО на примере RUP (Rational Unified Process). CASE-средства для организации процесса коллективной работы по созданию ПО (управление требованиями, конфигурацией, изменениями).

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

1. Начальный уровень (initial level) описан в стандарте в качестве основы для сравнения со следующими уровнями. На предприятии начального уровня организации не существует стабильных условий для созданий качественного программного обеспечения.

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

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

4. Управляемый уровень (managed level) в организации устанавливаются количественные показатели качества – как на программные продукты, так и на процесс в целом.

5. Оптимизирующий уровень (optimizing level) характеризуется тем, что мероприятия по улучшению применяются не только к существующим процессам, но и для оценки эффективности ввода новых технологий. Основной задачей всей организации на этом уровне является постоянное улучшение существующих процессов. КОНЕЦ

Стандарты ISO 9000 – обширная и наиболее распространенная во всем мире серия стандартов качества. Они охватывают множество отраслей современной индустрии и периодически обновляются. Изначально стандарты ISO 9000 слабо учитывали специфику отрасли ПО и были больше ориентированы на производственную сферу. ISO/IEC 15504, созданному в рамках совместного проекта международных организаций ISO и IEC под названием SPICE (Software Process Improvement for Capability dEtermination), стартовавшего в 1993 г. Стандарт ISO/IEC 15504 предназначен для оценки процесса разработки информационных систем, в частности, программного обеспечения. Он изначально был спроектирован таким образом, чтобы в значительной степени соответствовать существующим в отрасли стандартам оценки процесса создания ПО. Его текущая версия, датированная 2004 г., предусматривает шесть уровней возможностей (от нулевого до пятого), которые соответствуют уровням возможностей непрерывного представления стандарта CMMI.Качество программного продукта регламентирует стандарт ISO/IEC 9126, состоящий из отдельных частей, которые выпускаются независимо (на текущий момент их четыре: модель качества, внешние метрики, внутренние метрики и качество при использовании метрик). ISO/IEC 9126 предлагает комплексную иерархическую структуру для описания качественных характеристик ПО. Так, характеристиками качества наиболее высокого уровня являются функциональность, надежность, удобство применения, эффективность, сопровождаемость, переносимость. Каждая из них, в свою очередь, подразделяется на другие, более детальные. На текущий момент ISO/IEC 9126 – пожалуй, самый авторитетный стандарт, определяющий качество программного продукта

В основе RUP лежат следующие основные принципы:

• Ранняя идентификация и непрерывное (до окончания проекта) устранение основных рисков.

• Концентрация на выполнении требований заказчиков к исполняемой программе (анализ и построение модели прецедентов).

• Ожидание изменений в требованиях, проектных решениях и реализации в процессе разработки.

• Компонентная архитектура, реализуемая и тестируемая на ранних стадиях проекта.

• Постоянное обеспечение качества на всех этапах разработки проекта (продукта).

• Работа над проектом в сплочённой команде, ключевая роль в которой принадлежит архитекторам.

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

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

1. Начало (Inception)

- Формируются видение и границы проекта. - Создается экономическое обоснование (business case). - Определяются основные ребования, ограничения и ключевая функциональность продукта.

- Создается базовая версия модели прецедентов. - Оцениваются риски.

2. Проектирование (Elaboration)

- Документирование требований - Спроектированную, реализованную и оттестированную исполняемую архитектуру.

- Обновленное экономическое обоснование и более точные оценки сроков и стоимости.

3. Построение (Construction)

Во время этой фазы происходит реализация большей части функциональности продукта. Фаза Построение завершается первым внешним релизом системы и вехой начальной функциональной готовности (Initial Operational Capability).

4. Внедрение (Transition)

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

Билет 12.