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

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

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

Для оценки эффективности алгоритма применяется функция сложности, обозначаемая O (читается «о большое»). На самом деле есть и другие оценки, но на этапе когда школьник только-только начинает знакомиться с различными алгоритмами они не очень нужны. Функция сложности отражает по какой закономерности будет расти время выполнения программы в зависимости от исходных данных или их количества.

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

Основными функциями являются:

l O(1) - такая функция сложности говорит о том, что время работы программы постоянно при любых исходных данных;

l O(N) - количество операций растет пропорционально N (здесь N может быть как параметром задачи, так и количеством элементов в массиве).

l O(log N) - количество операций растет пропорционально логарифму N (именно такой сложностью обладает, например, метод половинного деления при поиске элемента в упорядоченном массиве). При увеличении N на порядок количество операций меняется на единицу. Основание логарифма обычно не уточняется, нас интересует характер роста (быстро/медленно), а не точное значение времени.

l O(N2) - количество операций растет пропорционально квадрату N. В общем случае может быть O(Nk) в зависимости от сложности задачи.

l O(N!) - количество операций растет пропорционально факториалу N.

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

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

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

Сложим количество операций N+(N-1)+1=2N. То есть существует такая константа, что при любом N количество операций не превышает CN. Следовательно, сложность алгоритма равна O(N).

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

Алгоритм состоит из следующих шагов:

Ввод массива (N операций ввода) поиск элемента с заданным свойством (как повезет: элемент может находиться как ближе к началу массива, так и в самом конце; если элемента не существует, то необходимо сделать все N сравнений, чтобы в этом убедиться) вывод результата.

В лучшем случае данный алгоритм потребует N+2 операции (ввод всего массива, единственное сравнение, вывод), в худшем (когда такого элемента нет - 2N+1 операцию). Если N будет большим числом, к примеру порядка 106, то единицей можно пренебречь. Следовательно, сложность алгоритма равна O(N).

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

Алгоритм состоит из следующих шагов:

Ввод слова (одна операция) цикл по всем символам

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

2. вывод найденного символа

Конец цикла

Общее количество операций 1+(S+1)*L. В случае достаточно больших S и L единицами можно пренебречь, получится что функция сложности данного алгоритма есть O(S*L).

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

Алгоритм состоит из следующих шагов:

Цикл, пока результат деления числа на 2 не станет равным 0

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

2. принять результат деления за новое число

Конец цикла

Общее количество операций не превышает 1+log2N. Поэтому данный алгоритм имеет сложность O(log N).

Если программа состоит из нескольких частей с различными функциями сложности, то бо льшая функция сложности «поглотит» меньшие. Например, если делается ввод массива O(N), сортировка O(N2) и вывод упорядоченного массива за O(N), то можно сказать, что вся программа имеет сложность O(N2)

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

Вопросы

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

1. Определите функцию сложности алгоритма решения квадратного уравнения.

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

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

4. Определите функцию сложности алгоритма сложения двух натуральных чисел в столбик (пусть A - количество цифр первого числа, B - количество цифр второго).

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

Библиотека программиста

«Если отладка - процесс удаления ошибок, то программирование должно быть процессом их внесения»

Э.Дейкстра

1.2. Зачем изучать алгоритмы? Эффективность алгоритмов

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

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

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

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

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

1.3. Эффективность алгоритмов

Предположим, быстродействие компьютера и объем его памяти можно увеличивать до бесконечности. Была бы тогда необходимость в изучении алгоритмов? Да, но только для того, чтобы продемонстрировать, что метод развязку имеет конечное время работы и что он дает правильный ответ. Если бы компьютеры были неограниченно быстрыми, подошел бы произвольный корректный метод решения задачи. Конечно, тогда чаще всего избирался бы метод, который легче реализовать.

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

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

Как отмечалось выше, в этом разделе центральную роль будет посвящено задачи сортировка. Первый алгоритм, который будет рассматриваться - сортировка включением, для своей работы требует времени, количество которого оценивается как c 1 n 2 , где n - размер входных данных (Количество элементов в последовательности для сортировки), c 1 - Некоторая постоянная. Это выражение указывает на то, как зависит время работы алгоритма от объема исходных данных. В случае сортировки включением эта зависимость является квадратичной. Второй алгоритм - сортировка слиянием - требует времени, количество которого оценивается как 2 nLog 2 n. Обычно константа сортировки включением меньше константы сортировки слиянием, то есть c12 растет быстрее с увеличением n, чем функция яLog 2 n. И для некоторого значения n = n 0 будет достигнуто такой момент, когда влияние разницы констант перестанет иметь значение и в дальнейшем функция c 2 nLog 2 n будет меньше c 1 n 2 для любых n > n 0 .

Для демонстрации этого рассмотрим два компьютера - А и Б. Компьютер А более быстрый и на нем работает алгоритм сортировки, а компьютер Б более медленный и на нем работает алгоритм сортировки методом слияния. Оба компьютера должны выполнить сортировку множества, состоит из миллиона чисел. Предположим, что компьютер А выполняет миллиард операций в секунду, а компьютер Б - лишь десять миллионов, есть А работает в 100 раз быстрее Б. Чтобы разница стала более ощутимой, допустим что код метода включения написан лучшим программистом в мире с использованием команд процессору, и для сортировки n чисел с этим алгоритмом нужно выполнить 2n 2 операций (то есть C 1 = 2). Сортировка методом слияния на компьютере Б написано программистом начинающим с использованием языка высокого уровня и полученный код требует 50nlog 2 n операций (то есть c 2 = 50). Таким образом, для сортировки миллиона чисел компьютеру А потребуется

а компьютеру Б -

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

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

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

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

При необходимости в библиографическом списке могут быть, например, такие разделы, как:

1. Документы государственных органов и общественных организаций;

2. Документы архивов;

3. Справочные и статистические издания;

4. Учебные и учебно-методические издания;

5. Научные монографии и статьи;

7. Периодическая печать;

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

Число источников в библиографическом списке выпускной квалификационной работы не может быть меньше 25-30 наименований.

Оформляется в соответствии с ГОСТ 2003 или ГОСТ Р 7.0.5-2008 «Библиографическая ссылка».

Примеры библиографического описания цитируемых источников

1. Турута Е.Ф. Активные SMD–компоненты: маркировка, характеристики, замена. – СПб.: Наука и техника, 2006. – 544с.

2. Ульрих В.А. Микроконтроллеры PIC16X7XX. – СПб.: Наука и техника, 2002. – 320 с.

Книга имеет редактора

1. Ремизевич Т.В. Микроконтроллеры для встраиваемых приложений: от общих переходов – к семействам HC05 и HC08 фирмы Motorola. /под ред. Кирюхина И.С. – М.: ДОДЭКА, 2000. – 272 с.

Определенный вид работы (учебник, справочник, энциклопедия и.т.п.)

1. Финкельштейн М.И. Основы радиолокации: Учеб. для вузов. – М.: Радио и связь, 1983. – 536 с.

2. Гук М. Аппаратные средства IBM PC: Энциклопедия. – СПб.: Изд-во «Питер», 1999. – 816 с.

1. Игловский И.Г. Слаботочные электрические реле: Справочник / И.Г. Игловский, Г.В. Владимиров. – М.: КУбК-а, 1996. – 560 с.

2. Романычева Э.Т. Инженерная и компьютерная графика / Э.Т. Романычева, Т.Ю. Соколова, Г.Ф. Шандурина. – М.: ДМК Пресс, 2001. – 592 с.

Если книга написана четырьмя авторами и издание имеет редактора, то все они перечисляются за косой чертой (/). Если книга имеет более четырех авторов, то после заглавия за косой чертой (/) перечисляются первые три и добавляются слова «и др».

3. Радиотехнические системы: Учеб. для вузов по спец. «Радиотехника» / Ю.П. Гришин, В.П. Ипатов, Ю.М. Казаринов и др.; Под ред. Ю.М. Казаринова. – М.: Высш. шк., 1990. – 496 с.

Ели редактора у издания нет, то блок «; Под ред. Ю.М. Казаринова.», отсутствует.

Книга переведена с другого языка и не имеет автора

1. Ресурсы Microsoft Windows Server 4.0. Книга 1: пер. с англ. – СПб.: BHV – Санкт-Петербург, 1997. – 408 с.

Статьи из журнала

1. Однобоков В.В. Обоснование магистрального метода оптимального распределения ресурсов // Научно-технические ведомости. - СПб.: Изд-во СПБГПУ, 2003. – вып. 4. – С.55-62.

Статьи из сборника

1. Глазырин Б. Э. Автоматизация выполнения отдельных операций в Word 2000 // Office 2000: 5 кн. в 1 – М., 2002. – Т. 3, Гл. 14. – С. 281–298.

Описание статьи дается на заглавие, если книга написана четырьмя и более авторами. Если статья написана четырьмя авторами, то все они перечисляются за косой чертой (/).

1. Боголюбов А. Н. О вещественных резонансах в волноводе с неоднородным заполнением / А. Н. Боголюбов, А. Л. Делицын, M. Д. Малых // Вестн. Моск. ун-та. Сер. 3, Физика. Астрономия. – 2001. – № 5. – С. 23–25.

Стандарты

1. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения: ГОСТ 19.701–90 (ИСО 5807–85). – Введ 1992–01–01. – М.: Госстандарт СССР: Изд-во стандартов, 1991. – 26 с.

2. Аппаратура радиоэлектронная бытовая. Входные и выходные параметры и типы соединений. Технические требования: ГОСТ Р 51771–2001. – Введ 2002–01–01. – М.: Госстандарт России: Изд-во стандартов, 2001. – 27 с.

Патентные документы

1. Приемопередающее устройство: пат. 2187888 Рос. Федерация / Чугаева В.И.; заявитель и патентодатель Воронеж. науч.-исслед. ин-т связи. – № 2000131736/09; заявл. 18.12.00; опубл. 20.08.02, Бюл. № 23 (II ч.). – 3 с.

Электронные ресурсы удаленного доступа

1. Ю. А. Кочетов. Теория принятия решений / Новосибирский гос–ный ун–т. – Режим доступа: http://math.nsc.ru/LBRT/k5/or.html

2. М. Перов. Организация работы с древовидными списками // Мир ПК – Электрон. журнал. – Изд-во "Открытые системы", 2008. –№ 1. – Режим доступа к журн.: http://www.osp.ru

3. Исследовано в России: многопредмет. науч. журн. / Моск. физ.-техн. ин-т. – Электрон. журн. – Долгопрудный: МФТИ, 1998. – Режим доступа к журн.: http://zhurnal.mipt.rssi.ru. – № гос. регистрации 0329900013.

Электронные ресурсы локального доступа

1. Internet шаг за шагом. – Электрон. дан. и прогр. – СПб. : ПитерКом, 1997. – 1 электрон. опт. диск (CD-ROM) + прил. (127 с.)

2. Большой толковый словарь английского и русского языков: 2 в 1. – Электрон. дан. и прогр. – Maccelesfield (UK): Europa House, 1999. - 1 электрон. опт. диск (CD-ROM).

3. Visio Professional: библиотека инженера–конструктора 5.0. – Электрон. дан. и прогр. – 1997. – 1 электрон. опт. диск (CD-ROM).

В список включаются 2 статьи на русском (обязательные) + 2 переводные на англ. (необязательные), написанные с участием соискателя.

Приложения

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

В качестве приложений возможно включать следующие материалы:

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

– заявка на патент или полезную модель;

– отчет о НИР, представленный на конкурс студенческих работ;

– макеты устройств, пакеты прикладных программ, информация о докладах на конференциях по теме ВКР и др.

– протоколы проведенных исследований и т.д..

3.3 Подготовка и оформление окончательного варианта ВКР

Требования к оформлению

Текст ВКР должен быть выполнен печатным способом с использованием компьютера и принтера на одной стороне белой бумаги формата А4 по ГОСТ 9327-60.

Основной текст работы печатается через 1,5 интервал (27-30 строк на странице) и через 1 интервал (ссылки и сноски) шрифтом Times New Roman, размером 14 (основной текст), 12 – текст в ссылках, сносках и таблицах. Размер левого поля 30 мм, правого – 10 мм, верхнего и нижнего – по 20 мм. Текст работы выравнивается по ширине.

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

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

Фамилии, названия учреждений и другие имена собственные в тексте ВКР приводят на языке оригинала. Допускается транслитерировать имена собственные и приводить названия учреждений в переводе на русский язык с добавлением (при первом упоминании) оригинального названия. Имена следует писать в следующем порядке: фамилия, имя, отчество или – фамилия, инициалы через пробелы, при этом не допускается перенос инициалов отдельно от фамилии на следующую строку.

Сокращение русских слов и словосочетаний в тексте ВКР выполняется по ГОСТ 7.12-93, сокращение слов на иностранных европейских языках – по ГОСТ 7.11-2004. Не допускаются сокращения следующих слов и словосочетаний: «так как», «так называемый», «таким образом», «так что», «например». Если в ВКР принята особая система сокращения слов и наименований, то перечень принятых сокращений должен быть приведен в структурном элементе ВКР «Определения, обозначения и сокращения». В тексте ВКР, кроме общепринятых буквенных аббревиатур, допускается использовать введенные их авторами буквенные аббревиатуры, сокращённо обозначающие какие-либо понятия из соответствующих областей знания. При этом первое упоминание таких аббревиатур указывается в круглых скобках после полного наименования, в дальнейшем они употребляются в тексте без расшифровки.

Нумерация разделов, подразделов, пунктов, подпунктов

Наименования структурных элементов «СОДЕРЖАНИЕ», «ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ», «ВВЕДЕНИЕ», «ЗАКЛЮЧЕНИЕ», «СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ» являются заголовками структурных элементов ВКР.

Заголовки структурных элементов ВКР пишутся в середине строки прописными буквами без точки, не подчёркиваются, например:

ВВЕДЕНИЕ

Каждый структурный элемент ВКР следует печатать с нового листа (страницы), в том числе разделы основной части.

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

3 Исследование эффективности полученных решений

Подразделы нумеруются в пределах раздела. Номер подраздела включает номер раздела и подраздела, разделённые точкой. Например, 1.1, 1.2, 1.3 и т.д.

Пункты должны иметь порядковую нумерацию в пределах каждого подраздела. Номер пункта включает номер раздела и порядковый номер подраздела и пункта, разделённые точкой. Например, 1.1.1, 1.1.2 и т.д.

Номер подпункта включает номер раздела, подраздела, пункта и порядковый номер подпункта, разделённые точкой. Например, 1.1.1.1, 1.1.1.2 и т. д. Если раздел состоит из одного подраздела, то подраздел не нумеруется. Если подраздел состоит из одного пункта, то пункт не нумеруется. Если пункт состоит из одного подпункта, то подпункт не нумеруется. После номера раздела, подраздела, пункта и подпункта в тексте точку не ставят.

Пример непосредственно СОДЕРЖАНИЯ

ВВЕДЕНИЕ5

1 Обзор задач и работ по теме исследования 7

2 Проектирование информационных моделей и разработка алгоритмов10

2.1 Выбор методов и средств проектирования10

2.2 Логическое проектирование системы11

2.3 Физическое проектирование системы13

2.4 Проектирование макета пользовательского интерфейса15

2.5 Алгоритмы работы18

3 Технология программной реализации разработанных моделей и алгоритмов25

4.1 Выбор средств программной реализации25

4.2 Программная реализация пользовательского интерфейса системы29

4.3 Обеспечение эксплуатационной и информационной безопасности разработанной системы33

4.4 Обоснование и экономический расчет затрат на разработку системы39

4 Исследование эффективности полученных решений43

4.1 Исследование эффективности проектных решений43

4.2 Исследование эффективности технологических решений48

4.3 Исследование эффективности разработанных алгоритмов51

ЗАКЛЮЧЕНИЕ55

СПИСОК ЛИТЕРАТУРЫ57

ПРИЛОЖЕНИЯ59

П.1 Графический материал к пояснительной записке59

П.2 Листинг подпрограммы фильтрации и группировки данных 61

П.3 Акт внедрения разработки 65

Разделы, подразделы должны иметь заголовки. Заголовки должны четко и кратко отражать содержание разделов, подразделов.

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

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

Например,

Нумерация страниц

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

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

Иллюстрации и таблицы, размещенные в тексте ВКР на отдельных листах, включают в общую нумерацию страниц. Иллюстрации и таблицы на листе формата А3 (297×420) учитывают как одну страницу.

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

Формулы

Формулы набираются с использованием редактора формул MicrosoftEquation (входит в состав MS Office). При этом под «формулой» понимается любая последовательность не менее чем двух символов, не являющаяся словом (названием, аббревиатурой) в русском или каком-либо другом языке.

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

Текст формулы выравнивается по левой стороне на расстоянии 1.25 сантиметра от левого края текста (с красной строки) независимо от того, нумеруется данная формула или нет:

Если формула не умещается на строке, то она переносится на следующую строку после знака «=» или после математических знаков «+», «–», и др. При этом выравнивание второй строки формулы остается прежним – 1,25 сантиметра от левого края текста статьи, как это показано в примере с формулой (2):

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

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

Абсолютное снижение трудовых затрат (DТ):

DТ = Т0 - Т1,

где Т0 – трудовые затраты на обработку информации по базовому варианту;

Т1 – трудовые затраты на обработку информации по предлагаемому варианту.

Для набора переменных (букв) следует использовать шрифт Times, курсив, не жирный (устанавливается в настройках MicrosoftEquation): например, t, V, s, U. Для набора цифр следует использовать шрифт Times, не курсив (!), не жирный (устанавливается в настройках MicrosoftEquation): например, 1, 2, 15. Размер шрифта для переменных и цифр – 14 пунктов. Размеры остальных элементов формул (устанавливаются в настройках MicrosoftEquation):

Крупный индекс – 8 пунктов;

Мелкий индекс – 6 пунктов;

Крупный символ (знаки суммы, интеграла) – 18 пунктов;

Мелкий символ – 12 пунктов.

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

Для стандартных функций (тригонометрических, логарифмических и т.п.), а также для специальных символов (sup, inf и т.п.) следует использовать шрифт Times, не жирный, не курсив (что соответствует стандартным настройкам MicrosoftEquation), например,

Иллюстрации

Иллюстрации (чертежи, графики, диаграммы, схемы), помещаемые в ВКР, должны соответствовать требованиям государственных стандартов Единой системы конструкторской документации. 9.9.2 Все иллюстрации в тексте ВКР (графики, чертежи, схемы, диаграммы и др.) размещают непосредственно после первой ссылки на них (или на следующей странице) и обозначают словом «Рисунок».

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

Иллюстрации за исключением иллюстраций приложений, следует нумеровать арабскими цифрами сквозной нумерацией. Допускается нумеровать иллюстрации в пределах раздела. В этом случае номер иллюстрации состоит из номера раздела и порядкового номера иллюстрации, разделенных точкой. Например – Рисунок 1.1. При ссылках на иллюстрации следует писать "... в соответствии с рисунком 2" при сквозной нумерации и "... в соответствии с рисунком 1.2" при нумерации в пределах раздела.

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

Рисунок 1 - Подпись к рисунку выравнивается по центру, печатается нежирным шрифтом размером 12 пунктов и при необходимости может быть
продолжена на следующей строке

После подрисуночной подписи оставляется одна пустая строка и продолжается печать текста статьи.

Таблицы

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

Нумерационный заголовок нужен для того, чтобы упростить связь таблицы с текстом; при ссылке в тесте достаточно указать: табл. 1. Таблицы нумеруются последовательно в порядке расположения в тексте пояснительной записки, арабскими цифрами. Слово «Таблица» (с заглавной буквы) и ее номер печатаются курсивом, и выравнивается по правому краю. Между словом «Таблица» и предшествующим абзацем оставляется одна пустая строка. После номера таблицы точка не ставится.

Цели и задачи лекции:ознакомление с методами анализа сложности и эффективности алгоритмов и структур данных

Основные вопросы: экспериментальный и аналитический анализ эффективности алгоритмов.

Классическое утверждение Н.Вирта «Хорошая программа – это единство продуманного алгоритма и эффективных структур данных».

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

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

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

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

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

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

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

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

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

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

Таким образом, мы приходим к необходимости использования для анализа алгоритмов методов общего анализа, который позволяет:

1) учитывает различные типы входных данных;

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

3) может проводиться по описанию алгоритма без его непосредственной реализации или экспериментов.

Суть общего анализа заключается в том, что некоторому алгоритму ставится в соответствие функция f=f(n1, .., nm). В простейшем варианте это функция одной переменной n1 – количества исходных данных. Однако могут быть и другие переменные – например точность расчета или его достоверность. Так для определения того является ли некоторое число простым в случае больших чисел (длина двоичного представления более чем 200 бит) используют вероятностный метод, достоверность которого можно варьировать. Наиболее известные функции это линейные, степенные, логарифмические. Поэтому следует потратить время и вспомнить основы работы с ними.

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

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

Иногда утверждения записываются в обобщенной форме: «Множество s содержит элемент х, обладающий свойством v. Для доказательства данного утверждения достаточно привести пример х "принадлежит" s, который обладает данным свойством. В подобной обобщенной форме записываются, как правило, и маловероятные утверждения, например: «Каждый элемент х множества s обладает свойством Р». Чтобы доказать ошибочность данного утверждения, достаточно просто привести пример: х "принадлежит" s, который не обладает свойством Р. В данном случае элемент х будет выступать в качестве контр-примера.

Пример: Утверждается, что любое число вида 2^n - 1 является простым, если n - целое число, большее 1. Утверждение ошибочно.

Доказательство: чтобы доказать неправоту, обходимо найти контр-пример.

Такой контр-пример: 2^4 - 1 = 15, 15= 3 * 5.

Существует и другой способ, основанный на доказательстве от противного (использовании отрицания). Основными методами в данном случае являются контрапозиция и контрадикция. Использование методов противопоставления подобно зеркальному отражению: чтобы доказать, что «если x - истинно, то и y - истинно», будем утверждать обратное «если y - ложно, то и x - ложно». С точки зрения логики, данные утверждения идентичны, однако второе выражение, которое является котропозицией первого, более удобно.

Пример: Если a*b - нечетное число, то а - нечетное или b – нечетное.

Доказательство: для доказательства данного утверждения рассмотрим контрапозицию: «Если а - четное число и b - нечетное, то a*b – четное. Пусть, а = 2*x, для некоторого целого числа x. Тогда a*b = 2*i*b, а следовательно произведение a*b - четное.

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

A or b = требуется выполнение a или b, или и a и b одновременно.
. a and b = требуется одновременное выполнение a и b.
. a xor b = требуется выполнение a, но не b или же b, но не a.

При использовании метода контрадикции для доказательства того, что утверждение q - верно, вначале предполагается, что q - ложно, а затем показывается, что такое предположение приводит к противоречию (например, 2 * 2 <> 4). Придя к подобному противоречию, можно утверждать, что ситуации, при которой q - ложно, не существует, и, следовательно, q – истинно.

В большинстве случаев в утверждениях о времени выполнения программы или используемом пространстве применяется целочисленный параметр n (обозначающий «размеры» задачи). Тогда когда мы формулируем утверждение x(n), то для множества значений n подобные утверждения равносильны. Так как данное утверждение относится к “бесконечному” множеству чисел, невозможно провести исчерпывающее прямое доказательство. В подобных ситуациях используют методы индукции. Метод индукции основан на том; что для любого n > 1. Существует конечная последовательность действий, которая начинается чего-то заведомо истинного и, в конечном итоге, приводит к доказательству того, что q(n) истинно. Таким образом, доказательство с помощью индукции начинается с утверждения, что q(n) истинно при n=1,2,3 и т.д. до некоторой константы k. Далее доказывается, что следующий «шаг» индукций q(n+1), q(n+2) также является истинным для n > k.

При анализе алгоритмов, подсчете количества операций и времени их выполнения, не следует учитывать “мелкие детали”, следует пренебречь постоянными множителями и константами. На практике используют понятие функции большого О . предположим, что существуют две функции f(n) и g(n), считается, что f(n) <= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

Например, алгоритм подсчета в массиве количества элементов равных нулю описывается О(n), где n – количество элементов.

1) 20n3+7,2n2-21,78n + 5 описывается как О(n3)

2)xn-2 + a(0) описывается как О(xn).

2) 3*log(n) + log(log(n)) описывается как О(log(n)).

3) 2100 описывается как О(1)

4) 5/n описывается как О(1/n).

Обратите внимание на то, что функция o(n) ограничивает сверху целевую функцию затрат времени, но необходимо стремиться всегда выбирать такую функцию О(n), чтобы была максимальная точность.

Наиболее известные функции О в порядке их возрастания:

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

В зависимости от вида функции f(n) выделяют следующие классы сложности алгоритмов.

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

1. Класс быстрых алгоритмов с постоянным временем выполнения, их функция трудоемкости O(1). Промежуточное состояние занимают алгоритмы со сложностью O(log N), которые также относят к данному классу.

2.Класс рациональных или полиномиальных алгоритмов, функция трудоемкости которых определяется полиномиально от входных параметров. Например, O(N), O(N 2 , O(N 3).

3.Класс субэкспоненциальных алгоритмов со степенью трудоемкости O(N log N).

4.Класс экспоненциальных алгоритмов со степенью трудоемкости O(2 N) .

5.Класс надэкспоненциальных алгоритмов. Существуют алгоритмы с факториальной трудоемкостью, но они в основном не имеют практического применения.

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

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

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

• Трудоемкость конструкции "Следование" есть сума трудоемкостей блоков, следующих друг за другом: f=f 1 +f 2 +...+f n .
• Трудоемкость конструкции "Ветвление" определяется через вероятность перехода к каждой из инструкций, определяемой условием. При этом проверка условия также имеет определенную трудоемкость. Для вычисления трудоемкости худшего случая может быть выбран тот блок ветвления, который имеет большую трудоемкость, для лучшего случая – блок с меньшей трудоемкостью. f if =f 1 +f then ·p then +f else ·(1-p then)
• Трудоемкость конструкции "Цикл" определяется вычислением условия прекращения цикла (обычно имеет порядок 0(1)) и произведения количества выполненных итераций цикла на наибольшее возможное число операций тела цикла. В случае использования вложенных циклов их трудоемкости перемножаются.

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

1. Декомпозиция алгоритма предполагает выделение в алгоритме базовых конструкций и оценку и трудоемкости. При этом рассматривается следование основных алгоритмических конструкций.
2. Построчный анализ трудоемкости по базовым операциям языка подразумевает либо совокупный анализ (учет всех операций), либо пооперационный анализ (учет трудоемкости каждой операции).
3. Обратная композиция функции трудоемкости на основе методики анализа базовых алгоритмических конструкций для лучшего, среднего и худшего случаев.

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