Контрольная работа по дисциплине

«Алгоритмы и анализ сложности»

V – номер варианта, равен порядковому номеру студента в списке команды

1. 
   Один миллиард пользователей, каждый имеет в интернете V тысяч фотографий по 1 мегабайту каждая. Назовите словами суммарный объем памяти.
   
2. 
   Некоторый алгоритм имеет квадратичную сложность P_float(n) = V*n*n, измеренную в количестве плавающих операций за один эксперимент с объемом входных данных n. Аналитик хочет выполнить один триллион экспериментов с данными объема один миллиард. Скорость суперкомпьютера 1 экза flops. Сколько времени работы суперкомпьютера следует заказать аналитику.
   
3. 
   Определите асимптотические оценки функции сложности алгоритма
   

P_if(n) = V*n*sin²(n)+V

4. 
   Выполните сортировку массива X = {7, 3, 4, V, 3, 5, 2, 1, 2*V, 10, 3, 6} по возрастанию тремя методами:
   

1. 
   Сортировка деревом SortTree
   
2. 
   Пирамидальная сортировка HeapSort, одна итерация
   
3. 
   Красно-черное дерево RBTree
   

5. 
   Найти 41^-1 (mod (50+V)) с помощью обобщенного алгоритма Эвклида
   
6. 
   С помощью алгоритма модулярного возведения в степень вычислить без калькулятора 1234501^1000000 (mod 100), то есть найти две последние цифры.
   
7. 
   Укажите минимальное количество умножений длинных чисел для степени D^(20+V), где D-длинное число. Используйте алгоритм быстрого возведения в степень.
   
8. 
   Найдите минимальный путь из вершины А в вершину D для заданной матрицы расстояний в ориентированном графе. Примените алгоритм Дейкстры. Используйте метки, помеченные и просмотренные узлы. Карту рисовать не надо!
   

   из\в	A	B	C	D	E	F
   A			V		6	8
   B	1		1	5
   C	2				3
   D	4	1	5			V
   E	3	V		9		2
   F	V	7		3	V

9. 
   С помощью алгоритма динамического программирования найдите размен суммы
   S=25 + V%5 руб. монетами по 3, 5, 8 руб. с минимальным количеством монет.
   
10. 
    Случайная величина задана функцией распределения
    

---

Определите плотность распределения f(x) и постройте генератор этой величины методом «обратной» функции.

11. 
    Стороны прямоугольного участка земли измерены в метрах в виде нечетких чисел и равны [100; 2, 3], [200; 4, 1]. Вычислите площадь участка также в виде нечеткого числа.
    

Составители: Трофимов С.П., Трофимова О.Г. 17.05.2023

---

Смотрите также файлы

• Контрольная работа для группы ю229 Криминология Выполнила студентка гр. Ю229 Мамаева Х. А.docx

• Отчет по производственной (преддипломной) практике Место прохождения практики.docx

• Пункт 1.docx

• Министерство агентство образования и науки Российской Федерации Поволжский Государственный Технологический Университет.rtf

• Ответы по педагогике Педагогика как наука. Предмет и сущность педагогики.docx