Cursuri teoria_computării computational_complexity vf

În domeniul informaticii, teoria complexității computaționale este o secțiune a teoriei computaționale care studiază costul muncii necesare pentru a rezolva o problemă computațională. Valoarea este măsurată prin concepte abstracte ale timpului și spațiului, numite resurse de calcul. Timpul este determinat de numărul de pași elementari necesari pentru găsirea unei soluții și de spațiul de cantitatea de memorie folosită în acest proces.







Astfel, se face o încercare de a răspunde la întrebarea centrală a dezvoltării de algoritmi, „cum să se schimbe timpul de execuție și cantitatea de memorie, în funcție de dimensiunea datelor de intrare și rezultatul?“.

Conceptul algoritmului a fost format din timpuri străvechi [1], [2]. dar până la sfârșitul primei treimi a secolului XX. matematica a fost mulțumită de ideea intuitivă a acestui obiect. Termenul "algoritm" a fost folosit în matematică numai în legătură cu anumiți algoritmi specifici. Declarația despre existența unui algoritm de rezolvare a problemelor de un anumit tip a fost însoțită de descrierea sa reală.







Fiecare algoritm presupune prezența unor date inițiale sau inițiale, iar ca urmare a aplicării duce la obținerea unui anumit rezultat dorit.

Aplicarea fiecărui algoritm se realizează prin efectuarea unui lanț discret (secvență) a anumitor acțiuni elementare. Aceste acțiuni sunt numite pași, iar procesul de execuție a acestora este numit proces algoritmic. Astfel, se remarcă proprietatea discretă a algoritmului. O caracteristică esențială a algoritmului este caracterul său de masă, adică capacitatea de a le aplica unei mari categorii de date inițiale. Cu alte cuvinte, fiecare algoritm este conceput pentru a rezolva o clasă de probleme de tip unic.

O condiție indispensabilă pe care algoritmul o satisface este determinismul sau certitudinea lui. Aceasta înseamnă că instrucțiunile algoritmului sunt atât de precise și distincte încât nu permit interpretări ambigue. Ele duc la rezultatul dorit prin modul singular și destul de clar.

Care este complexitatea sarcinii? Complexitatea algoritmică a celei mai simple soluții.

Din punct de vedere practic, înțelegerea complexității algoritmului ajută:

din punct de vedere cantitativ și calitativ, diferite soluții ale aceleiași probleme

pentru a evalua complexitatea problemei care trebuie rezolvată







Trimiteți-le prietenilor: