Отчет по лабораторной работе (Методы программирования) (1016814)

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

Текст из файла

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ

Кафедра ИТ-6 «Управление и моделирование систем»

Отчет о выполнении

лабораторной работы №1 по предмету

«Структуры и алгоритмы обработки данных».

Тема: «Математические основы О-символики».

Выполнил:

студент 1 курса,

группы ИТ-6

№ студ. Билета 10080

Васильев Олег Михайлович

(ф.и.о.)

Проверил: Филатов В.В.

Москва 2010

Вариант №77

Задание:

По экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), Q(N), ω(N), предложить и реализовать пример программы, трудоемкость которой соответствует полученным эмпирическим оценкам. Для чего необходимо:

1. По полученному ряду T(N) построить график зависимости T(N) от N;

2. Выдвинуть гипотезу о характере функции роста (классе эффективности, виде полинома функции роста) f(N) и определить вид функций асимптотических оценок Θ(f(N)), O(f(N)), o(f(N)), Ω(f(N)), ω(f(N));

3. На график T(N) наложить графики предложенных Θ(f(N)), O(f(N)), o(f(N)), Ω(f(N)), ω(f(N)), вычислив численно каждую из них в точках N={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 50, 100, 500} и определить соответствующие константы с и n₀ для каждой функции, согласно их определениям в теории О-символики;

4. На основе предложенного полинома f(N) предложить структуру (с смысле парадигмы структурного программирования) фрагмента программы, соответствующего полиному f(N) и написать программу, реализующую данную структуру операторов, внутри которого некоторый счетчик (для определенности назовем его N_op), увеличиваясь при каждой итерации на единицу, моделирует выполнение одной инструкции. Определить и вывести значение счетчика N_op после выполнения всего фрагмента программы (управляющей конструкции) для каждого значения N. Выполнить и занести в отчет о лабораторной работе значение счетчика для каждого N={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 50, 100, 500}, то есть получить ряд N_op(N).

5. Оформить отчет о выполнении лабораторной работы, где указать:

- задание и номер варианта задания, предполагаемый вид полинома функции роста f(N), и соответствующие ей Θ(f(N)), O(f(N)), o(f(N)), Ω(f(N)), ω(f(N));

- единую таблицу с исходными значениями T(N) и расчетными значениями f(N), Θ(f(N)), O(f(N)), o(f(N)), Ω(f(N)), ω(f(N)) (столбцы - значения N, а строки - значения функций);

- графики функций на едином рисунке;

- листинг программы, соответствующей предложенной функции роста;

- на втором рисунке-графике привести зависимости T(N), c·f(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N	1	2	3	4	5	6	7	8	9	10	20	30	50	100	500
T(N)	4	31	65	115	247	274	438	550	670	910	3510	7162	19985	85407	2306436

Полученные результаты работы:

Предполагаемый вид полинома функции роста f(n), и соответствующие ей Θ(f(n)), O(f(n)), o(f(n)), Ω(f(n)), ω(f(n)):

Таблица:

Графики:

Программа (вариант А), соответствующая предложенной функции роста:

var i,j,k,n:integer;

schet:longint;

begin

write('Vvedite n -> ');

readln(n);

schet:=0;

for i:=1 to n do begin

for j:=1 to 25 do

for k:=1 to (n-2) do

schet:=schet+1;

end;

schet:=schet+25;

writeln('ZNACHENIE SCHETCHIKA ---->>> ',schet);

readln;

end

.Графики:

Программа (вариант В), соответствующая предложенной функции роста:

var i,j,n:integer;

schet:longint;

begin

write('Vvedite n -> ');

readln(n);

schet:=0;

for i:=1 to n do begin

for j:=1 to (n-2) do

schet:=schet+25;

end;

schet:=schet+25;

writeln('ZNACHENIE SCHETCHIKA ---->>> ',schet);

readln;

end.

.Графики:

Программа (вариант С), соответствующая предложенной функции роста:

var i,j,k,n:integer;

schet:longint;

begin

write('Vvedite n -> ');

readln(n);

schet:=0;

for i:=1 to 25 do begin

for j:=1 to (n-1) do

for k:=1 to (n-1) do

schet:=schet+1;

end;

writeln('ZNACHENIE SCHETCHIKA ---->>> ',schet);

readln;

end.

.Графики:

9

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

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

Список файлов лабораторной работы