Самостоятельная работа №5 По предмету: Алгоритмы проектирования Алгоритмы на языке «разделяй и властвуй»

МИНИСТЕРСТВО ПО РАЗВИТИЮ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И КОММУНИКАЦИЙ РЕСПУБЛИКИ УЗБЕКИСТАН
КАРШИНСКИЙ ФИЛИАЛ ТАШКЕНТСКОГО УНИВЕРСИТЕТА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ АЛЬ-ХОРАЗМИЙ
ФАКУЛЬТЕТ ТТ И ПО

САМОСТОЯТЕЛЬНАЯ РАБОТА №5
По предмету: Алгоритмы проектирования

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

Подготовил: Нутфуллаев Шахзод
Студент 3-го курса гр. TT-13-20р


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


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

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

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

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

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

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

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

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

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

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

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