Лабораторная работа. Алгоритмы обработки данных

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

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

Теоретические сведения.

Ознакомьтесь с материалом лекции.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

1. Выполните анализ временной сложности алгоритмов простых сортировок. Проведите сравнительный анализ полученных результатов. Определите классы этих алгоритмов в зависимости от функции трудоемкости.
2. Выполните анализ временной трудоемкости алгоритма решения задачи о Ханойских башнях. Определите класс этого алгоритма в зависимости от функции трудоемкости.
3. Выполните анализ трудоемкости конструкций вложенных циклов для n=100, n=10⁶, n=10⁹. Составьте функцию временной трудоемкости алгоритма и определите его класс сложности. Считать, что все указанные операции корректны. Возможное переполнение разрядов не учитывать.

4. k=0;

5. for (a=0; a<n; a++)

6. for (b=0; b<n; b++)

7. for (c=0; c<n; c++)

k++;

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

Указания к выполнению работы.

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

Следует реализовать каждое задание в соответствии с приведенными этапами:

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

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

• Титульный лист.
• Словесная постановка задачи. В этом подразделе проводится полное описание задачи. Описывается суть задачи, анализ входящих в нее физических величин, область их допустимых значений, единицы их измерения, возможные ограничения, анализ условий при которых задача имеет решение (не имеет решения), анализ ожидаемых результатов.
• Математическая модель. В этом подразделе вводятся математические описания физических величин и математическое описание их взаимодействий. Цель подраздела – представить решаемую задачу в математической формулировке.
• Алгоритм решения задачи. В подразделе описывается разработка структуры алгоритма, обосновывается абстракция данных, задача разбивается на подзадачи. Схема алгоритма выполняется по ЕСПД (ГОСТ 19.003-80 и ГОСТ 19.002-80).
• Листинг программы. Подраздел должен содержать текст программы на языке программирования С++, реализованный в среде MS Visual Studio 2010.
• Контрольный тест. Подраздел содержит наборы исходных данных и полученные в ходе выполнения программы результаты.
• Выводы по лабораторной работе.
• Ответы на контрольные вопросы.

Контрольные вопросы

1. С какой целью проводится оценка ресурсной эффективности алгоритмов?
2. Почему в теории анализа алгоритмов нет привязки к конкретной реализации?
3. Могут ли оценки временной сложности для худшего и лучшего случаев совпадать? Подтвердите вывод примерами.
4. Охарактеризуйте область применения алгоритмов классов сложности и .
5. В чем особенность оценки трудоемкости рекурсивных алгоритмов?
6. Оцените временную трудоемкость рекурсивного и итерационного способов вычисления факториала целого неотрицательного числа. Определите класс сложности алгоритмов в каждом случае. Объясните результат.

Лекция: Алгоритмы обработки данных

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

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

Алгоритм не должен быть привязан к конкретной реализации. В силу разнообразия используемых средств программирования, их требований к аппаратным ресурсам и платформенной зависимости сходные по структуре, но различные в реализации, алгоритмы могут выдавать отличающиеся по эффективности результаты. При этом некоторые среды программирования содержат встроенные библиотечные функции, реализующие базовые алгоритмы обработки данных (например, в MS Visual Studio 2010 в библиотеки С++ входит функция быстрой сортировки массивов данных). Чтобы решения были переносимыми и оставались актуальными, не рекомендуется их ориентировать на процедурную реализацию среды. Поэтому главным в рассматриваемом подходе является выбор метода решения с учетом специфики задачи. Адаптация к среде осуществляется позднее.

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

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