1. Examen complex Cercetari operationale

(disciplinile:Cercetari operationale,

Matematica discreta,

Teoria probabilitatii si informatiei

Analiza si proiectarea algoritmilor)

Cercetari operationale

Notiuni generale

Probleme de decizie. Modele matematice ale problemelor de decizie. Obiectul de studiu "Cercetarii Operationale"

Clasificarea problemelor de decizie. Functie de utilitate. Criterii de decizie

Metoda matematica a unor probleme de decizie

Notiuni de multimi si functii convexe

Multimi convexe. Teoreme de separare pentru multimi convexe

Puncte extreme pentru multimi convexe. Sisteme de ecuatii liniare

Programarea liniara

Problema generala de programare liniara. Exemple de probleme de PL (problema dietei, problema utilizarii optime a resurselor disponibile, problema de transport)

Forme ale unei probleme PL

Interpretarea geometrica a problemelor de PL cu doua variabile. Metoda grafica de rezolvare

Solutie admisibila de baza. Criteriul de optimalitate

Algoritmul Symplex primar. Tabele Symplex

Determinarea solutiei initiale de baza. Metoda lui M-mare.

Dualitatea in programarea liniara. Probleme duale simetrice

Teoreme duale ale programarii liniare

Interpretarea economica a problemei duale de programare liniara

Algoritmul Symplex dual

Analiza modelelor liniare la sensibilitate

Reoptimizari. Parametrizari

Programarea liniara in numere intregi

Formularea problemei. Problema rucsacului. Problema de afectare. Problema voiajorului comercial

Generalitati privind metodele de rezolvare a problemelor de programare in variabile intregi

Metodele de sectionare ale lui Gomory

Metodele de ramificare si marginire

Metode de rezolvare a problemelor de optimizare neconditionata

Conditiile de extrem in optimizarea neconditionata

Metode de gradient.

Metoda Newton

Metode de directii conjugate

Programare neliniara

Functia lui Lagrange asociata unei probleme de programare matematica

Conditiile Kuhn-Tucker asociate unei probleme de programare matematica

Metodele de rezolvare a problemelor de programare convexa:

metoda planurilor de sectiune

metoda de directii admisibile

metode de penalizare

Probleme tipice la disciplina Cercetari operationale

Utilizand algoritmul simplex, sa se afle valorile extreme ale functiei liniare considerate in cazul cand sunt satisfacute conditiile liniare date. Metoda lui M-mare.

De rezolvat problema de programare liniara, utilizand algoritmul simplex dual.

Analizati modelul liniar la sensibilitate.

Sa se rezolve prin metoda grafica jocurile matriceale.

Sa se reduca jocul matriceal la rezolvarea a doua probleme duale simetrice de programare liniara.

Sa se rezolve problema de programare liniara in numere intregi, utilizand primul algoritm al lui Gomory.

Sa se rezolve problema de programare liniara in numere intregi, utilizand al doilea algoritm al lui Gomory.

Sa se rezolve problema de programare neliniara, utilizand conditiile Kunh-Tucker.

Matematica discreta

Algebra logicii

Tabele de adevar. Formule echivalente.

Algebra booleana Proprietatile operatiilor booleene.

Decompozitia functiilor logice.

Forma canonica disjunctiva (FCD). Forma canonica conjunctiva (FCC).

Sisteme complete de functii booleene.

Minimizarea FCD si FCC. Metoda lui Quine, Quine McCluskey, diagrame Karnaugh

Reprezentarea functiei logice prin scheme logice si diagrame de timp

Grafuri

Grafuri neorientate si grafuri orientate. Definitia de baza in teoria grafurilor.

Metode de reprezentare a grafului. Notiuni generale. Matrici, liste.

Drumuri si circuite in grafuri.

Algoritmi pe grafuri. Algoritmul de cautare in largime si dincime.

Notiune de graf de acoperire. Algoritmul de determinare a grafului de acoperire.

Drum minim (maxim). Algoritmul lui Ford si Bellman-Calaba pentru determinarea drumului minim (maxim).

Determinarea drumului hamiltonian intr-un graf orientat fara circfuite. Teorema lui I.C.Chen.

Determinarea drumului hamiltonian intr-un graf orientat, ce contine circuite.

Determinarea drumurilor elementare.

Retea de transport. Algoritmul Ford-Fulkerson pentru determinarea fluxului maxim.

Probleme tipice la disciplina Matematica discreta

Pentru functia logica data determinati FCD si FCC.

Pentru functia logica de patru variabile sa se determine forma disjunctiva minima dupa metoda lui Quine.

Sa se determine forma disjunctiva minima si forma conjunctiva minima a functiei logice de patru variabile dupa metoda lui Quine-McCluskey.

Reprezentati prin diagrama in timp functia logica data.

Pentru functia logica data construiti schema logica in baza SI-NU.

Pentru functia logica data construiti schema logica in baza SAU-NU.

Fiind data matricea de adiacenta a unui graf orientat, sa se deduca:

a)      gradele varfurilor;

b)      daca exista varfuri izolate;

c)      daca graful este complet.

Folosind algoritmul lui Ford determinati pentru graful dat drumurile minime si maxime dintre varfurile date.

Folosind algoritmul lui Belman-Calaba determinati pentru graful dat drumurile minime si maxime dintre varfurile date.

Folosind algoritmul lui Ford-Fulkerson determinati valoarea fluxului maxim pentru reteaua de transport data.

Construiti tabelele de adevar, determinati forma canonica disjunctiva, stabiliti forma minima si implementati in bazele "SI-NU", "SAU-NU" functiile logice:

=.

Pentru functiile logice date elaborati schemele logice in baza "SI-NU" si in baza "SAU-NU" si

reprezentati functiile prin diagrame temporale:

12.Sa se determine drumul hamiltonian in graful ,

13. Sa se determine drumurile hamiltoniene in graful ,

Document online: Probleme de integrare a copiilor cu cerinte educative speciale Referat: Animale domestice - poze si fise cu familiile de animale domestice

Teoria probabilitatii si informatiei

Obiectul de studiu "Teoria probabilitatilor"

Notiune de eveniment aleator. Operatii asupra evenimentelor

Definitia axiomatica a probabilitatii. Proprietatile ei

Definitia clasica a probabilitatii. Probabilitatea geometrica. Probabilitati conditionate

Independenta evenimentelor. Formula probabilitatii totale. Formula Bayes

Notiune de variabile aleatoare. Functia de reparatie a variabilelor aleatoare si proprietatile ei

Variabile aleatoare de tip discret si repartitia lor. Variabile aleatoare de tip continuu si densitatea lor de repartitie

Cele mai importante repartitii (model) de tip discret si continuu

Caracteristici numerice ale variabilelor aleatoare: valoarea medie, dispersia si proprietatile lor. Covariatia si coeficientul de corelatie

Inegalitatea Cebisev. Legea numerelor mari. Teorema limita centrala si aplicarea ei la modelarea statistica

Elemente ale teorii informatiei

Probleme tipice la disciplina Teoria probabilitatii si informatiei

Variabila aleatoare X este determinata de functia de repartitie

Determinati:

a)      Functia de repartitie F(x),

b)      Valoarea medie M_x ,

c)      Dispersia D_x,,

d)      Probabilitatea ca variabilele aleatoare X sa primeasca valori din intervalul .

Variabila aleatoare X este determinata de functia de repartitie

Determinati:

a)      Functia de repartitie F(x),

b)      Valoarea medie M_x ,

c)      Dispersia D_x,,

d)      Probabilitatea ca variabilele aleatoare X sa primeasca valori din intervalul.

Variabila aleatoare X este determinata de functia de repartitie

Determinati:

a)      Functia de repartitie F(x),

b)      Valoarea medie M_x ,

c)      Dispersia D_x,,

d)      Probabilitatea ca variabilele aleatoare X sa primeasca valori din intervalul .

Variabila aleatoare X este determinata de functia de repartitie

Determinati:

a)      Functia de repartitie F(x),

b)      Valoarea medie M_x ,

c)      Dispersia D_x,,

d)      Probabilitatea ca variabilele aleatoare X sa primeasca valori din intervalul .

Variabila aleatoare X este determinata de functia de repartitie

Determinati:

a)      Functia de repartitie F(x),

b)      Valoarea medie M_x ,

c)      Dispersia D_x,,

d)      Probabilitatea ca variabilele aleatoare X sa primeasca valori din intervalul .

6. Sunt doua urne: in prima sunt 5 bile albe si 4 negre, iar in a doua sunt 4 bile albe si 5 negre. Din prima urna se scoate 3 bile la intimplare si se arunca in a doua urna. Dupa aceasta din urna a doua se scoat 2 bile. Sa se determine probabilitatea ca ambele sunt albe.

Analiza si proiectarea algoritmilor

1. Complexitatea calculului.

2. Complexitatea abstracta.
3. Complexitatea structurala.
4. Complexitate concreta.
5. Resursele de calcul.
6. Complexitatea spatiala.
7. Complexitatea temporala.
8. Timpul de executie al unui algoritm.
9. Complexitatea asimptotica.
10. Θ - notatia. O - notatia. Ω - notatia.
11. o - notatia. v - notatia. ~ - notatia
12. Relatii de recurenta. Metoda ecuatiilor caracteristice. Recurente liniare omogene.
13. Recurente liniare neomogene.
14. Schimbarea variabilei.
15. Metoda master.
16. Tehnica divide si stapaneste de proiectare a algoritmilor
17. Tehnica greedy de proiectare a algoritmilor
18. Programarea dinamica.

2. Examen complex Programare

(disciplinile:Programarea in C, C++,

Baze de date,

Limbaje formale si compilatoare)

Programarea in C, C++

Tipuri de date. Declararea variabilelor. Operatiile limbajului C/C++. Clasificarea operatiilor

Operatorii limbajului C/C++. Clasificarea operatorilor (logici, aritmetici, etc.)

Conversia de tip.

Operatori conditionali (if-else), ramificare (switch, break)

Operatori ciclu (for, while, until)

Preprocesorul limbajului C si structura programului

Functiile limbajului C/C++. Prototipul functiei. Argumentele functiei

Tablouri. Definirea tablourilor unidimensionale si bidimensionale

Pointerii in C/C++. Referintele in C++. Pointerii si Tablourile

Pointerii si referintele in calitate de argumente ale functiilor

Aritmetica adreselor. Tablouri de pointeri. Pointer la pointer

Structuri. Definirea structurilor. Structuri si functii. Tablouri de structuri

Uniuni. Definirea uniunilor. Uniuni vide

Recursia

Siruri simbolice. Functii ce opereaza cu siruri simbolice

Fisiere. Pointeri la fisiere. Functiile ce opereaza cu fisierele

Clase, structuri si uniuni. Functii inline. Functii inline in declararea clasei

Atribuirea obiectelor. Transmiterea obiectelor functiilor

Functii prietene.

Tablouri de obiecte. Utilizarea pointerilor la obiecte. Operatorul THIS

Operatorii NEW si DELETE. Alocarea si eliberarea memorie dinamice in C/C++

Redefinirea functiilor. Redefinirea constructorilor. Definirea si utilizarea constructori copii. Argumentele implicite.

Redefinirea operatorilor. Redefinirea operatorilor binari, relationali si logici

Redefinirea operatorilor unari

Mostenirea. Gestionarea accesului la clasa de baza. Constructorii, destructorii si mostenirea lor. Mostenirea multipla

Clase de baza virtuale. Functii virtuale. Pointeri la clase derivate. Aplicarea polimorfismului

Probleme tipice la disciplina Programarea in C, C

Recursia. Pentru o secventa de program data si citeva alternative de raspuns sa se aleaga alternativa corecta.

Pentru o secventa de program data scrisa in C++, sa se gaseasca erorile posibile si sa se explice sensul lor. Ca exemple pot fi secvente de forma generala, secvente ce contin operatori conditionali, ramificare, de luare a deciziilor, etc.

Clase. Constructori, destructori. Mostenirea claselor. Obiecte. Structuri si Uniuni. Sa se scrie scrie o secventa de program cu utilizarea tehnicilor mentionate.

Obiecte. Pointeri la obiecte. Referinte la obiecte. Transmiterea obiectelor functiilor. Transmiterea obiectelor in functii prin utiizarea pointerilor si referintelor. Sa se scrie o secventa de program cu utilizarea tehnicilor mentionate.

Masive de obiecte. Alocarea memoriei dinamice cu ajutorul operatorilor NEW si DELETE. Sa se scrie o secventa de program cu utilizarea tehnicilor mentionate.

Functii prietene. Redefinirea functiilor. Redefinirea operatorilor binari, logici, unari, index, etc. Sa se scrie o secventa de program ce va efectua redefinirea unei functii/operator si va declara o functie prietena carei-va clase.

Exemple cu formatarea Intrarii/Iesirei. Gestiunea operatiilor de Intrare/Iesire. Functiile utilizator ce efectuiaza operatiile de Intrare/Iesire.

Exemple cu operatii de Intrare/Iesire in fisiere. Accesul neconditionat la continutul fisierului.

2.3. Baze de date

1. Algebra relationala

Operatiile traditionale pe multimi. Scheme relationale compatibile. Uniunea. Intersectia. Diferenta. Produsul cartezian. Redenumirea atributelor. Complementul. Operatiile relationale native. Proiectia. Selectia. Jonctiunea (Jonctiunea naturala). Semijonctiunea. Divizarea. Expresii algebrice. Selectii generalizate. Cereri conjunctive. Cereri cu diferente. Complementul unei multimi. Cuantificarea universala.

2. Limbajul SQL

Componentele generale ale SQL. Tipuri de date. Definirea schemei bazei de date. Crearea schemei relationale. Modificarea si suprimarea schemei relationale. Cele mai simple cereri. Cereri de selectie. Criterii de selectie. Cereri de agregare. Functii de agregare. Agregarea tuplurilor. Actualizarea bazei de date. Inserarea tuplurilor. Modificarea tuplurilor. Suprimarea tuplurilor. Cereri multi-relatie. Uniunea, intersectia si diferenta cererilor. Cereri cu jonctiuni. Cereri imbricate. Definirea accesului la baza date. Definirea utilizatorilor. Permise asupra relatiilor. Sinonime. Blocarea relatiilor si gestiunea tranzactiilor. Viziuni. Indecsi. Constrangeri si asertiuni. Declansatoare.

Probleme tipice la disciplina Baze de date

1. Fie relatiile r(ABC) si s(ABC) de mai jos:

Sa se gaseasca relatia reprezentata de expresia algebrei relationale:

s_{(C c3) & (B b3)}(r s)p_ABC(r^~s)

2. Fie schema bazei de date

articole(Art_Id, Art_Nume, Oras, Bucati, Pret);

clienti(Cl_Id, Cl_Nume, Cl_Oras, Reducere);

agenti(Ag_Id, Ag_Nume, Ag_Oras, Comision);

comenzi(Luna, Cl_Id, Ag_Id, Art_Id, ComBucati, Suma).

Examinati schema bazei de date de mai sus si exprimati urmatoarea intrebare in algebra relationala:

a) Sa se gaseasca numele si orasele articolelor care au fost vandute in luna ianuarie

b) Care sunt clientii ce nu au cumparat nici un articol de un pret mai mic sau egal cu 100

3. Fie schema bazei de date

uzine(UzinaID, UzinaNume, UzinaOras)

articole(ArticolID, ArticolNume, Culoare, Greutate)

furnizori(FurnizorID, FurnizorNume, Statut, FurnOras)

livrari(ArticolID, UzinaID, FurnizorID, Cantitate)

Examinati schema bazei de date de mai sus si exprimati urmatoarea intrebare in limbajul SQL:

a) Denumirile si culorile articolelor livrate de furnizorul nr.1.

b) Uzinele care se aprovizioneaza numai prin furnizorul nr.3.

Limbaje formale si compilatoare

Gramatici si limbaje formale clasificabile Chomsky

Automate finite deterministe si nedeterministe

Echivalenta gramaticilor regulate si a automatelor finite

Lema de pompare si aplicatiile ei

Arbori de derivare, teorema de ramificare

Transformari echivalente asupra gramaticilor independente de context. Eliminarea simbolurilor inutile, redenumirilor

Forma normala Chomsky

Recursia de stanga. Forma normala Greibach

Teorema "uvwxy" si aplicatiile ei

Echivalenta gramaticilor independente de context si a automatelor stiva

Analiza sintactica descendenta. Recursivitatea stanga si factorizarea gramaticilor

Masina de analiza predictiva

Gramatici si analizoare LL(k)

Analiza sintactica ascendenta. Masina de analiza "deplaseaza-reduce"

Gramatici de precedenta. Algoritmul de construire a relatiilor de precedenta. Precedenta slaba

Probleme tipice la disciplina Limbaje formale si compilatoare

Pentru automatul finit nedeterminist dat sa se construiasca automatul finit determinist echivalent.

Pentru gramatica regulata data sa se construiasca automatul finit echivalent.

Pentru automatul finit dat sa se construiasca gramatica regulata echivalenta.

Aplicind lema de pompare pentru cuvantul z sa se construiasca descompunerea z=uvw.

Sa se simplifice eliminind simbolurile neproductive si inaccesibile gramatica independenta de context data.

Sa se aduca la forma normala Chomsky gramatica independenta de context data.

Sa se elimine recursia stanga.

Sa se elimine e-productiile.

Aplicind teorema "uvwxz" pentru cuvantul z sa se construiasca descompunerea z=uvwxy.

Pentru gramatica independenta de context data sa se construiasca analizorul sintactic LL(1).