Qo’yilgan masala. Kesishmaydigan to’plam ostilari va birlashmalarini qidirish algoritmi. Ish tartibi

AMALIY MASHG’ULOT № 6

FAN NOMI		Algoritmlarni loyihalash
HAFTA		3
MAVZU:		Kesishmaydigan to‘plam ostilari va birlashmalarini qidirish algoritmi. NP-to‘liq masalalar. NP-to‘liq masalalarga keltirish usullari.
ISHDAN MAQSAD:		Kesishmaydigan to‘plam ostilari va birlashmalarini qidirish algoritmi. NP-to‘liq masalalar. NP-to‘liq masalalarga keltirish usullari.

Qo’yilgan masala. Kesishmaydigan to’plam ostilari va birlashmalarini qidirish algoritmi.
Ish tartibi:

• 
  Tajriba ishi nazariy ma’lumotlarini o‘rganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  C++ dasturlash muhitida dasturni yaratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.
  

Nazariy qism

Esingizda bo’lsa bu masalani xasislik algoritmlari orqali yechgandik. Xasislik algoritmlarining xususiyatlaridan kelib chiqib, biz o’shanda 3000 natijasini olgandik. Chunki xasislik algoritmi har doim ham optimal yechimni bermaydi, balki, u yechimni tezkorlik bilan topishga yordam beradi. Yechim yetarlicha bo’ladi, lekin optimal bo’lmasligi mumkin. Masala uchun Xasislik algoritmida algoritm murakkabligi bahosi O(n) ga teng.