Complexitate computațională

Concepte în Informatică

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Clase de complexitate

Clase de complexitate

  • Timp polinomial (P)
  • Timp polinomial nedeterminist (NP)
  • NP-Complet
  • NP-Dificil

O animație care arată întregul spațiu de complexitate a problemelor

Concepte în Informatică

P (Timp polinomial)

O imagine care arată spațiul problemelor P

Clasă de complexitate --> P (Timp polinomial)
Semnificație Rezolvabil rapid și eficient
Exemplu Sortarea unei liste
Analogie „Clasarea documentelor în ordine alfabetică"
Punct cheie Sunt considerate „ușoare" în termeni computaționali
1 https://www.baeldung.com/cs/p-np-np-complete-np-hard
Concepte în Informatică

NP (Timp polinomial nedeterminist)

O imagine care arată spațiul problemelor P și NP

Clasă de complexitate --> NP (Timp polinomial nedeterminist)
Semnificație Soluția poate fi verificată, dar e greu de găsit
Exemplu Verificarea corectitudinii unui puzzle Sudoku
Analogie „Găsirea unui document cu informații lipsă"
Punct cheie Verificarea soluțiilor e „ușoară", dar găsirea lor e dificilă
1 https://www.baeldung.com/cs/p-np-np-complete-np-hard
Concepte în Informatică

NP-Complet

O imagine care arată spațiul problemelor P, NP și NP-Complet

Clasă de complexitate --> NP-Complet
Semnificație Cele mai dificile din NP. Rezolvă toate problemele NP
Exemplu Problema comis-voiajorului
Analogie „Puzzle complex: ușor de verificat, greu de rezolvat"
Punct cheie Nicio soluție eficientă cunoscută, dar găsirea uneia ar rezolva toate NP
1 https://www.baeldung.com/cs/p-np-np-complete-np-hard
Concepte în Informatică

NP-Dificil

O imagine care arată spațiul problemelor P, NP, NP-Complet și NP-Dificil

Clasă de complexitate --> NP-Dificil
Semnificație La fel de dificil ca NP-Complet sau mai dificil
Exemplu Planificare optimă cu dependențe complexe, neverificabilă
Analogie „Găsirea orei optime pentru o întâlnire cu multe constrângeri, neverificabilă rapid"
Punct cheie Posibil imposibil de rezolvat în practică
1 https://www.baeldung.com/cs/p-np-np-complete-np-hard
Concepte în Informatică

Marea enigmă: P=NP?

O diagramă care ridică întrebarea fundamentală de cercetare: P=NP?

Concepte în Informatică

Să exersăm!

Concepte în Informatică

Preparing Video For Download...