6.4 Теорема об ускорении

Теорема 6.7 Теорема Блюма об ускорении.

Существуют функции, которые можно вычислять ве быстрее и быстрее почти всюду, а именно: пусть М₁ – некоторая МНР, вычисляющая функцию f(n), пусть t₁(n) – время ее работы.

Тогда существует машина М₂, которая также вычисляет функцию f(n), причем для почти всех n время ее работы t₂(n)≤𝜑(t₁(n)), где 𝜑 – произвольная функция ускорения со свойствами

.

^n→∞

Комментарий. Если φ(n)=

100 раз быстрее машины М_1.

Если φ(n)=, то ускорение уже происходит не в разы, а на порядок.

Без доказательства.

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

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

Лабораторные работы

Сортировка массивов

1. Метод «Пузырька»

2. Метод прямого выбора(SelectSort)

3. Метод прямого слияния (MergeSort)

Преобразование Фурье

4. Дискретное преобразование Фурье.

5. «Полу-быстрое» преобразование Фурье.

6. Быстрое преобразование Фурье.

Свертки

7. Свертка с помощью обычного алгоритма.

8. Свертка с помощью быстрого алгоритма (через ДПФ).

Умножение чисел

9. Умножение чисел столбиком.

10. Быстрое умножение чисел.

Задачи на графах

11. Поиск минимального остова в связанном неориентированном графе с помощью алгоритма Краскалла.

12. Нахождение кратчайшего расстояния с помощью алгоритма Форда-Беллмана.

13. Нахождение кратчайшего расстояния с помощью алгоритма Дейкстры.

Задачи динамического программирования

14. Задача грабителя(задача «о рюкзаке»).

15. Задача о перемножении матриц.

Расчетно-графическое задание

Вариант расчетно-графического задания выбирается по номеру в журнале. Символ b в матрице расстояний означает ∞.

Вариант1. Написать 2 программы, вычисляющие произведение двух матриц A[i,j]=(-1)^(i+j), B[i,j]=i+j,i,j=1…100. Использовать алгоритмы быстрого и обычного умножения. Сравнить трудоемкость двух алгоритмов.

Вариант2. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одновременного ветвления). Сравнить трудоемкость двух алгоритмов.

Вариант3. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одностороннего ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант4. Написать 2 программы, вычисляющие произведение двух матриц A[i,j]=(-1)^(i+j), B[i,j]=i-j,i,j=1…100. Использовать алгоритмы быстрого и обычного умножения. Сравнить трудоемкость двух алгоритмов.

Вариант5. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одновременного ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант6. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одностороннего ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант7. Написать 2 программы, вычисляющие произведение двух матриц A[i,j]=(-1)^j, B[i,j]=i+j,i,j=1…100. Использовать алгоритмы быстрого и обычного умножения. Сравнить трудоемкость двух алгоритмов.

Вариант8. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одновременного ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант9. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одностороннего ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант10. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одностороннего ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант11. Написать 2 программы, вычисляющие произведение двух матриц A[i,j]=(-1)^(i+j), B[i,j]=i+j,i,j=1…100. Использовать алгоритмы быстрого и обычного умножения. Сравнить трудоемкость двух алгоритмов.

Вариант12. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одновременного ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант13. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одностороннего ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант14. Написать 2 программы, вычисляющие произведение двух матриц A[i,j]=(-1)^(i+j), B[i,j]=i-j,i,j=1…100. Использовать алгоритмы быстрого и обычного умножения. Сравнить трудоемкость двух алгоритмов.

Вариант15. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одновременного ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант16. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одностороннего ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант17. Написать 2 программы, вычисляющие произведение двух матриц A[i,j]=(-1)^j, B[i,j]=i+j,i,j=1…100. Использовать алгоритмы быстрого и обычного умножения. Сравнить трудоемкость двух алгоритмов.

Вариант18. Написать 2 программы, вычисляющие произведение двух матриц A[i,j]=(-1)^(i+j), B[i,j]=i+j,i,j=1…100. Использовать алгоритмы быстрого и обычного умножения. Сравнить трудоемкость двух алгоритмов.

Вариант19. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одновременного ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант20. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одностороннего ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант21. Написать 2 программы, вычисляющие произведение двух матриц A[i,j]=(-1)^(i+j), B[i,j]=i-j,i,j=1…100. Использовать алгоритмы быстрого и обычного умножения. Сравнить трудоемкость двух алгоритмов.

Вариант22. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одновременного ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант23. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одностороннего ветвления). Сравнить трудоемкость двух алгоритмов.

С=

Вариант24. Написать 2 программы, вычисляющие произведение двух матриц A[i,j]=(-1)^j, B[i,j]=i+j,i,j=1…100. Использовать алгоритмы быстрого и обычного умножения. Сравнить трудоемкость двух алгоритмов.

Вариант25. Написать 2 программы, решающие задачу коммивояжера. Граф G задан матрицей c[i,j]. Использовать алгоритмы прямого перебора и метод ветвей и границ (схема одновременного ветвления). Сравнить трудоемкость двух алгоритмов.

С=