close

Вход

Забыли?

вход по аккаунту

?

448.Прогнозирование времени выполнения программного кода Рублев В С

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П.Г. Демидова
Кафедра теоретической информатики
В В.С. Рублев
Прогнозирование
времени выполнения
программного кода
Методические указания
по лабораторному практикуму
Рекомендовано
Научно-методическим советом университета
для студентов, обучающихся по специальностям
Математическое обеспечение и администрирование
информационных систем
и Прикладная математика и информатика
Ярославль 2007
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 519.725
ББК В 185я73
Р 82
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2007 года
Рецензент
кафедра вычислительных и программных систем
ЯрГУ им. П.Г. Демидова
Р 82
Рублев, В.С. Прогнозирование времени выполнения командного кода: метод. указания по лабораторному практикуму / В.С. Рублев; Яросл. гос. ун-т. – Ярославль: ЯрГУ,
2007. – 36 с.
Методические указания помогают освоить методы прогнозирования времени выполнения программного кода
SQL-запросов.
Предназначены для студентов, обучающихся по специальностям 010500 Математическое обеспечение и администрирование информационных систем (дисциплина «Метрология и качество программного обеспечения», блок ЕН) и
010501 Прикладная математика и информатика (дисциплина «Визуальные системы программирования», блок ЕН),
очной формы обучения.
УДК 519.725
ББК В 185я73
© Ярославский государственный
университет им. П.Г. Демидова,
2007
© В.С. Рублев, 2007
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. Цель работы
1. Обучение методам прогнозирования времени выполнения
программного кода SQL-запросов.
2. Обучение методам разработки SQL-запроса, эффективного
по времени выполнения.
2. Общее задание
1. Для базы данных динамической ситуации, определенной в
лабораторной работе «Проектирование реляционной базы данных
и интерфейса», разработать SQL-запрос индивидуального задания
в двух вариантах: без связей таблиц внешними ключами и со связью таблиц внешними ключами.
2. Проанализировать запрос и определить трудоемкость запроса для каждого варианта.
3. Выбрать вид функций временной сложности и набор тестов
(значений параметров функций) для вычислительных экспериментов.
4. Построить программу тестирования, определяющую время
выполнения запроса с генерацией данных тестов случайным образом, и отладить ее.
5. Провести тестирование со снятием времени выполнения запроса.
6. Вычислить коэффициенты функций временной сложности
по методу наименьших квадратов. Проанализировать полученные
функции и при отрицательных значениях старших коэффициентов
(коэффициентов у старших членов функций) пересмотреть трудоемкость в сторону понижения, пересчитать коэффициенты.
7. Разработать программу предсказания времени выполнения
(минимального, максимального и среднего) для запроса с выполнением теста производительности компьютера и корректировкой
значений функций, а также с определением реального времени выполнения SQL-запроса.
8. Провести дополнительные тесты для других значений параметров, которые выходят за область параметров, использованную
для построения функций временной сложности. Сравнить резуль3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
таты предсказания с реальным временем и в необходимых случаях
провести корректировку трудоемкости и вида функций.
9. Сравнить оба варианта запроса и сделать предложения по
дальнейшему улучшению кода запроса.
10. Составить отчет, который должен содержать:
1) Задание общее и индивидуальное.
2) Запрос и таблицы для двух вариантов.
3) Анализ трудоемкости запроса.
4) Определение вида функций временной сложности.
5) Программу тестирования (насыщение таблиц случайным и
предопределенным образом в соответствии с тем или иным тестом).
6) Параметры тестов и результаты выполнения тестирования.
7) Расчет коэффициентов функций временной сложности по
методу наименьших квадратов.
8) График функций временной сложности с точками тестирования.
9) Программу прогноза времени выполнения запроса с тестом
производительности компьютера.
10) Дополнительное тестирование и сравнение с прогнозом.
11) Анализ вариантов запроса и предложения по дальнейшему
улучшению.
3. Варианты индивидуальных заданий
1. Динамическая ситуация. Сессия определяется изменяющимся списком сдаваемых студентами предметов, зависящих от курса, и оценками, получаемыми каждым студентом по этим предметам, а также состоянием студента:
1) подготовка – сессия не закончена (не все предметы сдавались студентом);
2) перевод на следующий курс – сессия сдана успешно, а курс
студента не последний;
3) отчисление – сессия закончена, и более чем по 2-м предметам оценки неудовлетворительные;
4) окончание – сессия сдана успешно и курс студента последний.
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Запрос. Список предметов, по которым максимальное количество студентов сдало предмет на наивысшую оценку для данного
предмета.
2. Динамическая ситуация. Назначение научного руководителя
определяется для студентов, специализирующихся по кафедре работы преподавателя, имеющих курс не ниже 2-го:
1) без руководителя – курс ниже 3-го;
2) перевод на следующий курс (отчисление после последнего
курса);
3) назначение руководителя – 3-й курс;
4) изменение руководителя – курс выше 3-го.
Запрос. Список преподавателей, которые руководят максимальным количеством студентов среди преподавателей своей кафедры.
3. Динамическая ситуация. Предприятие определяется отделами и списками работников отделов с их стажами. Во главе каждого отдела стоит один из работников отдела – руководитель. Состояния работника:
1) прием – стаж равен 0;
2) выслуга – стаж увеличивается на 1;
3) проводы на пенсию – достижение пенсионного стажа;
4) назначение руководителем – если отдел не имеет руководителя;
5) перевод в другой отдел.
Запрос. Список руководителей отдела, в которых работает
максимальное число работников с предпенсионным стажем работы.
4. Динамическая ситуация. Автобусные маршруты, каждый из
которых определяется номером и кольцевым списком остановок, а
каждый автобус определяется номером машины и номером маршрута. Состояния автобуса:
1) снят с маршрута – новый или в ремонте;
2) назначение на маршрут;
3) изменение маршрута;
4) списание.
Запрос. Список остановок, которые принадлежат максимальному числу маршрутов с минимальным числом автобусов на этих
маршрутах.
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5. Динамическая ситуация. Вступительные экзамены на факультеты, каждый из которых имеет свой список экзаменов и проходной балл, а абитуриент может подать на несколько факультетов и определяется состоянием:
1) подача заявления – не сформирован список факультетов для
абитуриента;
2) экзамены – список факультетов абитуриента сформирован,
но не сданы все экзамены;
3) выбор факультета – все экзамены сданы;
4) зачисление – если на выбранный факультет набран проходной балл.
По окончанию зачисления всех абитуриентов формирование
списков зачисленных.
Запрос. Список экзаменов, по которым максимальное число
студентов получило наивысшую оценку среди студентов, подавших заявление на несколько факультетов.
6. Динамическая ситуация. Прием на работу со списками рабочих мест, определяемых профессией и ставкой, и претендентов,
определяемых профессиями и рейтингом (квалификацией). Состояния претендента:
1) заявление – определяются профессии претендента и рейтинг;
2) выбор места – все профессии и рейтинг определены;
3) зачисление – рейтинг претендента больше рейтингов других
желающих поступить на это место.
Формирование списка зачисленных претендентов с местами.
Запрос. Список рабочих мест, на которые претендуют максимальное количество работников с самым высоким рейтингом для
такого места.
7. Динамическая ситуация. Библиотечный абонемент со списками книг и читателей, для каждого из которых определяется состояние:
1) заявка – формирование списка заявленных книг;
2) чтение – формирование списка прочитанных книг;
3) обмен – сдача прочитанных книг, получение заявленных
книг, если они свободны.
Библиотека имеет 3 состояния:
1) поступление – книга поступает новая или из ремонта;
2) ремонт – книга поступает в ремонт;
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3) прием-выдача книг от читателей.
Запрос. Список книг, на которые претендует максимальное
число читателей, имеющих минимальное число взятых книг.
8. Динамическая ситуация. Рынок со списками товаров (с количеством и ценой) и очередью покупателей (с кошельком – количество денег). Состояние покупателя:
1) занять очередь – стать последним; при этом список покупок
пустой;
2) стоять в очереди – определить список необходимых покупок, если не первый и не последний в очереди;
3) купить – если первый в очереди; если денег не хватило, снова занять очередь.
Запрос. Список товаров, имеющих наибольший дефицит (разность между суммарным необходимым количеством для всех покупателей этого товара и количеством непроданного).
9. Динамическая ситуация. Пассажирские перевозки со списками поездов (номер, список остановок, остановка местонахождения) и пассажиров (откуда, куда). Состояние поезда:
1) формирование – пополнение списка остановок;
2) остановка – посадка-высадка пассажиров;
3) движение – списки остановок и пассажиров поезда не изменяются.
Запрос. Список остановок, через которые проходит максимальное количество поездов с минимальным количеством пассажиров, выходящих на такой остановке.
10. Динамическая ситуация. Обед в столовой со списками
блюд (с ценой) и очередью студентов (с кошельком – количество
денег). Состояние студента:
1) занять очередь – стать последним; при этом список блюд
пустой; определяются деньги в кошельке;
2) стоять в очереди – определить список блюд на обед, если
не первый и не последний в очереди;
3) заплатить – если первый в очереди (если денег не хватило,
снова занять очередь).
Запрос. Список блюд, которые заказывают максимальное количество студентов с кошельками, позволяющими оплатить все заказанные блюда.
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
11. Динамическая ситуация. Авиаперевозки со списками аэропортов, рейсов (аэропорт вылета, аэропорт назначения, список аэропортов следования, вместимость пассажиров, аэропорт местоположения) и пассажиров (аэропорт вылета, аэропорт назначения).
Состояние рейса:
1) посадка-высадка – выходят пассажиры, чей аэропорт назначения совпадает с аэропортом местоположения самолета, и садятся
пассажиры, чей аэропорт назначения совпадает с одним из последующих в списке аэропортов следования;
2) полет – список пассажиров не меняется; местоположение
самолета меняется на следующий аэропорт следования.
Состояния пассажира:
1) без билета – определяются аэропорты вылета и назначения;
2) с билетом на посадку – определяется подходящий рейс;
3) полет;
4) высадка – когда самолет достиг аэропорта назначения пассажира.
Запрос. Список аэропортов, в которые следует максимальное
количество рейсов с минимальным количеством пассажиров, находящихся в полете.
12. Динамическая ситуация. Хоккей со списками команд (список игроков, список на игру), хоккеистов (команда, разряд, забитые
шайбы, количество сыгранных игр, количество добытых очков, начальный разряд = 5) и игр (команда-хозяин, команда-гость, упорядоченный список игроков, забивших шайбы). Состояния игры:
1) определить игру – определить команды и списки игроков на
игру;
2) начать игру – опустошить список игроков, забивших шайбы;
3) закончить игру – определить список игроков, забивших
шайбы; повысить разряд (уменьшить значение) для хоккеистов,
для которых отношение добытых очков к сыгранным играм >2 и в
этом случае сбрасывает число игр на 0, а число добытых очков делает равным (разряд – 4)*10.
Запрос. Список команд, имеющих наименьшее число игроков с
наивысшим разрядом для команды.
13. Динамическая ситуация. Самодеятельность со списком
кружков (руководитель, список учеников кружка), списком учеников (список кружков ученика), списком руководителей (список
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
кружков руководителя, список учеников руководителя). Состояния
ученика:
1) желание – определение списка кружков;
2) поступление – включение в списки кружков;
3) уход – исключение из кружка.
Запрос. Список руководителей, которые руководят наибольшим числом кружков, посещаемых учениками с наименьшим количеством кружков.
14. Динамическая ситуация. Школа со списком классов (список
учеников класса), списком учеников, списком учителей
(список классов учителя, стаж). Состояния учителя:
1) поступление – стаж равен 0, определяются классы;
2) преподавание – стаж по событию увеличивается на 1;
3) выход на пенсию – при достижении пенсионного стажа.
Запрос. Список опытных учителей (стаж больше 1), имеющих
наибольшее число классов с наименьшим числом учеников.
15. Динамическая ситуация. Метро со списком линий (список
станций линии, список поездов линии), список поездов (номер, линия), списком станций.
Запрос. Список станций метро, через которые проходит наибольшее число линий с наименьшим числом поездов на линии.
16. Динамическая ситуация. Ресторан со списком столиков,
списком официантов (список столиков официанта, число собранных «штанов» за неуплату), списком блюд (цена), списком посетителей (кошелек, список желаемых блюд). Состояния столика:
занят, свободен. Состояния посетителя:
1) ожидание – ждет свободного столика;
2) заказ – определяет список блюд;
3) обед;
4) расчет – оплачивает обед; если денег в кошельке мало, расплата «штанами»; столик освобождается.
Запрос. Список официантов, обслуживающих наибольшее число столиков, которые заняты посетителями, сделавшими наибольший по сумме цен заказ.
17. Динамическая ситуация. Командный шахматный турнир
со списком команд (список шахматистов команды) и списком
шахматистов (разряд, команда, число сыгранных партий, число
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
добытых очков, список соперников, с которыми сыграны партии).
Состояния шахматиста:
1) зачисление в команду – начальные значения параметров
(разряд=5);
2) назначение на игру – выбор соперника, с которым не играл;
3) игра – изменение числа добытых очков в зависимости от
введенного результата партии;
4) квалификация – повышение разряда (меньше на 1), если отношение выигранных очков к числу сыгранных партий больше ½,
в этом случае процедура сбрасывает число сыгранных партий на 0,
а число очков на (разряд – 5)*0,05;
5) отчисление – если за турнир все партии проиграл.
Запрос. Список команд, включающих наибольшее число шахматистов, имеющих самый высокий разряд в команде и сыгравших
наименьшее число партий в команде.
18. Динамическая ситуация. Читальный зал со списком книг
(список претендентов, занятость) и списком читателей (список
взятых книг, список прочитанных книг, список заказа). Состояния
читателя:
1) запись – формирование заказа;
2) сдача-выдача – сдача прочитанных книг, выдача тех книг
заказа, которые свободны.
Запрос. Список абонентов, сдающих минимальное количество
книг, на которые претендуют максимальное число других читателей.
19. Динамическая ситуация. Перевозки маршрутками со списком маршруток (номер, список пунктов прохождения, пункт местонахождения, список пассажиров маршрутки) и списком пассажиров (пункты посадки и высадки, список подходящих маршруток). Состояния пассажира:
1) появление пассажира – определяются пункты посадки, высадки и список подходящих маршруток;
2) посадка – в маршрутку из списка подходящих, если ее пункт
местонахождения совпадает с пунктом посадки;
3) поездка – учет в списке пассажиров маршрутки;
4) высадка – пункт местонахождения маршрутки совпадает с
пунктом высадки.
Состояния маршрутки:
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1) посадка – пункт местонахождения маршрутки совпадает с
пунктами посадки пассажиров;
2) движение – к следующему в списке пункту прохождения.
Запрос. Список маршруток, имеющих наибольшее число пунктов прохождения общих с другими маршрутками, на которых садится наибольшее число пассажиров.
20. Динамическая ситуация. Торговля со списком товаров (цена, количество – пополняемое) и очередью покупателей (список
товаров для покупки с количествами, кошелек – пополняемый).
Состояния покупателя:
1) занять очередь – определить список товаров для покупки;
2) касса – рассчитаться за товары; если денег не хватило, повторно занять очередь с предварительным пополнением кошелька;
3) пополнение кошелька – добавление денег.
Состояния торговли:
1) пополнение товарами – если нет покупателей или не хватило товара;
2) продажа – расчет покупателя, если товаров хватает.
Запрос. Список покупателей, закупающих наибольшее число
дефицитных товаров (их количества не хватит всем желающим купить).
21. Динамическая ситуация. Биржа труда со списками рабочих мест, определяемых профессией и ставкой, и безработных,
определяемых профессиями и рейтингом (квалификацией). Состояния безработного:
1) постановка на учет – определяются профессии безработного и рейтинг;
2) появление места – все профессии и рейтинг определены;
3) зачисление – рейтинг безработного больше рейтингов других претендентов на это место.
Формирование списка безработных, получивших место.
Запрос. Список безработных, обладающих наименьшим рейтингом и наибольшим количеством профессий, для которых нет
рабочих мест.
22. Динамическая ситуация. Приемные экзамены со списком
факультетов (число мест, список экзаменов на факультет, список
абитуриентов на факультет), списком экзаменов (список абитуриентов с оценками по экзамену) и списком абитуриентов (список
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
заявленных абитуриентом факультетов, список экзаменов с оценками). Состояния абитуриента:
1) подача заявления – определение ранжированного списка факультетов и списка экзаменов;
2) экзамен – определение оценки; при неудовлетворительной
оценке забирает документы;
3) зачисление – при сдаче всех экзаменов после конкурса.
Состояния приема:
1) прием заявлений – определение списков факультетов и экзаменов;
2) экзамен – определение оценок для всех сдающих этот экзамен абитуриентов;
3) конкурс – после сдачи всех экзаменов по следующему алгоритму:
1. ранжирование абитуриентов по набранным баллам на каждый факультет;
2. зачисление абитуриентов на первый факультет в их списке, если они
в списке факультета входят в число мест факультета;
3. коррекция для каждого факультета числа оставшихся мест и оставшегося ранжированного списка абитуриентов; остановка алгоритма, если
оставшихся мест ни на один факультет нет;
4. коррекция для оставшихся абитуриентов их ранжированных списков
факультетов вычеркиванием первого факультета; переход на п. 2.
Запрос. Список абитуриентов, не сдавших хотя бы 1 экзамен на
каждый заявленный факультет.
23. Динамическая ситуация. Руководство студенческой научной работой определяется списками студентов и преподавателей
по кафедре специализации студента. Состояния студента:
1) без руководителя – курс ниже 3-го;
2) перевод на следующий курс (отчисление после последнего
курса);
3) назначение руководителя – 3-й курс;
4) изменение руководителя – курс выше 3-го.
Запрос. Список кафедр, на которых специализируется наибольшее число студентов, и при этом ими руководит наименьшее
число преподавателей.
24. Динамическая ситуация. Зачетная сессия определяется
списками студентов (список зачетных предметов с отметкой за12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
чет/незачет) и списком предметов (список сдающих зачет в зависимости от номера курса). Состояния студента:
1) подготовка – нет сданных зачетов;
2) зачеты – все зачеты определены;
3) допуск в экзаменационную сессию – срок прошел.
Запрос. Список студентов, которые не сдали зачет по наибольшему числу предметов для студента.
25. Динамическая ситуация. Самодеятельность со списками
руководителей (список кружков руководителя и список учеников
руководителя), кружков (руководитель и список учеников) и учеников (список кружков). Состояния ученика:
1) запись в кружки;
2) работа в кружках;
3) уход из кружка.
Запрос. Список кружков, руководитель которых имеет и другие кружки, а ученики которых другие кружки не посещают.
26. Динамическая ситуация. Работа со списками отделов (руководитель, список работников отдела) и работников (отдел,
стаж). Состояния работника:
1) прием – стаж равен 0;
2) повышение – увеличение стажа на 1, если стаж не пенсионный;
3) проводы на пенсию – достигнут пенсионный стаж.
Запрос. Список новых работников (стаж равен 0), работающих
в отделах с наибольшим числом работников.
27. Динамическая ситуация. Трамвайные маршруты со списками маршрутов (список трамваев маршрута, упорядоченный
список остановок маршрута), остановок (список маршрутов),
трамваев (список маршрутов). Состояния остановки:
1) подготовка – маршрутам не присвоена;
2) определение маршрутов;
3) удаление остановки.
Запрос. Список трамваев, маршруты которых имеют наибольшее количество остановок общих с другими маршрутами.
28. Динамическая ситуация. Библиотека со списками книг (количество экземпляров), читателей (списки взятых, потребных и
сдаваемых книг). Состояния читателя:
1) заявка – формирование списка потребных книг;
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2) чтение – формирование списка сдаваемых книг;
3) обмен – сдача прочитанных книг, получение заявленных
книг, если есть свободные экземпляры.
Запрос. Список книг, имеющих свободный экземпляр и наибольшее число читателей, взявших книгу.
29. Динамическая ситуация. Торговля со списком товаров (цена, количество – пополняемое) и очередью покупателей (список
товаров для покупки с их количествами, кошелек – пополняемый).
Состояния покупателя:
1) занять очередь – определить список товаров для покупки;
2) пополнение кошелька – добавление денег;
3) покупка – рассчитаться за товары; если товара не хватило,
повторно занять очередь.
Состояния торговли:
1) подвоз товаров – если нет покупателей или не хватило товара;
2) продажа – расчет покупателя, если у него хватает товаров и
денег.
Запрос. Список покупателей, желающих купить товары на
наибольшую сумму по сравнению с покупателями, стоящими в
очереди сзади.
30. Динамическая ситуация. Чемпионат по футболу со списками команд (список футболистов, список игр), футболистами
(разряд, число добытых очков, занятость в игре), игр (упорядоченный список игроков, забивших голы). Состояния футболиста:
1) зачисление в команду – начальные значения параметров
(разряд=4);
2) назначение на игру – формирование списка на игру;
3) игра – формирование списка игроков, забивших голы;
4) квалификация – повышение разряда (меньше на 1), если отношение добытых очков к сыгранным играм >1,5 в этом случае
сбрасывает число игр на 0, а число добытых очков делает равным
(разряд – 5)*10.
Запрос. Список футболистов, команды которых сыграли наибольшее число игр и имеют наибольшее число игроков с наибольшим разрядом в команде.
31. Динамическая ситуация. Кафе со списками блюд (с ценой)
и очередью клиентов (деньги, список заказа). Состояния клиента:
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1) занять очередь – стать последним; при этом список заказанных блюд пустой;
2) стоять в очереди – определить список заказа, если не первый и не последний в очереди;
3) заплатить – если первый в очереди; если денег не хватило,
отказаться от самого дорогого заказанного блюда.
Запрос. Список блюд, которое заказало наибольшее число клиентов, стоящих в очереди и способных оплатить свой заказ.
32. Динамическая ситуация. Поликлиника со списками врачей
(список больных, специализация: терапевт, хирург, невропатолог)
и больных (лечащий врач, диагноз). Состояния больного:
1) диагностика – у терапевта определяется диагноз;
2) лечение – определяется лечащий врач;
3) выписка – удаление из списка.
Запрос. Список врачей, имеющих наибольшее число больных с
определенным диагнозом.
33. Динамическая ситуация. Сады со списками садовников
(список деревьев, возможность – максимальное число деревьев, за
которыми может ухаживать) и деревьев (садовник, возраст, число
плодов). Состояния дерева:
1) посадка – начальные данные;
2) цветение – увеличение возраста на 1 год;
3) созревание – определение числа плодов;
4) урожай – сбор урожая.
Запрос. Список садовников, имеющих наибольшее число плодов от своих деревьев.
34. Динамическая ситуация. Маркетинг со списками магазинов
(списки имеющихся и дефицитных товаров), товаров (количество,
список магазинов с товаром) и продаж (магазин, товар, количество). Состояния товара:
1) завоз товара в магазин – увеличение количества;
2) продажа – уменьшение количества; если нехватка, переход
в дефицитные.
Запрос. Список магазинов, имеющих наименьший список дефицитных товаров и при этом наибольший ассортимент товаров.
35. Динамическая ситуация. Авиамаршруты со списками авиарейсов (пункт вылета, пункт посадки, список пассажиров, вмести15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
мость пассажиров) и пассажиров (пункт вылета, пункт назначения,
маршрут). Состояния авиарейса:
1) посадка – садятся пассажиры, чей пункт вылета совпадает с
пунктом вылета авиарейса и авиарейс входит в его маршрут;
2) полет – список пассажиров не меняется;
3) прилет – пассажиры выходят.
Состояния пассажира:
1) покупка билетов – определяются пункты вылета и назначения, а также маршрут с наименьшим числом пересадок;
2) полет;
3) высадка – изменение пункта вылета на следующий пункт
маршрута.
Запрос. Список пассажиров, которые могут достигнуть пункта
назначения лишь с наибольшим числом пересадок.
36. Динамическая ситуация. Комплектация изделий со списками изделий разного типа:
1) деталь – не содержит других изделий;
2) агрегат – содержит другие изделия.
Состояния комплектации:
1) сборка – включение в изделие других комплектующих изделий;
2) приемка – составление для изделия итогового списка всех
деталей (как непосредственно включенных, так и входящих в агрегаты) с их суммарным количеством по каждой детали.
Запрос. Список изделий, содержащих наибольший ассортимент деталей и при этом их наименьшее количество.
37. Динамическая ситуация. Троллейбусное движение со списками маршрутов (циклический упорядоченный список остановок
маршрута и список троллейбусов маршрута), троллейбусов (маршрут, остановка следования) и остановок (тип: обычная, по требованию, конечная). Состояния троллейбуса:
1) выход на линию – определение маршрута и остановки следования, как одной из конечных;
2) движение – к следующей остановке по маршруту, которая
становится остановкой следования.
Запрос. Список троллейбусов, находящихся в наибольшем количестве на одной и той же остановке следования.
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
38. Динамическая ситуация. Первенство факультетов со списками соревнований (список факультетов, списки игр проведенных
и предстоящих с командами других факультетов), факультетов
(список соревнований), игр (2 факультета, очки каждому: 2 – выигрыш, 1 – ничья, 0 – проигрыш). Состояния игры:
1) не проводилась – очки не определены;
2) закончилась – определяется победитель.
Запрос. Список факультетов, имеющих наименьшее число команд, участвующих в соревнованиях и при этом набравших наибольшее число очков.
39. Динамическая ситуация. Зрелище со списками театров
(репертуар: список пар «дата – пьеса»), пьес (список театров, ставящих пьесу), зрителей (список желаемого просмотра, план: список пар посещения «дата – пьеса»). Состояния зрителя:
1) желание – определение желаемого просмотра пьес;
2) планирование – максимальный план, при котором зритель
посещает максимальное число постановок, но в 1 день не может
смотреть 2 пьесы;
3) замена – изменение плана, когда пьеса снята из репертуара
на запланированный день.
Запрос. Список театров, имеющих наименее разнообразный
репертуар и при этом наибольшее число зрителей, пожелавших
приобрести билеты на спектакли театра.
40. Динамическая ситуация. Дешевые обеды со списками столовых (список клиентов столовой, меню: список пар «блюдо – цена»), клиентов (список желаемых блюд; столовая) и блюд (список
столовых, имеющих блюдо). Состояния клиента:
1) заказ – определение списка желаемых блюд;
2) выбор – столовой с наиболее дешевым обедом;
3) обед.
Запрос. Список наиболее экономичных столовых для каждого
клиента.
41. Динамическая ситуация. Экономичные покупки со списками
магазинов (прейскурант: список пар «товар – цена», список покупок: пары «покупатель – товар»), товаров (список магазинов,
имеющих товар) и покупателей (список товаров для покупки и
список покупок: «магазин – товар»). Состояния покупателя:
1) заказ – определение списка товаров;
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2) выбор магазинов – с наиболее низкими ценами;
3) покупки – поход по магазинам.
Запрос. Список магазинов наиболее дешевых покупок для каждого покупателя.
42. Динамическая ситуация. Телевидение со списками ТВканалов (список зрителей канала, список передач: пары «время –
передача»), передач (список ТВ-каналов, ведущих передачу), зрителей (список желаемых передач, план просмотра: пары «передача – ТВ-канал»). Состояния зрителя:
1) заявка – составление списка желаемых передач;
2) планирование – составление максимального плана;
3) просмотр.
Запрос. Список планов с максимальным числом передач из заказов для каждого зрителя.
43. Динамическая ситуация. Семестр со списками предметов
(список студентов, слушающих предмет; план лекций: список пар
«преподаватель – номер семестра»), преподавателей (список проводимых преподавателем предметов: пары «предмет – номер семестра») и студентов (семестр, список слушаемых студентом предметов, список слушаемых студентом преподавателей). Состояния
студента:
1) начало семестра – составление списка предметов для слушания;
2) занятия – составление списка слушаемых преподавателей.
Запрос. Список предметов, которые ведет минимальное число
преподавателей и при этом слушает наибольшее число студентов.
44. Динамическая ситуация. Труд со списками предприятий
(директор, список отделов), отделов (менеджер, список работников) и работников (стаж, статус: обычный, менеджер отдела, директор). Состояния отделов:
1) слияние двух отделов предприятия – менеджер первого становится менеджером нового, а менеджер второго увольняется;
2) разделение отдела – выделение из отдела нового отдела с
менеджером, обычным работником отдела с наибольшим стажем, и
списком работников, идущих в списке отдела после менеджера.
Состояния работника:
1) прием на работу – обычный работник со стажем 0;
2) стаж – увеличение на 1;
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3) повышение – статуса;
4) увольнение.
Запрос. Список предприятий, имеющих наибольшее число отделов с максимальным суммарным стажем работников.
45. Динамическая ситуация. Поездки в автобусе со списками
остановок, автобусов (упорядоченный список остановок автобуса,
остановка следования, список пассажиров) и пассажиров (остановки посадки, высадки, список подходящих автобусов). Состояния пассажира:
1) готовится к поездке – определяются остановки посадки,
высадки и список подходящих автобусов;
2) ждет – на остановке;
3) посадка – в автобус;
4) поездка;
5) высадка – на остановке высадки.
Запрос. Список остановок, на которых находится наибольшее
число автобусов с наибольшим числом пассажиров в автобусе для
данной остановки.
46. Динамическая ситуация. Конкурсный прием со списками
экзаменов, факультетов (количество свободных мест, занятых
мест, список абитуриентов факультета, список экзаменов факультета) и абитуриентов (список заявленных факультетов, список экзаменов: пары «экзамен – оценка», список факультетов, куда прошел, выбранный факультет). Состояния абитуриента:
1) подача заявления – определение заявленных факультетов;
2) экзамены – изменение оценок;
3) конкурс – определение для каждого факультета списка абитуриентов, набравших наибольшую сумму баллов по числу свободных мест;
4) выбор факультета – коррекция числа свободных и занятых
мест на выбранном факультете и списков для других факультетов.
Запрос. Список абитуриентов, подавших заявление на наибольшее число факультетов и при этом сдавших не менее одного
экзамена на каждый факультет.
47. Динамическая ситуация. Трудовой набор со списками профессий, предприятий (список свободных профессий на предприятии, список приглашенных претендентов на предприятие, список
принятых работников) и претендентов (список профессий претен19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
дента, список заявленных предприятий, список пригласивших
предприятий, выбранное предприятие). Состояния предприятия:
1) потребность – определение списка потребных профессий;
2) приглашение – определение списка приглашенных претендентов;
3) зачисление – определение списка принятых работников.
Состояния претендента:
1) поиск работы – определение списка профессий;
2) заявление – определение списка предприятий;
3) выбор – из списка пригласивших предприятий.
Запрос. Список профессий, требующихся максимальному числу предприятий и при этом имеющих наименьшее число претендентов.
48. Динамическая ситуация. Выбор руководителя со списками
руководителей (кафедра, список руководимых студентов, список
студентов руководителя, список студентов, заявивших руководителя, количество свободных мест для руководителя) и студентов
(курс, упорядоченный список заявленных руководителей, выбранный руководитель). Состояния руководителя:
1) объявление набора – определение количества свободных
мест;
2) выбор студентов – из списка каждого студента, заявившего
руководителя первым;
3) конец набора – удаление руководителя из списков студентов, заявивших руководителя, но не выбранных им.
Состояния студента:
1) выбор не нужен – курс не 3-й;
2) заявление руководителя – составление упорядоченного списка заявленных руководителей;
3) выбор – руководителя.
Запрос. Список кафедр с максимальным числом студентов,
претендующих на одного руководителя.
49. Динамическая ситуация. Маршруты трамваев со списками
маршрутов (список трамваев маршрута, упорядоченный циклический список остановок маршрута, количество трамваев маршрута),
остановок (тип: обычная, по требованию), трамваев (список маршрутов). Состояния маршрута:
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1) остановки – определение упорядоченного циклического
списка остановок;
2) трамваи – определение трамваев маршрута.
Запрос. Список остановок по требованию, имеющих наибольшее число маршрутов, для которых число трамваев минимально.
50. Динамическая ситуация. Лесничества со списками лесников (список участков лесника, ограничение возрастов вырубки и
подсадки), участков леса (лесник, список деревьев: пары «возраст – количество», ограничения количества деревьев), деревьев
(пары «возраст – количество»). Состояния лесника:
1) план – составление для каждого участка списка деревьев для
вырубки и списка деревьев для подсадки с проверкой ограничений;
2) вырубка – уменьшение количества деревьев на участке;
3) посадка – увеличение количества деревьев на участке.
Запрос. Список лесников с максимальным количеством участков, на которых заготовки минимальны для каждого лесника.
51. Динамическая ситуация. Лабораторный практикум со списками лабораторий (список студентов лаборатории, план работ:
пары «преподаватель – номер семестра»), преподавателей (список
лабораторных работ: пары «лаборатория – номер семестра») и
студентов (семестр, список заданных студенту лабораторных работ, список выполненных лабораторных работ). Состояния преподавателя:
1) планирование – определение плана работ;
2) занятия – определение списков студентов для каждой работы.
Состояния студента:
1) выдача работ – определение списка работ для студента;
2) выполнение – определение списка выполненных работ.
Запрос. Список лабораторий с максимальным количеством
студентов, выполняющих работы у минимального числа преподавателей для каждой лаборатории.
52. Динамическая ситуация. Программистский проект со списками программ (разряд программы, программист) и программистов (категория программиста, резюме: список выполненных программ как пар «разряд программ – количество программ»). Состояния программы:
1) задание – определение программиста;
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2) выполнение;
3) сдача – корректировка резюме программиста.
Запрос. Список программистов, выполняющих наибольшее количество программ с наименьшим разрядом для каждого программиста.
53. Динамическая ситуация. Студенческий обед со списками
блюд (объем, цена) и студентов (кошелек: деньги на обед, аппетит: желаемый суммарный объем блюд, список выбранных студентом блюд). Состояния студента:
1) перевод – пополнение кошелька;
2) желание – определение аппетита;
3) выбор – определение списка блюд, наиболее близких по
суммарному объему;
4) касса – расчет, если денег в кошельке хватает;
5) отказ – замена наиболее дорогого блюда на более дешевое с
близким объемом.
Запрос. Список блюд студентов, аппетит которых превышает
возможности кошелька.
54. Динамическая ситуация. Конкурсы в вузы со списками вузов
(список факультетов вуза, список абитуриентов вуза), факультетов
(вуз, список экзаменов факультета, проходной балл, список абитуриентов факультета, список зачисленных), абитуриентов (список заявленных вузов – факультетов, список сданных экзаменов с оценками)
и экзаменов (вуз, факультет). Состояния абитуриента:
1) заявления – определение списка вузов – факультетов;
2) экзамены – определение оценок по экзаменам;
3) конкурс – определение вузов – факультетов, на которые набран проходной балл;
4) зачисление – выбор вуза – факультета.
Запрос. Список вузов, имеющих наименьшее число факультетов с максимальным числом абитуриентов на факультет для каждого вуза.
55. Динамическая ситуация. Очереди в магазинах со списками
товаров, магазинов (список товаров магазина: «товар – количество – цена», очередь покупателей: упорядоченный список) и покупателей (список необходимых товаров: «товар – количество», кошелек: количество денег). Состояния покупателя:
1) желание – определение необходимых товаров;
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2) планирование – определение списка «товар-магазин»;
3) очередь – занять очереди в магазинах;
4) покупка – в том магазине, где покупатель первый.
Запрос. Список товаров, имеющихся в максимальном количестве магазинов и требующихся покупателям, которые стоят первыми в очереди.
56. Динамическая ситуация. Отдых со списками туристов
(список желаемых мест с примерными сроками, путевка),
агентств (список путевок: пар «путевка – количество», список туристов агентства) и путевок (агентство, место отдыха, сроки, количество). Состояния туриста:
1) желание – определение срока и списка желаемых мест;
2) поиск – агентства с путевкой, наиболее подходящей (сроки
наименее отличаются по сумме отклонений начала и конца);
3) покупка – изменение списков туристов и путевок агентства.
Запрос. Список путевок, по которым места отдыха и сроки
удовлетворяют возможно большее число туристов и при этом
имеются в максимальном количестве агентств.
4. Методика оценивания трудоемкости
алгоритма и построения характеристик
временной сложности программного кода
В практической деятельности выпускников специальностей
Прикладная математика и информатика и Математическое
обеспечение и администрирование информационных технологий
весьма важным является умение снабдить разрабатываемую программу выводом для пользователя информации о времени ее выполнения или о доле уже выполненной работы. Это особенно касается тех случаев, когда программа слишком продолжительна по
времени. Существуют два подхода к достижению этой цели:
1. В первом случае программа содержит циклы в явном виде,
ее можно разбить на непересекающиеся циклы и при этом можно
выделить главный цикл – основной по трудоемкости алгоритма.
Это особенно легко сделать тогда, когда такой внешний цикл единственный, и потому можно и не использовать оценку его трудоем23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
кости. Вставим перед этим главным циклом программный код,
оценивающий число повторений цикла, скажем, в переменной All,
а внутрь главного цикла, но не в его подциклы, вставим увеличение счетчика Count главного цикла и вывод процентного отношения Count/All*100 всей работы в текстовом или графическом виде
при помощи шкалы прогресса. Если при этом программный код
внутри этого цикла выполняется долго (например, более секунды),
то в этом коде также найдем вложенный цикл, являющийся главным по трудоемкости. Затем вставим перед его выполнением программный код, оценивающий число его повторений, скажем, в переменной All1, а внутрь его вставим код увеличения счетчика
Count, обнуленного перед главным циклом, и вывод процентного
отношения Count/(All*All1)*100 или связанного с этим значением
шкалы прогресса. Поступая также дальше при долгом выполнении
кода внутри второго цикла, мы, в конце концов, найдем приемлемое решение. Преимущество такого подхода в его простоте. Однако ряд недостатков затрудняет его использование или делает совсем невозможным:
1) внешний цикл программы может быть не единственным, и в
этом случае не всегда легко оценить трудоемкость каждого внешнего цикла;
2) при одинаковой трудоемкости нескольких внешних циклов
нужно уметь оценить долю времени выполнения каждого из этих
циклов, что уже требует более тонкого анализа алгоритма и определения характеристик временной сложности;
3) наконец, циклов в явном виде может не быть: например, при
выполнении SQL-операторов циклы скрыты в его конструкциях,
которые не позволяют вставлять код (да и если бы такое было возможно, мы бы узнали о его результате только после полного выполнения SQL-оператора).
2. Во втором случае программа не содержит циклы в явном виде (см. выше). Тогда необходимо уметь разработать программный
код, который перед выполнением программы или ее части оценивает время выполнения и информирует пользователя. Для этого
выполняется следующая последовательность действий:
1) оценивается трудоемкость алгоритма программы (максимальная, минимальная и средняя);
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2) на основе этих оценок строится вид функций временной
сложности программы (максимального, минимального и среднего
времени в зависимости от параметров программы);
3) разрабатываются тесты с различными параметрами программы для определения неизвестных коэффициентов характеристик временной сложности программы;
4) проводится тестирование программы с целью определения
времени ее выполнения в зависимости от набора параметров программы;
5) проводится численный расчет коэффициентов характеристик временной сложности с целью приближенного определения
этих характеристик;
6) проводится тест производительности компьютера, на котором определены характеристики временной сложности, с целью их
коррекции на компьютере использования;
7) строится код определения временных характеристик в зависимости от параметров программы и код теста производительности
для определения коэффициента коррекции, этот код встраивается
для выполнения перед вызовом программы (или ее части) с целью
вычисления и выдачи пользователю ожидаемого временного интервала выполнения программы и среднего времени этого ожидания.
Несомненно, является полезным использование такого подхода
в различных курсах обучения указанным специальностям, связанным с разработкой и анализом алгоритмов.
4.1. Анализ алгоритмов
и методика оценивания трудоемкости
В качестве основной характеристики сложности алгоритма
принято рассматривать число шагов t исполнения алгоритма. Однако t зависит от исходных данных задачи. Зависимость эта в
большинстве случаев является весьма сложной, и не всегда ее возможно анализировать непосредственно. В то же время, если мы
непосредственно не можем предсказать, сколько будет выполняться алгоритм, то разумно потребовать меньшее: каковы будут временные рамки выполнения алгоритма (максимальное и минимальное время), сколько в среднем будет выполняться алгоритм (среднее время)? Но для любых вариантов задачи время (число шагов)
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ничем не ограничено. Так, при сортировке массива время, как правило, зависит от длины массива и растет с ростом числа элементов
массива.
Принято входные данные V алгоритма характеризовать одним
параметром или несколькими параметрами. Одной из таких характеристик является объем входных данных – число элементов входных данных. Эта характеристика объективно характеризует входные данные так же, как и число шагов объективно характеризует
исполнение алгоритма. В свою очередь, устанавливают зависимость объема входных данных от одного или нескольких параметров, характеризующих задачу. Так, в задаче сортировки массива
таким параметром является длина n массива, в задаче нахождения
кратчайшего пути в графе объем входных данных связан с числом
n вершин графа, а в задаче нахождения кратчайшего остовного дерева объем данных зависит от числа m ребер графа. В других задачах оптимизации на графах в качестве параметров выбирается и
число n вершин, и число m ребер.
Так как число шагов алгоритма зависит не только от выбранных в задаче параметров P=(n, m, …), характеризующих объем
входных данных V=(P,X), но и от других характеристик входных
данных X=(x1, x2,…), то мы введем оценку по всем этим характеристикам. Оценка наибольшего числа шагов, необходимых для выполнения алгоритма, в зависимости от параметров P:
t = t(P,X) ≤ maxx t(P,X) ≡ T(P),
называется максимальной трудоемкостью алгоритма, или просто
трудоемкостью алгоритма. Максимальная трудоемкость дает нам
возможность оценить максимальное время, необходимое для исполнения алгоритма. Эта оценка может быть очень завышенной в
некоторых случаях. Поэтому важно иметь оценку наименьшего
числа шагов, которую мы назовем минимальной трудоемкостью:
t = t(P,X) ≥ minx t(P,X) ≡ Tmin(P),
и оценку среднего числа шагов, которую мы назовем средней трудоемкостью:
t = t(P,X) ≤ 1/k∑x t(P,X) ≡ Tcp(P),
где k – число вариантов других характеристик входных данных.
Для простоты мы будем предполагать, что задача имеет 1 параметр n, и обращать внимание на отличия, когда это не так. Тру26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
доемкость алгоритма позволяет оценить время выполнения алгоритма при решении той или иной задачи:
Tф(X) ≤ τ·T(n).
При этом коэффициент τ статистически определяется для исполнителя или оценивается (что чаще бывает) некоторой константой.
Однако точный вид зависимости T(n) от аргумента n часто
очень трудно (практически невозможно) установить. Поэтому вместо установления вида функции для трудоемкости оценивается быстрота роста этой функции при помощи некоторой простой функции f(n). Говорят, что
T(n) = O(f(n)),
если |T(n)| ≤ C| f(n)| для всех значений n > n0. Такая оценка роста
функции T(n) является односторонней, так как функция f(n) может
расти быстрее. Лучше оценивать рост трудоемкости функцией f(n),
имеющей тот же порядок роста, т. е. также |T(n)| ≥ C1| f(n))|. В этом
случае пишут
T(n) = Θ(f(n))
и говорят, что рост T(n) оценивается ростом f(n). Наиболее простыми функциями, оценивающими рост трудоемкости, являются
полиномы p(n) = nk + c1nk-1 +…+ ck. В случае T(n) = Θ(p(n)), учитывая, что p(n) = Θ(nk), получаем T(n) = Θ(nk). Говорят, что в этом
случае трудоемкость полиномиальна, или алгоритм имеет полиномиальную трудоемкость. При k = 1 T(n) = Θ(n), и алгоритмы принято называть алгоритмами с линейной трудоемкостью.
Если есть 2 алгоритма A1 и A2 решения некоторой задачи и оба
имеют полиномиальную трудоемкость, причем k1< k2, то говорят,
что первый алгоритм имеет меньшую трудоемкость. Но меньшая
трудоемкость не означает, что время решения задачи первым алгоритмом будет меньше, чем вторым. Так, пусть
90n ≤ T1 (n) ≤ 100n, 9n2 ≤ T2 (n) ≤ 10 n2.
Тогда при n < 10 оказывается, что время решения задачи для
первого алгоритма больше, чем для второго. Однако из определения
ясно, что найдется такое n0 (в примере n0 = 10), что время решения
задачи при n > n0 будет всегда меньше для первого алгоритма.
Трудоемкость алгоритма может иметь скорость роста меньшую,
чем линейная. Например, T(n) = Θ(√n) или T(n) = Θ(log n). Но и в
этом случае принято говорить о полиномиальной трудоемкости.
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Алгоритмы, трудоемкость которых растет быстрее любого полинома, принято называть алгоритмами экспоненциальной трудоемкости, даже если скорость роста трудоемкости оценивается более
медленной функцией, чем экспонента. Например, экспоненциальными являются все алгоритмы со следующими трудоемкостями:
T(n) = Θ(2n), T(n) = Θ(2√n), T(n) = Θ(2nm ).
Причина, по которой используются только эти 2 названия трудоемкости (полиномиальная и экспоненциальная), состоит в том,
что алгоритмы полиномиальной трудоемкости, как правило, эффективны, если показатель степени у полинома не слишком большой. А алгоритмы экспоненциальной трудоемкости не являются
эффективными, так как время вычисления по этим алгоритмам растет «космически» быстро.
Заметим теперь, что при нескольких параметрах входных данных трудоемкость полиномиального алгоритма растет как полином
от нескольких аргументов. Например,
T(n,m) = Θ(n·m2), T(n,m,k) = Θ(n2k·log m).
Процесс получения оценки трудоемкости называется оцениванием трудоемкости. Для этого следует анализировать алгоритм с
точки зрения быстроты роста числа его шагов при изменении параметров задачи (параметров входных данных).
Прежде всего, в алгоритме следует выделить циклы. Если циклов нет, то число шагов линейной структуры алгоритма не зависит
от параметров задачи, и, следовательно, трудоемкость является
константной, т. е. оценивается как Θ(1).
Циклическая структура алгоритма ведет к повторению выполнения его частей, что влияет на общее число шагов выполнения, т.
е. на трудоемкость. Следует оценить для каждого цикла, от каких
параметров задачи зависит число повторений цикла и как оно растет с ростом этих параметров.
Если цикл B с числом повторений n(B) вложен в цикл A с числом повторений n(A) и циклы независимы (число повторений цикла B не зависит от выполнения цикла A), то общее число повторений цикла B с учетом повторений цикла A составляет n(A)·n(B). Отсюда правило: для вложенных независимых циклов их трудоемкости перемножаются
Θ(AB)= Θ(A) · Θ(B).
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Если вложенные циклы не являются независимыми, т. е. число
повторений внутреннего цикла ni(B) зависит от номера i повторения при выполнении внешнего цикла, то нужно проанализировать,
как зависит общее число повторений внутреннего цикла
n(A)
∑ ni(B)
i=1
от параметров задачи.
Если циклы не являются вложенными, то трудоемкость определяется наибольшей из трудоемкостей циклов
Θ(A+B) = Θ(A) + Θ(B) = max {Θ(A), Θ(B)}.
Заметим теперь, что при оценке максимальной трудоемкости
следует подбирать такие примеры входных данных для тех или
иных параметров задачи, на которых реализуется максимальное
число шагов алгоритма. При оценке минимальной трудоемкости
следует подбирать примеры, на которых реализуется минимальное
число шагов алгоритма. Ввиду сложности некоторых алгоритмов
такие примеры не всегда удается построить, но в таких случаях для
оценки трудоемкости бывает достаточно примеров, близких по
числу операций к максимальному или соответственно к минимальному числу.
Рассмотрим ряд примеров оценивания трудоемкости.
Пример 1. Алгоритм Дейкстры нахождения кратчайшего пути
между вершинами a и b связного графа G(X,U). Пусть n = |X| – число вершин графа и l(xi,xj) – расстояние от xi до xj. Можно привести
следующее пошаговое описание алгоритма:
1. Определить начальный список S помеченных вершин, включив в него a(0) (в скобках – пометка), начальное значение последней помеченной вершины last = a и начальный список непомеченных вершин N = {x1 (λ1),…}, записав в скобках расстояние от вершины до a: λi = l(a,xi), если (a,xi)ε U, или λi = ∞, если иначе.
2. Найти минимальное значение λj = mini λi.
3. Переместить вершину xj из списка N в список S с пометкой
значением last и определить новое значение last = xj.
4. Пересчитать значения λi для списка N, положив
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
λi =min {λi, λj + l(xj,xi)}.
5. Если xj = b, закончить выполнение алгоритма, иначе перейти к шагу 2.
В качестве параметра задачи естественно выбрать число n
вершин графа. Анализ алгоритма показывает, что он содержит несколько циклов:
1) цикл шага 1, который выполняется n-1 раз, т. е. его трудоемкость Θ(n);
2) выполнение шагов 2 – 5 повторяется, т.е. идет циклически.
Назовем этот цикл внешним. Его повторение зависит от входных
данных и максимально, когда вершина b включается в список S последней, и минимально, когда она включается сразу же за вершиной a. Поэтому при определении максимальной трудоемкости
нужно брать для этого цикла оценку Θ(n), а при определении минимальной трудоемкости – оценку Θ(1);
3) внутри внешнего цикла выполняются 4 шага, при этом шаги
3 и 5 не содержат циклов, и потому их трудоемкости оцениваются
как Θ(1). Шаги 2 и 4 содержат внутренние циклы, среднее число
повторений которых равно n/2. Поэтому трудоемкости каждого из
этих циклов можно оценить как Θ(n). Суммарная трудоемкость тела внешнего цикла равна Θ(n) + Θ(1) + Θ(n) + Θ(1) = Θ(n).
Учитывая полученные трудоемкости циклов, можно оценить
максимальную трудоемкость как
Θ(n) + Θ(n)·Θ(n) = Θ(n2),
а минимальную трудоемкость – как
Θ(n) + Θ(1)·Θ(n) = Θ(n).
Замечание. Внешний и внутренние циклы не являются независимыми – мы обошли эту трудность, взяв среднее число повторений внутренних циклов. Более аккуратно при оценивании максимальной трудоемкости следует брать число повторений внутренних циклов равным n-1, n-2,…, 1, и тогда повторение их тела во
внешнем цикле составит
(n-1) + (n-2) +…+1 = n(n-1)/2,
что также дает Θ(n2). При оценивании минимальной трудоемкости
внешний цикл выполняется 1 раз, а внутренний – (n-1) раз, поэтому
оценка трудоемкости будет Θ(n).
30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 2. Сортировка массива методом пузырька задана процедурой на C++:
void SortP (int n, float X[])
{ Bool b=true;
for (int k=n-1; b && k>0; k--)
for (int i=0, b=false; i<k; i++)
if (X[i]>X[i+1])
{
float r = X[i];
X[i] = X[i+1];
X[i+1] = r;
b=true;
}
}
Процедура содержит вложенные циклы. Внешний цикл в случае массива входных данных, упорядоченного по убыванию, будет
выполняться максимальное число раз: n-1, а в случае входного
массива, упорядоченного по возрастанию, будет выполняться
только 1 раз. Внутренний цикл во втором случае выполняется n-1
раз, а в первом случае циклы зависимы, но, как и в предыдущем
примере, внутренний цикл в среднем выполняется n/2 раз. Поэтому
максимальная трудоемкость (входные данные первого случая) оценивается как Θ(n)·Θ(n) = Θ(n2), а минимальная трудоемкость
(входные данные второго случая) – как Θ(1)·Θ(n) = Θ(n).
Пример 3. Оценить трудоемкость следующей процедуры на
С++ при n > 0:
long f (int n)
{
long j=1;
while (n>0) j<<=n--;
while (j>0) j>>=1;
return j;
}
Процедура имеет 2 цикла, не вложенных один в другой. Но начальное значение параметра j второго цикла определяется в первом
цикле, так что некоторая зависимость циклов есть. Первый цикл
будет выполняться ровно n раз, если n>0. Поэтому его трудоемкость оценивается как Θ(n). В результате выполнения первого цикла параметр j примет значение 2n+n(n+1)+…+1 = 2 n(n+1)/2. Второй цикл
будет выполняться log2 j=n(n+1)/2 раз, так как в теле цикла параметр j уменьшается ровно в 2 раза, и, значит, трудоемкость этого
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
цикла оценивается как Θ(n2). Поэтому трудоемкость процедуры
оценивается как Θ(n)+Θ(n2)=Θ(n2).
Пример 4. Оценить трудоемкость следующего SQL-оператора:
select e.EmpName, d.DeptName
from Emp e, Dept d
where e.DeptNo = d.DeptNo
Оператор имеет 2 цикла: по таблице Emp, длина которой n, и
по связанной с ней внешним ключом таблице Dept, длина которой
m. Если таблицы не проиндексированы совместно, то трудоемкость данного оператора оценивается как Θ(nm). Если же они проиндексированы совместно по полю DeptNo, которое является первичным ключом для таблицы Dept и внешним ключом для таблицы
Emp, то при эффективной организации выполнения SQL-оператора
трудоемкость может оцениваться как Θ(n), т.е. быть на порядок
меньше.
4.2. Характеристики
временной сложности программы
Оценка трудоемкости еще не позволяет ничего сказать о времени выполнения программы, реализующей алгоритм, для тех или
иных данных. Мы можем судить только о быстроте роста этого
времени. Скажем, если трудоемкость оценивается как Θ(n2), то с
увеличением параметра n в 2 раза требующееся время будет увеличиваться примерно в 4 раза. Такая качественная оценка не всегда
удовлетворяет нас. Допустим, что мы запустили программу, и она
уже выполняется 10 минут. Может, программа зациклилась и ее
следует снять? А если нет, то сколько она еще будет выполняться?
Таким образом, оценка времени выполнения программы может
стать актуальной. Если программа в начале своей работы выдает,
что интервал времени ожидания ее выполнения такой-то и в среднем придется ждать столько-то, то на такие данные можно опираться при принятии решения, следует ли продолжить счет.
Введем 3 статистические функции tmin(n), tmax(n), tcp(n), оценивающие время работы программы в зависимости от значения параметра n (при большем числе параметров задачи эти функции имеют
большее число аргументов). Их вид зависит от оценки соответствующей трудоемкости.
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рассмотрим вначале общий случай оценки трудоемкости полиномом T(n)=Θ(nk). В этом случае выбирается соответствующий
вид функции t(n)=ck nk+ck-1nk-1+...+c1n+c0. Здесь ci (i=1,…, k) – неизвестные коэффициенты, и мы рассматриваем не только коэффициент ck, который определяет время при довольно больших значениях
параметра n, но и коэффициенты при меньших степенях n, которые
могут влиять на время при малых значениях параметра n. Для получения значения коэффициентов ci (i=1,…, k) следует выбрать ряд
различных значений параметра n = n1, n2,..., np, где p > k. Затем для
каждого значения параметра nj выбрать данные, соответствующие
этому параметру, и провести вычислительный эксперимент с программой, замерив время ее выполнения τj. Затем по методу наименьших квадратов можно найти коэффициенты ci, которые минимизируют сумму квадратов отклонений полинома в точках nj от
значений τj:
p
∑ (t(nj)-τj)2.
j=1
Для более грубой оценки можно взять p=k+1 и решить систему
уравнений
k
∑ cinji = τj (j =1,…,k+1)
i=0
относительно неизвестных ci.
При оценке трудоемкости логарифмической функцией или
произведением полинома на логарифмическую функцию следует и
функцию времени t(n) строить в подобном виде. Так, при оценке
трудоемкости T(n)=Θ(n·log2 n) следует выбрать вид t(n) = c1nlog2 n
+ c2n + c3log2 n + c4, а при T(n) = Θ(n2log2n) следует выбрать вид t(n)
= c1n2log2n + c2n2 + c3nlog2n + c4n + c5log2n + c6. Проведя достаточное количество вычислительных экспериментов, построив и решив
соответствующую систему уравнений, можно найти коэффициенты
функции времени t(n).
При оценке трудоемкости T(n) = Θ(√ n) следует выбрать вид
t(n)=c1√ n+c2, а затем провести вычислительные эксперименты и
найти неизвестные коэффициенты, решив соответствующую систему уравнений.
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
При экспоненциальной оценке трудоемкости T(n) = Θ(2n) можно взять соответствующий вид функции t(n) = c1·c2n и, проведя
2 вычислительных эксперимента для n1, n2, найти τ1, τ2. Так как
τ1/τ2 = c2n1-n2, то c2 = (τ1/τ2)1/(n1-n2) и c1 = τ1c2-n1 = τ2c2-n2. Аналогичным
образом можно поступать при другом виде экспоненциальной
оценки трудоемкости.
В тех случаях, когда оценка трудоемкости алгоритма включает
в себя несколько параметров задачи, вид функций времени следует
выбирать соответствующим такому виду оценки трудоемкости.
Например, при T(n,m)=Θ(nm2) следует функцию времени искать в
виде
t(n,m) = c1nm2 + c2nm + c3n + c4m + c5.
И в других случаях следует поступать подобным образом.
Теперь сделаем 3 замечания относительно выбора данных, выбора ряда параметров задачи для вычислительного эксперимента и
организации проведения эксперимента:
1. При построении функции максимального времени следует
выбирать данные, приводящие к максимальному числу шагов алгоритма. Если не представляется возможным построить такие данные, то следует для каждого значения параметра nj провести не 1, а
много экспериментов (например, 10), и взять максимальное значение времени. Аналогичным образом следует поступать при построении функций минимального времени и среднего времени.
2. Значения параметров для вычислительного эксперимента
следует выбирать такими, чтобы время эксперимента не было
слишком малым, так как точность измерения времени имеет порядок ≈ 0.02 сек. Поэтому разумно выбирать значения параметров,
дающие время эксперимента не менее 10 сек. Однако в ряде случаев данные эксперимента могут составлять значительный объем, и
возникает проблема ввода таких данных и проблема памяти для
них. Первую из них можно решить программной генерацией данных, возможно, с использованием датчика случайных чисел, но
вторую проблему так просто одолеть не удается. Поэтому вместо
параметров, приводящих к значительным объемам данных, можно
выбрать меньшие значения параметров, но вызов процедуры повторять k раз (k=102,...,106) в цикле. Для исключения времени этого
цикла следует замерить время пустого цикла с таким же числом
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
повторений и вычесть его из времени цикла вызова процедуры.
Полученное значение времени следует разделить на k.
3. Ряд значений параметра (параметров) также нужно выбирать
разумным способом. Если трудоемкость оценивается как Θ(log n),
то выбор значений параметра n, отличающихся друг от друга на
несколько единиц, мало скажется на изменении времени эксперимента и потому приведет к большим погрешностям (система уравнений получится близкой к вырожденной). Поэтому в таком случае
каждое следующее значение параметра можно выбирать в 2 раза
больше предыдущего. Если же трудоемкость имеет экспоненциальную оценку, то, наоборот, не следует выбирать слишком далекие друг от друга значения параметра: так, при T(n)=Θ(2n) увеличение параметра на 10 ведет к увеличению времени в 1 000 раз. Будет разумным в этом случае, чтобы следующее значение параметра
было на 1 - 2 больше значения предыдущего.
Помимо полученных функций максимального, минимального
и среднего времени выполнения параметров следует также указать
производительность процессора, на котором производились вычислительные эксперименты. Для использования этих функций на
компьютере с другой производительностью следует всегда вычисленное значение функций умножать на отношение производительностей процессоров, для чего макросом задавать производительность используемого процессора.
В заключение сделаем следующее замечание. При вычислении
коэффициентов функций времени может оказаться, что коэффициент при самой старшей степени полинома ничтожно мал, в особенности по сравнению с коэффициентами других степеней. Это может говорить о том, что соответствующая трудоемкость оценена
неверно и на самом деле ее оценка ниже. В таком случае следует
повторить расчеты с более низкой оценкой трудоемкости и проконтролировать эти расчеты дополнительными экспериментами с
более высокими значениями параметров, для чего сравнить время
эксперимента и значение функции. Данный контроль необходим и
в случаях, когда такой ситуации нет. Если при контроле оказывается, что время эксперимента значительно превышает значение
функции, это говорит о том, что оценка соответствующей трудоемкости занижена. Необходимо и в этом случае пересмотреть оценку
трудоемкости и пересчитать коэффициенты функции.
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Содержание
1. Цель работы ....................................................................................................... 3
2. Общее задание.................................................................................................... 3
3. Варианты индивидуальных заданий ............................................................ 4
4. Методика оценивания трудоемкости алгоритма и построения
характеристик временной сложности программного кода................ 23
4.1. Анализ алгоритмов и методика оценивания трудоемкости ...... 25
4.2. Характеристики временной сложности программы .................. 32
Учебное издание
Рублев Вадим Сергеевич
Прогнозирование времени выполнения
программного кода
Методические указания
по лабораторному практикуму
Редактор, корректор О.Н. Скибинская
Компьютерная верстка Е.Л. Шелеховой
Подписано в печать 16.03.2007 г. Формат 60х84/16.
Бумага тип. Усл. печ. л. 2,09. Уч.-изд. л. 1,5.
Тираж 80 экз. Заказ
Оригинал-макет подготовлен
в редакционно-издательском отделе ЯрГУ.
Отпечатано на ризографе.
Ярославский государственный университет.
150000 Ярославль, ул. Советская, 14.
36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В.С. Рублев
Прогнозирование
времени выполнения
программного кода
38
Документ
Категория
Без категории
Просмотров
10
Размер файла
520 Кб
Теги
времени, прогнозирование, выполнения, 448, рублев, кода, программного
1/--страниц
Пожаловаться на содержимое документа