Задание на лабу_new (1016811)

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

1

T(N)

17

95

298

575

1118

1901

3222

4320

6878

8342

76564

251381

1187797

9379801

1137969646

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

2

T(N)

8

24

69

147

297

567

943

1608

2369

3242

32322

135572

739596

6971981

1026663832

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

3

T(N)

14

42

83

147

215

266

383

489

576

698

2945

6705

16298

76591

1871905

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

4

T(N)

10

60

266

682

1440

2802

4815

8168

12762

18202

184488

687790

3793457

30816246

4989361796

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

5

T(N)

3

4

45

121

308

443

824

1388

1641

2141

13003

33865

92408

432646

17582996

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

6

T(N)

8

34

65

139

201

322

421

557

570

918

3899

7848

20829

89038

2218955

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

7

T(N)

8

14

19

25

26

29

44

39

40

52

92

139

216

413

2003

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

8

T(N)

6

27

78

190

418

724

1001

1575

2027

3170

22538

73486

390423

3176252

403475282

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

9

T(N)

4

22

59

111

206

341

474

585

845

1195

5602

12231

35805

186181

4925642

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

10

T(N)

4

10

14

17

19

26

36

47

69

82

373

695

2021

9533

244977

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

11

T(N)

2

22

116

411

787

1571

2775

4289

6234

10983

100161

422046

2043957

24223968

2966536156

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

12

T(N)

5

31

112

246

490

849

1497

1986

2961

4160

31875

100964

482408

3934120

498311535

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

13

T(N)

2

13

59

144

276

444

732

890

1056

1743

9545

19995

79268

305449

10594192

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

14

T(N)

8

38

142

321

695

1222

2126

3412

4563

6948

68450

257375

1300891

12802897

2034599815

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

15

T(N)

13

38

93

137

227

297

464

507

636

790

3476

7472

18306

84060

1900163

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

16

T(N)

6

68

421

1383

2560

5329

8328

15330

20821

30915

347184

1246441

6306894

71542155

9281098534

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

17

T(N)

12

42

75

123

215

303

350

468

657

778

2685

6336

17519

69563

1852244

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

18

T(N)

7

48

263

806

1715

3232

5704

10017

13474

20577

183233

745423

4341214

42473005

5247951777

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

19

T(N)

8

20

52

90

128

180

238

261

353

400

1627

2760

7271

28469

653715

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

20

T(N)

5

27

74

159

235

301

392

531

701

973

3177

7413

24917

91560

2219577

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

21

T(N)

17

69

196

439

816

1373

2197

3456

4560

5910

46231

168602

716507

6011078

787811239

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

22

T(N)

9

14

35

97

289

460

796

2050

2399

3042

45556

165821

861347

5738976

708231414

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

23

T(N)

5

21

77

249

458

687

1174

1327

2380

2708

15905

34425

119976

518754

17005328

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

24

T(N)

13

45

146

307

553

892

1320

1849

2669

3499

17057

39533

127313

641911

19192959

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

25

T(N)

14

23

58

99

161

231

333

410

495

585

2400

5868

16829

68812

2192353

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

26

T(N)

10

25

66

129

190

300

467

637

864

975

5564

14075

41441

190062

6346751

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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), сf(N), N_op(N), постараться обеспечить единство масштаба при помощи константы c_{N_op}.

N

1

2

3

4

5

6

7

8

9

10

20

30

50

100

500

27

T(N)

5

37

194

534

1418

2511

5377

8116

11974

15180

167008

737604

3283979

33880539

4556808521

№ вари-анта

Задание: по экспериментальным данным T(N) замеров времени выполнения (числа фактически выполненных инструкций) некоторой программы эмпирически определить характер функции роста трудоемкости реализованного алгоритма, вид и значения её асимптотической оценки Θ(N), O(N), o(N), (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₀ для каждой функции, согласно их определениям в теории О-символики;