1. Examen complex Matemetici speciale (disciplinile:

Matematica discretă, Analiza şi proiectarea algoritmilor Structuri de date și algoritmi Limbaje formale și proiectarea compilatoarelor )

1.1. Matematica discretă

Algebra logicii

Tabele de adevăr. Formule echivalente. Algebra booleană Proprietăţile operaţiilor booleene.

Decompoziţia funcţiilor logice. Forma canonică disjunctivă (FCD). Forma canonică conjunctivă (FCC). Sisteme complete de funcţii booleene. Minimizarea FCD şi FCC. Metoda lui Quine, Quine-McCluskey, diagrame Karnaugh.

Reprezentarea funcţiei logice prin scheme logice şi diagrame de timp

Grafuri

Grafuri neorientate şi grafuri orientate. Definiţia de bază în teoria grafurilor. Metode de reprezentare a grafului. Noţiuni generale. Matrici, liste.

Drumuri şi circuite în grafuri. Algoritmi pe grafuri. Algoritmul de căutare în largime şi dîncime. Noţiune de graf de acoperire. Algoritmul de determinare a grafului de acoperire. Drum minim (maxim). Algoritmul lui Ford şi Bellman-Calaba pentru determinarea drumului minim (maxim). Determinarea drumului hamiltonian într-un graf orientat fără circfuite. Teorema lui I.C.Chen. Determinarea drumului hamiltonian într-un graf orientat, ce conţine circuite. Determinarea drumurilor elementare. Reţea de transport. Algoritmul Ford-Fulkerson pentru determinarea fluxului maxim.

Probleme tipice la disciplina Matematica discretă

1. Pentru funcţia logică dată determinaţi FCD şi FCC.2. Pentru funcţia logică de patru variabile să se determine forma disjunctivă minimă după metoda lui Quine.3. Să se determine forma disjunctivă minimă şi forma conjunctivă minimă a funcţiei logice de patru variabile

după metoda lui Quine-McCluskey.4. Reprezentaţi prin diagrama în timp funcţia logică dată.5. Pentru funcţia logică dată construiţi schema logică în baza ŞI-NU.6. Pentru funcţia logică dată construiţi schema logică în baza SAU-NU.7. Fiind dată matricea de adiacenţă a unui graf orientat, să se deducă:a) gradele vârfurilor;b) dacă există vârfuri izolate;c) dacă graful este complet.8. Folosind algoritmul lui Ford determinaţi pentru graful dat drumurile minime şi maxime dintre vârfurile

date.9. Folosind algoritmul lui Belman-Calaba determinaţi pentru graful dat drumurile minime şi maxime dintre

vârfurile date.

10. Folosind algoritmul lui Ford-Fulkerson determinaţi valoarea fluxului maxim pentru reţeaua de transport dată.

11. Construiţi tabelele de adevăr, determinaţi forma canonică disjunctivă, stabiliţi forma minimă şi implementaţi în bazele “ŞI-NU”, “SAU-NU” funcţiile logice:

,

= .

12. Pentru funcţiile logice date elaboraţi schemele logice în baza „ŞI-NU” şi în baza „SAU-NU” şireprezentaţi funcţiile prin diagrame temporale:

12.Să se determine drumul hamiltonian în graful ,

13. Să se determine drumurile hamiltoniene în graful ,

1.2 . Analiza şi proiectarea algoritmilor

1. Complexitatea calculului. 1. Complexitatea abstractă. 2. Complexitatea structurală. 3. Complexitate concretă. 4. Resursele de calcul.5. Complexitatea spaţială.6. Complexitatea temporală. 7. Timpul de execuţie al unui algoritm.8. Complexitatea asimptotică. 9. Θ – notaţia. O – notaţia. Ω – notaţia.10. o – notaţia. - notaţia. ~ - notaţia 11. Relaţii de recurenţă. Metoda ecuaţiilor caracteristice. Recurenţe liniare omogene. 12. Recurenţe liniare neomogene. 13. Schimbarea variabilei. 14. Metoda master.15. Tehnica divide şi stăpâneşte de proiectare a algoritmilor.16. Tehnica greedy de proiectare a algoritmilor.17. Programarea dinamică.

2.4. Limbaje formale şi compilatoare

Gramatici şi limbaje formale clasificabile ChomskyAutomate finite deterministe şi nedeterministeEchivalenţa gramaticilor regulate şi a automatelor finiteLema de pompare şi aplicaţiile ei

2

Arbori de derivare, teorema de ramificareTransformări echivalente asupra gramaticilor independente de context. Eliminarea simbolurilor inutile, redenumirilorForma normală ChomskyRecursia de stânga. Forma normală GreibachTeorema “uvwxy” şi aplicaţiile eiEchivalenţa gramaticilor independente de context şi a automatelor stivăAnaliza sintactică descendentă. Recursivitatea stângă şi factorizarea gramaticilorMaşina de analiză predictivăGramatici şi analizoare LL(k)Analiza sintactică ascendentă. Maşina de analiză “deplasează-reduce”Gramatici de precedenţă. Algoritmul de construire a relaţiilor de precedenţă. Precedenţa slabă

Probleme tipice la disciplina Limbaje formale şi compilatoare

1. Pentru automatul finit nedeterminist dat să se construiască automatul finit determinist echivalent.2. Pentru gramatica regulată dată să se construiască automatul finit echivalent. 3. Pentru automatul finit dat să se construiască gramatica regulată echivalentă.4. Aplicînd lema de pompare pentru cuvântul z să se construiască descompunerea z=uvw.5. Să se simplifice eliminînd simbolurile neproductive şi inaccesibile gramatica independentă de context

dată.6. Să se aducă la forma normală Chomsky gramatica independentă de context dată.7. Să se elimine recursia stângă.8. Să se elimine -producţiile.9. Aplicînd teorema “uvwxz” pentru cuvântul z să se construiască descompunerea z=uvwxy.10. Pentru gramatica independentă de context dată să se construiască analizorul sintactic LL(1).

3

2. Examen complex Programare (disciplinile: Programarea în C, C++,

Baze de date, APPOO

AMSI)

2.1. Programarea în C, C++Tipuri de date. Declararea variabilelor. Operaţiile limbajului C/C++. Clasificarea operaţiilorOperatorii limbajului C/C++. Clasificarea operatorilor (logici, aritmetici, etc.)Conversia de tip.Operatori condiţionali (if-else), ramificare (switch, break)Operatori ciclu (for, while, until)Preprocesorul limbajului C şi structura programuluiFuncţiile limbajului C/C++. Prototipul funcţiei. Argumentele funcţieiTablouri. Definirea tablourilor unidimensionale şi bidimensionalePointerii în C/C++. Referinţele în C++. Pointerii şi TablourilePointerii şi referinţele în calitate de argumente ale funcţiilorAritmetica adreselor. Tablouri de pointeri. Pointer la pointerStructuri. Definirea structurilor. Structuri şi funcţii. Tablouri de structuriUniuni. Definirea uniunilor. Uniuni videRecursiaŞiruri simbolice. Funcţii ce operează cu şiruri simboliceFişiere. Pointeri la fişiere. Funcţiile ce operează cu fişiereleClase, structuri şi uniuni. Funcţii inline. Funcţii inline în declararea claseiAtribuirea obiectelor. Transmiterea obiectelor funcţiilorFuncţii prietene.Tablouri de obiecte. Utilizarea pointerilor la obiecte. Operatorul THISOperatorii NEW şi DELETE. Alocarea şi eliberarea memorie dinamice în C/C++Redefinirea funcţiilor. Redefinirea constructorilor. Definirea şi utilizarea constructori copii. Argumentele implicite.Redefinirea operatorilor. Redefinirea operatorilor binari, relaţionali şi logiciRedefinirea operatorilor unariMoştenirea. Gestionarea accesului la clasa de bază. Constructorii, destructorii şi moştenirea lor. Moştenirea multiplăClase de bază virtuale. Funcţii virtuale. Pointeri la clase derivate. Aplicarea polimorfismului

Probleme tipice la disciplina Programarea în C, C++

11. Recursia. Pentru o secvenţă de program dată şi cîteva alternative de răspuns să se aleagă alternativa corectă.

12. Pentru o secvenţă de program dată scrisă în C++, să se găsească erorile posibile şi să se explice sensul lor. Ca exemple pot fi secvenţe de formă generală, secvenţe ce conţin operatori condiţionali, ramificare, de luare a deciziilor, etc.

13. Clase. Constructori, destructori. Moştenirea claselor. Obiecte. Structuri şi Uniuni. Să se scrie scrie o secvenţă de program cu utilizarea tehnicilor menţionate.

14. Obiecte. Pointeri la obiecte. Referinţe la obiecte. Transmiterea obiectelor funcţiilor. Transmiterea obiectelor în funcţii prin utiizarea pointerilor şi referinţelor. Să se scrie o secvenţă de program cu utilizarea tehnicilor menţionate.

4

15. Masive de obiecte. Alocarea memoriei dinamice cu ajutorul operatorilor NEW şi DELETE. Să se scrie o secvenţă de program cu utilizarea tehnicilor menţionate.

16. Funcţii prietene. Redefinirea funcţiilor. Redefinirea operatorilor binari, logici, unari, index, etc. Să se scrie o secvenţă de program ce va efectua redefinirea unei funcţii/operator şi va declara o funcţie prietenă cărei-va clase.

17. Exemple cu formatarea Intrării/Ieşirei. Gestiunea operaţiilor de Intrare/Ieşire. Funcţiile utilizator ce efectuiază operaţiile de Intrare/Ieşire.

18. Exemple cu operaţii de Intrare/Ieşire în fişiere. Accesul necondiţionat la conţinutul fişierului.

2.2. Baze de date

1. Algebra relaţionalăOperaţiile tradiţionale pe mulţimi. Scheme relaţionale compatibile. Uniunea. Intersecţia. Diferenţa. Produsul cartezian. Redenumirea atributelor. Complementul. Operaţiile relaţionale native. Proiecţia. Selecţia. Joncţiunea (Joncţiunea naturală). Semijoncţiunea. Divizarea. Expresii algebrice. Selecţii generalizate. Cereri conjunctive. Cereri cu diferenţe. Complementul unei mulţimi. Cuantificarea universală.

2. Limbajul SQLComponentele generale ale SQL. Tipuri de date. Definirea schemei bazei de date. Crearea schemei relaţionale. Modificarea şi suprimarea schemei relaţionale. Cele mai simple cereri. Cereri de selecţie. Criterii de selecţie. Cereri de agregare. Funcţii de agregare. Agregarea tuplurilor. Actualizarea bazei de date. Inserarea tuplurilor. Modificarea tuplurilor. Suprimarea tuplurilor. Cereri multi-relaţie. Uniunea, intersecţia şi diferenţa cererilor. Cereri cu joncţiuni. Cereri imbricate. Definirea accesului la baza date. Definirea utilizatorilor. Permise asupra relaţiilor. Sinonime. Blocarea relaţiilor şi gestiunea tranzacţiilor. Viziuni. Indecşi. Constrângeri şi aserţiuni. Declanşatoare. Probleme tipice la disciplina Baze de date 1. Fie relaţiile r(ABC) şi s(ABC) de mai jos:

r A B C s A B C

a1 b2 c1 a2 b1 c2a2 b1 c1 a2 b2 c2a1 b2 c2 a2 b1 c3a1 b1 c1 a1 b2 c1a1 b3 c2 a2 b2 c1a2 b2 c2a2 b1 c2

Să se găsească relaţia reprezentată de expresia algebrei relaţionale:(Cc3) & (Bb3)(rs) ABC(r\~s)

2. Fie schema bazei de date

articole(Art_Id, Art_Nume, Oraş, Bucăţi, Preţ);clienţi(Cl_Id, Cl_Nume, Cl_Oraş, Reducere);agenţi(Ag_Id, Ag_Nume, Ag_Oraş, Comision);comenzi(Lună, Cl_Id, Ag_Id, Art_Id, ComBucăţi, Sumă).

Examinaţi schema bazei de date de mai sus şi exprimaţi următoarea întrebare în algebra relaţională:

5

a) Să se găsească numele şi oraşele articolelor care au fost vândute în luna ianuarie b) Care sunt clienţii ce nu au cumpărat nici un articol de un preţ mai mic sau egal cu 100

3. Fie schema bazei de date

uzine(UzinăID, UzinăNume, UzinăOraş)articole(ArticolID, ArticolNume, Culoare, Greutate)furnizori(FurnizorID, FurnizorNume, Statut, FurnOraş)livrări(ArticolID, UzinăID, FurnizorID, Cantitate)

Examinaţi schema bazei de date de mai sus şi exprimaţi următoarea întrebare în limbajul SQL:a) Denumirile şi culorile articolelor livrate de furnizorul nr.1.b) Uzinele care se aprovizionează numai prin furnizorul nr.3.

6