Алгоритмы на языке «разделяй и властвуй». Понятие о классах r и np, np-полных задачах

Преимущества парадигмы «разделяй и властвуй»

• 
  алгоритмы, основанные на этой парадигме, работают быстрее, чем простые решения. Например: скорость пузырьковой сортировки, простой сортировки, составляет O (n²), а MergeSort — O (n * logn).
  

• 
  такие алгоритмы можно использовать без каких-либо изменений в параллельных вычислительных системах
  

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

• 
  для действительных чисел такие алгоритмы работают точнее, потому что операции над действительными числами в частичных решениях выполняются точнее (например, в алгоритмах умножения)
  

Недостатки парадигмы «разделяй и властвуй»

• 
  алгоритмы, основанные на такой парадигме, используют рекурсию, которая замедляет их на определенную величину. Более того, небольшая ошибка может отбросить решение на бесконечную итерацию.
  

• 
  ошибка в выборе основного условия приведет к ошибке и перерасходу памяти во всех подзадачах
  

2. Работа с кэш-памятью
Кэш — это высокоскоростная память, которую процессор персонального компьютера использует для хранения часто запрашиваемых данных в течение определенного периода времени. Это качественно повышает эффективность, потому что сообщает процессору, как искать нужные данные и как получить данные максимально быстро. Кэш-память напрямую влияет на скорость выполнения различных операций, поскольку заранее хранит информацию, которая необходима. Принцип его работы можно описать на простом примере. Чтобы оптимизировать свою работу, каждый старается расположить вещи на рабочем столе в определенном логическом порядке.
Возможно ручки, телефон, необходимые справки, текущие документы и т.д. могут быть расположены рядом, потому что нет возможности каждый раз, когда кто-то прятал нужные документы под годовой отчет пять лет назад, потому что это требует времени и сил. Именно по такому принципу работает кэш-память. Что это означает на уровне компьютера? На самом деле это аналогичный процесс. Вся информация доступна в определенной иерархии на персональном компьютере. Если какая-то информация требуется чаще, чем другая, они располагаются ближе друг к другу.
Кэш – это быстродействующая память, позволяющая быстро доставлять необходимую информацию к процессору, в результате чего производительность персонального компьютера повышается в качестве. Кэш также используется браузерами и требует простой процедуры очистки. Кэш [или кеш (в англ. cache, фр. помещено в реф.рф cacher — скрывать; произносится — кеш) — с быстрым доступом, содержащий информацию, которая может потребоваться быстрой памяти, например оперативную. Доступ к данным в кеше выполняется быстрее, чем извлечение или пересчет данных из внешней памяти, что сокращает среднее время доступа.
Процессор получает данные из оперативной памяти для работы. При этом сигналы обрабатываются в микросхеме на очень высокой частоте (несколько сотен МГц), а все обращения к ОЗУ происходят на частоте в несколько раз меньшей. Чем выше внутренний множитель частоты, тем эффективнее процессор может работать с данными, хранящимися внутри, чем с данными, хранящимися снаружи. Обычно процессор почти ничего не хранит внутри себя. В нем очень мало ячеек обработки данных (эти «рабочие» ячейки называются регистрами). Поэтому давно (с 4-го поколения) была предложена технология кэширования для ускорения работы процессора.
Кэш — это относительно небольшой набор ячеек памяти, которые действуют как буфер. Когда что-то читается из общей памяти или записывается в нее, копия данных также включается в кеш. Если снова понадобятся сами данные, нет необходимости извлекать их удаленно — гораздо быстрее извлечь их из буфера. Использование кэш-памяти позволило значительно повысить производительность компьютерной системы. Когда технология кэширования впервые использовалась для процессоров 486, кэш располагался как можно ближе к процессору на материнской плате; хоть емкость и не большая, но использовались самые "быстрые" по производительности микросхемы.
Сегодня кеш установлен в виде "пирамиды". Кэш первого уровня, самый быстрый по скорости, но самый маленький по размеру, является частью кристалла процессора. Они сделаны по той же технологии, что и процессорные регистры, ставшие очень дорогими, но очень быстрыми и, главное, надежными. Его размер составляет всего несколько десятков Кбайт, но это очень важно для быстрой обработки. Кэш-память второго уровня может располагаться на том же кристалле процессора (в этом случае она работает на частоте ядра процессора). Обычно размер кэша L2 измеряется сотнями Кбайт (128/256/512 Кбайт и т. д.).
Самый большой, но самый медленный кэш — это кэш 3-го уровня. В процессор он не входит, потому что он установлен на материнской плате и работает на его частоте. Его размер может достигать 1-2 МБ. Размер кэшей L1 и L2 оказывает огромное влияние на стоимость процессора. Процессоры одной модели и данной рабочей частоты могут отличаться размером кэш-памяти.
В программировании cache-oblivious алгоритмы — это алгоритмы, разработанные таким образом, что они используют кэш процессора (англ. cache) вне зависимости от размера кеша (или длины строк кеша). Оптимальный алгоритм, не обращающий внимания на кэш, — это алгоритм, не обращающий внимания на кэш, который оптимально использует кэш в асимптотическом смысле без учета переменных факторов. Такие алгоритмы работают эффективно и без модификации на разных машинах, вне зависимости от размера кеша разных уровней памяти.
Простые алгоритмы без кэширования: умножение матриц, внешняя сортировка, транспонирование матриц и некоторые другие задачи. Как правило, алгоритмы без кэширования используют подход «разделяй и властвуй», когда задача делится на подзадачи и подзадачи. В процессе распределения у нас будут небольшие задачи. Через какое-то время эти подзадачи начнут укладываться в размер кеша, мы не знаем, когда они влезут, но продолжим делить на наименьшие базовые размеры.
Затем мы применяем эффективный алгоритм для подзадачи. После этого объединяем результаты по сути основной задачи. Например, алгоритм умножения матриц, не обращающий внимания на кэш, генерируется путем рекурсивного деления каждой матрицы на четыре подматрицы. Когда матрица полностью закеширована, мы используем оптимизированный алгоритм для небольших задач, а затем добавляем результат работы функций в матрицу.