Задание 1. Анализ сложности алгоритма

Провести анализ и оценку временной сложности заданного алгоритма. Варианты заданий представлены в таблице, выбираются по первой букве фамилии студента. Блок-схемы алгоритмов – на рис. 1.1–1.6. В блок-схемах символ div обозначает операцию целочисленного деления, mod – остаток от целочисленного деления.

Таблица 1.1 – Варианты заданий

Рисунок 1.1 – Тривиальный алгоритм возведения x в степень n

Рисунок 1.2 – Рекурсивный алгоритм возведения x в степень n

Рисунок 1.3 – Алгоритмы быстрого возведения x в степень n

Рисунок 1.4 – Алгоритм вычисления значения многочлена степени n, заданного массивом своих коэффициентов A = {A[0], A[1],…, A[n]} при некотором значении переменной x по схеме Горнера

Рисунок 1.5 – Алгоритм вычисления значения многочлена степени n, заданного массивом своих коэффициентов A = {A[0], A[1],…, A[n]} при некотором значении переменной x

Рекомендации по выполнению задания

Практическое определение времени выполнения основано на следующих правилах: 

1. За функцию берется количество операций, возрастающее быстрее всего.

2. Константы не учитываются, в том числе и основания логарифма.  

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

4. Время выполнения операторов присваивания обычно имеет порядок О(1).

5. Время выполнения операторов ввода-вывода обычно имеет порядок О(1).

6. Время выполнения последовательности операторов определяется суммированием.

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

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

9. В случае, когда имеют место рекурсивные процедуры или функции, необходимо с каждой рекурсивной процедурой (функцией) связать временную функцию Т(n), где n определяет объем ее аргументов, и получить рекуррентное соотношение для T(n), представляющее собой уравнение (или неравенство) для Т(n), где участвуют значения T(k) для различных значений k < n. Решение таких рекуррентных соотношений состоит в последовательном раскрытии выражений Т(k) в правой части уравнения путем подстановки в исходное соотношение k вместо n до тех пор, пока не получится формула, у которой в правой части отсутствует Т.

Задание 2. Функционально-ориентированное моделирование программного обеспечения в методологии SADT

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

Таблица 2.1 –  Варианты заданий

Для предметной области:

1. Разработать модель процессов в нотации IDEF0.

2. Создать словарь данных модели.

3. Дополнить модель диаграммами DFD.

Рекомендации по выполнению задания

В работе используется свободно распространяемое ПО Ramus2.0 https://github.com/Vitaliy-Yakovchuk/ramus/releases или Ramus Education.

При разработке модели процессов в нотации IDEF0 необходимо:

- разработать контекстную диаграмму и описать ее;

- разработать диаграмму декомпозиции первого уровня, содержащую не менее 4 процессов, и описать ее.

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

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

К файлу отчета по работе дополнительно приложить файл Ramus rabota2.rsf.

Задание 3. Моделирование программного обеспечения в методологии UML

Для предметной области практического задания 2:

1. Провести описание своей предметной области в ключе объектно-ориентированного подхода.

2. Выполнить построение диаграммы прецедентов в StarUML.

3. Выполнить документирование элементов модели в StarUML.

4. Добавить описание потока событий одного прецедента.

Рекомендации по выполнению задания

В работе используется свободное средство моделирования StarUML. Ссылка для скачивания последней официальной версии с официальным неограниченным пробным периодом – http://staruml.io.

Руководство пользователя StarUML – https://docs.staruml.io/.

Руководство пользователя на русском языке – http://staruml.sourceforge.net/docs/user-guide(ru)/user-guide.pdf.

Задание 4. Детализация объектно-ориентированных моделей программного обеспечения

Для предметной области практического задания 2:

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

2. Построить диаграмму классов с атрибутами, операциями и отношениями своей предметной области.

3. Выполнить документирование классов.

4. Сгруппировать классы в 2-3 пакета, построить диаграмму пакетов.

5. Построить диаграмму состояний одного объекта модели.

Рекомендации по выполнению задания

В работе используется свободное средство моделирования StarUML. Ссылка для скачивания последней официальной версии с официальным неограниченным пробным периодом – http://staruml.io.

Руководство пользователя StarUML – https://docs.staruml.io/.

Руководство пользователя на русском языке – http://staruml.sourceforge.net/docs/user-guide(ru)/user-guide.pdf.

Задание 5. Математическое моделирование надежности программного обеспечения с помощью модели Джелински – Моранды

По таблице 5.1 выбрать номер задачи по первой букве своей фамилии.

Таблица 5.1 –  Варианты заданий

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

Задача 1. В результате тестирования программы серией из шести случайно выбранных из набора тестов обнаружено 2 ошибки. Ошибки обнаружены вторым и шестым тестами. Требуется определить количество ошибок N в программе до начала тестирования.

Задача 2. В результате тестирования программы серией из 10 случайно выбранных из набора тестов обнаружено 2 ошибки. Ошибки обнаружены первым и восьмым тестами. Требуется определить количество ошибок N в программе до начала тестирования.

Задача 3. В результате тестирования программы серией из 10 случайно выбранных из набора тестов обнаружено 3 ошибки. Ошибки обнаружены первым, третьим и десятым тестами. Требуется определить количество ошибок N в программе до начала тестирования.

Задача 4. В результате тестирования программы серией из восьми случайно выбранных из набора тестов обнаружено 2 ошибки. Ошибки обнаружены третьим и восьмым тестами. Требуется определить количество ошибок N в программе до начала тестирования.

Задача 5. В результате тестирования программы серией из 25 случайно выбранных из набора тестов обнаружено 3 ошибки. Ошибки обнаружены четвертым, десятым и двадцать вторым тестами. Требуется определить количество ошибок N в программе до начала тестирования» [2].

Задача 6. В результате тестирования программы серией из 30 случайно выбранных из набора тестов обнаружено 3 ошибки. Ошибки обнаружены шестым, четырнадцатым и двадцать восьмым тестами. Требуется определить количество ошибок N в программе до начала тестирования.

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

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

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

Задача 10. В результате тестирования программы серией из 11 случайно выбранных из набора тестов обнаружено 2 ошибки. Ошибки обнаружены третьим и десятым тестами. Все ошибки исправлены сразу после обнаружения. В предположении, что исправление ошибок не повлекло появление новых ошибок, требуется оценить количество оставшихся в программе ошибок» [2].

Рекомендации по выполнению задания

Пример выполнения задания представлен в пособии Б.В. Черникова «Оценка качества программного обеспечения. Практикум» [2, с. 287–289].

Задание 6. Математическое моделирование надежности программного обеспечения с помощью модели Миллса

По таблице 6.1 выбрать номер задачи по первой букве своей фамилии.

Таблица 6.1 – Варианты заданий

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

Задача 1. В программу было преднамеренно внесено (посеяно) 11 ошибок. В результате тестирования обнаружено 16 ошибок, из которых 11 ошибок были внесены преднамеренно. Все обнаруженные ошибки исправлены. До начала тестирования предполагалось, что программа содержит не более 7 ошибок. Требуется оценить количество ошибок до начала тестирования и степень отлаженности программы.

Задача 2. В программу было преднамеренно внесено (посеяно) 25 ошибок. В результате тестирования обнаружено 29 ошибок, из которых 25 ошибок были внесены преднамеренно. Все обнаруженные ошибки исправлены. До начала тестирования предполагалось, что программа содержит не более 8 ошибок. Требуется оценить количество ошибок до начала тестирования и степень отлаженности программы.

Задача 3. В программу было преднамеренно внесено (посеяно) 23 ошибки. В результате тестирования обнаружено 29 ошибок, из которых 23 ошибки были внесены преднамеренно. Все обнаруженные ошибки исправлены. До начала тестирования предполагалось, что программа содержит не более 5 ошибок. Требуется оценить количество ошибок до начала тестирования и степень отлаженности программы.

Задача 4. В программу было преднамеренно внесено (посеяно) 19 ошибок. В результате тестирования обнаружено 24 ошибки, из которых 19 ошибок были внесены преднамеренно. Все обнаруженные ошибки исправлены. До начала тестирования предполагалось, что программа содержит не более 7 ошибок. Требуется оценить количество ошибок до начала тестирования и степень отлаженности программы.

Задача 5. В программу было преднамеренно внесено (посеяно) 34 ошибки. В результате тестирования обнаружено 29 ошибок, из которых 18 ошибок были внесены преднамеренно. Все обнаруженные ошибки исправлены. До начала тестирования предполагалось, что программа содержит не более 15 ошибок. Требуется оценить степень отлаженности программы на момент обнаружения указанных выше ошибок» [2].

Задача 6. В программу было преднамеренно внесено (посеяно) 17 ошибок. В результате тестирования обнаружено 10 ошибок, из которых 6 ошибок были внесены преднамеренно. Все обнаруженные ошибки исправлены. До начала тестирования предполагалось, что программа содержит не более 7 ошибок. Требуется оценить степень отлаженности программы на момент обнаружения указанных выше ошибок.

Задача 7. В программу было преднамеренно внесено (посеяно) 39 ошибок. В результате тестирования обнаружено 23 ошибки, из которых 16 ошибок были внесены преднамеренно. Все обнаруженные ошибки исправлены. До начала тестирования предполагалось, что программа содержит не более 9 ошибок. Требуется оценить степень отлаженности программы на момент обнаружения указанных выше ошибок.

Задача 8. В программу было преднамеренно внесено (посеяно) 42 ошибки. В результате тестирования обнаружено 29 ошибок, из которых 25 ошибок были внесены преднамеренно. Все обнаруженные ошибки исправлены. До начала тестирования предполагалось, что программа содержит не более 9 ошибок. Требуется оценить степень отлаженности программы на момент обнаружения указанных выше ошибок» [2].

Рекомендации по выполнению задания

Пример выполнения задания представлен в пособии Б.В. Черникова «Оценка качества программного обеспечения. Практикум» [2, с. 293–300].

Задание 7. Проектирование базы данных для выбранной предметной области

1. В нотации Чена для выбранной в задании 2 предметной области постройте диаграмму «сущность – связь» (ERD). Для выполнения задания используйте бесплатный онлайн-сервис Visual Paradigm или другое доступное программное средство.

2. Используя диаграмму «сущность – связь», разработайте БД и установите связи между таблицами. Создайте диаграмму БД. Для выполнения задания используйте СУБД MS SQL Server, MS Access, программу MySQL Workbench или другое доступное программное средство.

3. Выполните предлагаемое задание. Вставьте скриншоты диаграмм в отчет.

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