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

Ташкентский университет информационных технологий имени Мухаммада ал-Хоразмий Карши филлиал
5- Самостоятельная работа
Предмет: Алгоритмы проектирования
Тема: Алгоритмы на языке «разделяй и властвуй». Понятие о классах R и NP, NP-полных задачах
Группа : TT-13-20p
Выполнил: Чориев Сардор
Проверил: Улашева Ш
Карши 2023


Алгоритмы на языке "разделяй и властвуй".
ПЛАН:
1. Метод «разделяй и властвуй».
2. Работа с кэш-памятью.
3. Проблемы с приложением.
4. Примеры.
5. Вывод.


Метод разделяй и властвуй
В программировании разделяй и властвуй — это алгоритмическая парадигма, основная идея которой состоит в том, чтобы разделить алгоритмические задачи на более мелкие части, аналогичные основной задаче, и решить их рекурсивно. В этой парадигме, поскольку проблема разделена на части, частичные проблемы должны быть меньше, чем основная проблема, и это основное состояние, при котором разделение прекращается.
Все типы алгоритмов «разделяй и властвуй» состоят из 3 шагов:
Стадия разделения. В этом случае основная проблема разбивается на более мелкие задачи, аналогичные этой задаче.

Стадия доминирования. Та часть, которая соответствует нашей основной ситуации, будет решена как есть.

Стадия консолидации.На этом этапе решенные подзадачи собираются вместе, и это становится решением основной проблемы.
Таким образом, парадигму «разделяй и властвуй» можно запомнить тремя предложениями:
отдельный
правило
комбинировать

Парадигма «разделяй и властвуй» лежит в основе популярных алгоритмов программирования:

• 
  Быстрая сортировка
  

• 
  Сортировка слиянием
  

• 
  Ближайшие две точки
  

• 
  Умножение Штрассена (умножение Штрассена)
  

• 
  Алгоритм Карацубы
  

• 
  Алгоритм Кули-Тьюки (Алгоритм Кули-Тьюки)
  

• 
  позволяет легко решать сложные задачи