Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2013-2014‎ > ‎

6. alkalom

Néhány szakkörön át olyan feladatokat nézünk meg, amelyekről közismert, hogy nagy bemenet esetén nem oldhatók meg. (Picit pontosabban a P != NP sejtés teljesülése esetén következik, hogy nem létezik polinomiális megoldó algoritmus. Ennek részleteiről egy későbbi alkalommal lesz szó.)

Az ilyen feladatokkal is érdemes foglalkozni, például a következők miatt:
  • Annak ellenére, hogy nem létezik polinomiális megoldó algoritmus, nem túl nagy bemenetre még lehet remény hatékony programot írni.
  • Előfordulhat, hogy az elméleti korlát igaz, de a gyakorlatban előforduló esetekben vannak olyan plusz korlátozások, amelyek mellett már hatékonyan kezelhető a feladat.
  • Néha annak is örülünk, ha az optimálisnál nem sokkal rosszabb közelítő megoldást találunk.
  • A véletlen felhasználásával bizonyos esetekben nagyon-nagy valószínűséggel megtaláljuk a jó megoldást.

Feladat