1. Examen complex Cercetări operaţionale (disciplinile:Cercetări operaţionale,

Matematica discretă, Teoria probabilităţii şi informaţieiAnaliza şi proiectarea algoritmilor)

1.1. Cercetări operaţionaleNoţiuni generale

Probleme de decizie. Modele matematice ale problemelor de decizie. Obiectul de studiu “Cercetării Operaţionale”Clasificarea problemelor de decizie. Funcţie de utilitate. Criterii de decizieMetoda matematică a unor probleme de decizie

Noţiuni de mulţimi şi funcţii convexeMulţimi convexe. Teoreme de separare pentru mulţimi convexePuncte extreme pentru mulţimi convexe. Sisteme de ecuaţii liniare

Programarea liniarăProblema generală de programare liniară. Exemple de probleme de PL (problema dietei, problema utilizării optime a resurselor disponibile, problema de transport)Forme ale unei probleme PLInterpretarea geometrică a problemelor de PL cu două variabile. Metoda grafică de rezolvareSoluţie admisibilă de bază. Criteriul de optimalitateAlgoritmul Symplex primar. Tabele SymplexDeterminarea soluţiei iniţiale de bază. Metoda lui M-mare.Dualitatea în programarea liniară. Probleme duale simetriceTeoreme duale ale programării liniareInterpretarea economică a problemei duale de programare liniarăAlgoritmul Symplex dualAnaliza modelelor liniare la sensibilitateReoptimizări. Parametrizări

Programarea liniară în numere întregiFormularea problemei. Problema rucsacului. Problema de afectare. Problema voiajorului comercialGeneralităţi privind metodele de rezolvare a problemelor de programare în variabile întregiMetodele de secţionare ale lui GomoryMetodele de ramificare şi mărginire

Metode de rezolvare a problemelor de optimizare necondiţionatăCondiţiile de extrem în optimizarea necondiţionatăMetode de gradient.Metoda NewtonMetode de direcţii conjugate

Programare neliniarăFuncţia lui Lagrange asociata unei probleme de programare matematicăCondiţiile Kuhn-Tucker asociate unei probleme de programare matematicăMetodele de rezolvare a problemelor de programare convexă:

metoda planurilor de secţiune metoda de direcţii admisibile metode de penalizare

Probleme tipice la disciplina Cercetări operaţionale

1. Utilizând algoritmul simplex, să se afle valorile extreme ale funcţiei liniare considerate în cazul când sunt satisfăcute condiţiile liniare date. Metoda lui M-mare.

2. De rezolvat problema de programare liniară, utilizând algoritmul simplex dual.3. Analizaţi modelul liniar la sensibilitate.4. Să se rezolve prin metoda grafică jocurile matriceale.5. Să se reducă jocul matriceal la rezolvarea a două probleme duale simetrice de programare liniară.6. Să se rezolve problema de programare liniară în numere întregi, utilizând primul algoritm al lui Gomory.7. Să se rezolve problema de programare liniară în numere întregi, utilizând al doilea algoritm al lui

Gomory.8. Să se rezolve problema de programare neliniară, utilizând condiţiile Kunh-Tucker.

1.2. 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.

2

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.3. Teoria probabilităţii şi informaţieiObiectul de studiu “Teoria probabilităţilor”Noţiune de eveniment aleator. Operaţii asupra evenimentelorDefiniţia axiomatică a probabilităţii. Proprietăţile eiDefiniţia clasică a probabilităţii. Probabilitatea geometrică. Probabilităţi condiţionateIndependenţa evenimentelor. Formula probabilităţii totale. Formula BayesNoţiune de variabile aleatoare. Funcţia de reparaţie a variabilelor aleatoare şi proprietăţile eiVariabile aleatoare de tip discret şi repartiţia lor. Variabile aleatoare de tip continuu şi densitatea lor de repartiţieCele mai importante repartiţii (model) de tip discret şi continuuCaracteristici numerice ale variabilelor aleatoare: valoarea medie, dispersia şi proprietăţile lor. Covariaţia şi coeficientul de corelaţieInegalitatea Cebîşev. Legea numerelor mari. Teorema limită centrală şi aplicarea ei la modelarea statisticăElemente ale teorii informatiei

Probleme tipice la disciplina Teoria probabilităţii şi informaţiei

1. Variabila aleatoare X este determinată de funcţia de repartiţie

Determinaţi:a) Funcţia de repartiţie F(x),

3

b) Valoarea medie Mx ,c) Dispersia Dx,,d) Probabilitatea că variabilele aleatoare X să primească valori din intervalul .

2. Variabila aleatoare X este determinată de funcţia de repartiţie

Determinaţi:a) Funcţia de repartiţie F(x), b) Valoarea medie Mx , c) Dispersia Dx,, d) Probabilitatea că variabilele aleatoare X să primească valori din intervalul

.3. Variabila aleatoare X este determinată de funcţia de repartiţie

Determinaţi: a) Funcţia de repartiţie F(x), b) Valoarea medie Mx ,c) Dispersia Dx,, d) Probabilitatea că variabilele aleatoare X să primească valori din intervalul .

4. Variabila aleatoare X este determinată de funcţia de repartiţie

Determinaţi: a) Funcţia de repartiţie F(x), b) Valoarea medie Mx ,c) Dispersia Dx,, d) Probabilitatea că variabilele aleatoare X să primească valori din intervalul .

5. Variabila aleatoare X este determinată de funcţia de repartiţie

Determinaţi: a) Funcţia de repartiţie F(x), b) Valoarea medie Mx , c) Dispersia Dx,, d) Probabilitatea că variabilele aleatoare X să primească valori din intervalul .

6. Sunt două urne: în prima sunt 5 bile albe şi 4 negre, iar în a doua sunt 4 bile albe şi 5 negre. Din prima urnă se scoate 3 bile la întîmplare şi se aruncă în a doua urnă. După aceasta din urna a doua se scoat 2 bile. Să se determine probabilitatea că ambele sunt albe.

1.4. Analiza şi proiectarea algoritmilor

1. Complexitatea calculului. 2. Complexitatea abstractă. 3. Complexitatea structurală. 4. Complexitate concretă. 5. Resursele de calcul.6. Complexitatea spaţială.7. Complexitatea temporală. 8. Timpul de execuţie al unui algoritm.

4

9. Complexitatea asimptotică. 10. Θ – notaţia. O – notaţia. Ω – notaţia.11. o – notaţia. - notaţia. ~ - notaţia 12. Relaţii de recurenţă. Metoda ecuaţiilor caracteristice. Recurenţe liniare omogene. 13. Recurenţe liniare neomogene. 14. Schimbarea variabilei. 15. Metoda master.16. Tehnica divide şi stăpâneşte de proiectare a algoritmilor.17. Tehnica greedy de proiectare a algoritmilor.18. Programarea dinamică.

5

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

Baze de date, Limbaje formale şi compilatoare)

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++

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

2. 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.

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

4. 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.

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

6

6. 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.

7. 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.

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

2.3. 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ă:

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

7

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.

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 eiArbori 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

9. Pentru automatul finit nedeterminist dat să se construiască automatul finit determinist echivalent.10. Pentru gramatica regulată dată să se construiască automatul finit echivalent. 11. Pentru automatul finit dat să se construiască gramatica regulată echivalentă.12. Aplicînd lema de pompare pentru cuvântul z să se construiască descompunerea z=uvw.13. Să se simplifice eliminînd simbolurile neproductive şi inaccesibile gramatica independentă de context

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

8