SUBIECTE EXAMEN
METODE DE ANALIZĂ A ALGORITMILOR
SUBIECTE EXAMEN
METODE DE ANALIZĂ A ALGORITMILOR
TEORIE
1) (0,5p) Definiţia algoritmului:
2) (0,5p) Un algoritm cuprinde:
o Domeniu de date:
o Descrierea algoritmului:
3) (0,5p) Starea unui algoritm reprezintă:
4) (0,5p) Sintaxa intrucţiunii IF-THEN-ELSE
5) (0,5p) Sintaxa instrucţiunii WHILE
6) (0,5p) Sintaxa instrucţiunii FOR
7) (0,5p) Sintaxa instrucţiunii REPEAT
8) (1p) Proprietăţile algoritmilor:
o Generalitate
o Finititudine
o Unicitate
9) (1p) Metode de verificare a corectitudinii algoritmilor:
o Analiza experimentală
o Analiza formală
10) (1,5p) Principalele etape ale analizei formale:
o Problema precondiţiilor
o Problema postcondiţiilor
11) (0,5p) Verificarea corectitudinii algoritmului
o Algoritm parţial corect
o Algoritm total corect
12) (1,5p) Verificarea corectitudinii instrucţiunilor repetitive
o Corectitudine parţială
o Corectitudine totală
o Proprietăţi invariante
13) (0,5p) Modelul teoretic al mașinii Turing
14) (1p) Arhitectura mașinii Turing
15) (0,5p) Definiţia maşinii Turing.
16) (1p) Calcule deterministe pentru o mașină Turing. Mașina Turing deterministă
1
SUBIECTE EXAMEN
METODE DE ANALIZĂ A ALGORITMILOR
17) (1p) Calcule nedeterministe pentru o mașină Turing. Mașina Turing nedeterministă
18) (0,5p) Mașina Turing vs. Calculator
19) (0,5p) Configurație a unei Mașini Turing
20) (1p) Relația de “trecere” între două configurații
21) (0,5p) Funcţie Turing calculabilă
22) (0,5p) Limbaj decidabil în sens Turing
23) (1p) Analiza complexității algoritmilor
o Complexitate statică
o Complexitate dinamică
24) (1p) Timp de execuție. Modelul de calcul cu acces aleator
25) (0,5p) Cazul cel mai favorabil
26) (0,5p) Cazul cel mai defavorabil
27) (0,5p) Cazul mediu
28) (1p) Ipoteze de estimare a cazului mediu. Cazuri echiprobabile
29) (1p) Etapele analizei algoritmilor nerecursivi
30) (0,5p) Operație dominantă
31) (0,5p) Termen dominant
32) (1p) Ordinul de creștere
o Exemple de creșteri
33) (1p) Compararea algoritmilor în baza ordinului de creștere
34) (0,5p) Analiza asimptotică
35) (2p) Notația O. Definiție. Proprietăți
36) (2p) Notația Ω. Definiție. Proprietăți
37) (2p) Notația Θ. Definiție. Proprietăți
38) (1p) Interpretarea notațiilor asimptotice
39) (1p) Sumar al proprietăților notațiilor asimptotice
40) (1p) Clase de complexitate cu exemple de algoritmi
2
SUBIECTE EXAMEN
METODE DE ANALIZĂ A ALGORITMILOR
41) (2p) Analiza principalelor instrucțiuni:
o instrucțiunea secvențială
o instrucțiunea condițională
o instrucțiunea repetitivă
42) (1p) Metode generale de calcul pentru indicatorii de complexitate ai unui algoritm
43) (1,5p) Analiza algoritmilor nerecursivi vs. analiza algoritmilor recursivi.
44) (2p) Metoda Master. Cazuri de aplicare ale Teoremei Master
45) (0,5p) Algoritm determinist
46) (0,5p) Algoritm nedeterminist
47) (0,5p) Clase de complexitate P și NP.
Număr total de subiecte TEORIE
- 3 subiecte de 0,5p
- 3 subiecte de 1p
- 1 subiect de 1,5p
- 1 subiect de 2p
Număr maxim de puncte: 5p
EXERCIȚII
1. (1p) Corectitudinea funcțiilor recursive
2. (1p) Corectitudinea instrucțiunilor repetitive
3. (2p) Complexitatea algoritmilor a căror execuție nu depinde de proprietățile datelor de
intrare.
4. (3p) Complexitatea algoritmilor a căror execuție depinde de proprietățile datelor de
intrare:
o algoritmul de sortare prin interschimbare
o algoritmul de sortare prin inserție
3
SUBIECTE EXAMEN
METODE DE ANALIZĂ A ALGORITMILOR
o algoritmului de căutare liniară
o agloritmul care testează dacă un vector conține numai elemente distincte
5. (2p) Determinarea ordinului de complexitate pe baza relației de recursie folosind:
o metoda iterației
o metoda substituției
o metoda arborilor de recursie
o metoda Master
6. (3p) Complexitatea algoritmilor recursivi:
o algoritmul de căutare binară
o algoritmul de sortare prin interschimbare
o algoritmul Turnurile din Hanoi
Număr total de subiecte EXERCIȚII:
- 2 subiecte de 1p
- 1 subiect de 2p
- 1 subiect de 3p
Număr maxim de puncte: 4p