+ All Categories
Home > Documents > Subiecte (INF)

Subiecte (INF)

Date post: 01-Feb-2017
Category:
Upload: trinhhanh
View: 277 times
Download: 2 times
Share this document with a friend
29
INFORMATICA (4 ani) LICENTA 2007 SUBIECTE PROPUSE LA DISCIPLINELE DE INFORMATICĂ 1. Algoritmi si Structuri de Date I 1. Algoritm de generarea a tuturor submultimilor unei multimi – descriere si implementare in Java. 2. Algoritm de simulare a inmultirii numerelor naturale mari – descriere si implementare in Java. 3. Algoritmi recursivi – descriere si implementare in Java (de exemplu, folosind problema acoperirii tablei de sah prin mutari ale calului). 4. Algoritm de generare a combinarilor – descriere si implementare in Java. 5. Algoritm de determinare a tuturor triangulatiilor unui poligon convex – descriere si implementare in Java. 6. Scrieti un program pentru determinarea tuturor radacinilor rationale ale unei ecuatii cu coeficienti intregi. 7. Scrieti un program pentru descompunerea unui numar natural ca suma de cat mai putini termeni din sirul Fibonacci ( 0 1 1 2 0, 1, , 2 k k k F F F F F k = = = + ). 8. Fie 1 x si 2 x radacinile ecuatiei 2 3 2 x x 0 + = si 1 n n S x x 2 n = + . Sa se scrie un program care determina numarul divizorilor lui . 50 S 9. Scrieti un program pentru determinarea numarului combinarilor de 1234 elemente luate cate 567 (atentie: rezultatul are 369 cifre!). 10. Scrieti un program care sa determine cea mai mica valoare a lui astfel incat n 1 2 1234567 ... n x x x = + + + si { } , ,1 k x kk k n 2. Algoritmi si Structuri de Date II 11. Metoda “backtracking” – descriere si exemple. 12. Algoritmi eficienti de sortare – descriere si exemple (quicksort, heapsort). 13. Metoda “programare dinamica” – descriere si exemple. 14. Algoritmi pentru determinarea arborelui partial minim (Prim, Kruskal). 15. Metode de parcurgere a grafurilor neorientate – descriere si aplicatii. 16. Scrieti un program care sa afiseze toate partitiile lui 32 ca suma de numere naturale impare (nu conteza ordinea termenilor).
Transcript
Page 1: Subiecte (INF)

INFORMATICA (4 ani)

LICENTA 2007

SUBIECTE PROPUSE LA DISCIPLINELE DE INFORMATICĂ

1. Algoritmi si Structuri de Date I

1. Algoritm de generarea a tuturor submultimilor unei multimi – descriere si implementare in Java.

2. Algoritm de simulare a inmultirii numerelor naturale mari – descriere si implementare in Java.

3. Algoritmi recursivi – descriere si implementare in Java (de exemplu, folosind problema acoperirii tablei de sah prin mutari ale calului).

4. Algoritm de generare a combinarilor – descriere si implementare in Java. 5. Algoritm de determinare a tuturor triangulatiilor unui poligon convex – descriere

si implementare in Java. 6. Scrieti un program pentru determinarea tuturor radacinilor rationale ale unei

ecuatii cu coeficienti intregi. 7. Scrieti un program pentru descompunerea unui numar natural ca suma de cat mai

putini termeni din sirul Fibonacci ( 0 1 1 20, 1, , 2k k kF F F F F k− −= = = + ≥ ). 8. Fie 1x si 2x radacinile ecuatiei 2 3 2x x 0− + = si 1

nnS x x2

n= + . Sa se scrie un program care determina numarul divizorilor lui . 50S

9. Scrieti un program pentru determinarea numarului combinarilor de 1234 elemente luate cate 567 (atentie: rezultatul are 369 cifre!).

10. Scrieti un program care sa determine cea mai mica valoare a lui astfel incat n1 21234567 ... nx x x= + + + si { }, ,1kx k k k n∈ − ≤ ≤

2. Algoritmi si Structuri de Date II

11. Metoda “backtracking” – descriere si exemple. 12. Algoritmi eficienti de sortare – descriere si exemple (quicksort, heapsort). 13. Metoda “programare dinamica” – descriere si exemple. 14. Algoritmi pentru determinarea arborelui partial minim (Prim, Kruskal). 15. Metode de parcurgere a grafurilor neorientate – descriere si aplicatii. 16. Scrieti un program care sa afiseze toate partitiile lui 32 ca suma de numere

naturale impare (nu conteza ordinea termenilor).

Page 2: Subiecte (INF)

17. Scrieti un program care sa determine un subsir crescator maximal dintr-un sir de 100 de numere naturale preluat dintr-un fisier text.

18. Se preia dintr-un fisier text o matrice cu 30 linii si 40 coloane. Elementele matricei sunt numai valori 0 sau 1. Scrieti un program care sa determine un “dreptunghi de arie maxima” in aceasta matrice, care sa contina numai elemente nule (dreptunghiul va fi determinat de cele doua linii si cele doua coloane intre care se afla valorile indicilor elementelor care fac parte din acest dreptunghi).

19. Scrieti un program care sa determine componentele conexe ale unui graf neorientat.

20. Scrieti un program care sa determine distanta minima dintre doua noduri ale unui graf neorientat ponderat folosind algoritmul lui Dijkstra.

3. Programarea calculatoarelor

21. Elemente de baza ale programarii in Java. Tipuri de date. Notiunea de variabila.

Metode. Supraincarcarea metodelor. Transferul parametrilor. 22. Recursivitate. Conceptul de recursivitate. Functii matematice recursive.

Implementarea recursivitatii in Java. 23. Structuri statice de date. Tablouri de date uni- si multidimensionale in Java. 24. Structuri dinamice de date: liste, stive, cozi, arbori binari. Implementarea

structurilor dinamice de date in Java. 25. Programarea intrarilor si iesirilor in Java.

26. Un medicament se caracterizeaza prin denumire, compoziţie, indicaţii, contraindicaţii şi mod de administrare. Sa se scrie o clasă Medicament care implementeaza caracteristicile medicamentelor si furnizează metode publice prin care se pot obtine informatii despre un anumit medicament. Informatiile despre medicamente vor fi preluate din fisierul “dateMedicamente.txt” cu urmatorul continut: neo-angin | amilmetacrezol, alcool, levomentol | tratatementul bolilor inflamatorii | copii sub 6 ani | la 2-3 ore famotidină | 20 mg de famotidină | ulcer gastric şi duodenal | hipersensibilitate la substanţa activă | o singură doză/zi flamexin | ciclodextrin, glicolat de sodiu | antiinflamatori, antireumatic | alergie la piroxicam | un comprimat pe zi Sa se foloseasca clasa Medicament, precum si o structura de date (la alegere) pentru a scrie o clasa numita AgendaMedicala care furnizeaza metode ce implementeaza urmatoarele operaţii:

- afisarea denumirii medicamentelor în ordine alfabetică, - cautare după denumirea unui medicament, - afişarea informaţiilor unui anumit medicament, şttindu-se numele acestuia.

Page 3: Subiecte (INF)

27. Un abonat telefonic se caracterizeaza prin nume, prenume, adresa şi numar de telefon. Sa se scrie o clasa Abonat care implementeaza caracteristicile unui abonat si furnizează metode publice prin care se pot obtine informatii despre un anumit abonat. Informatiile despre abonati vor fi preluate din fisierul “date.txt” cu urmatorul continut: Ionescu Pop Aleea rozelor 457789 Popescu Ion Strada Sperantei 789064 Marinescu Marin Strada Stejarului 675643 Sa se foloseasca clasa Abonat, precum si o structura de date (la alegere) pentru a scrie o clasa numita AgendaTelefonica care furnizeaza metode ce implementeaza urmatoarele operaţii: - afisarea abonaţilor în ordine alfabetică după numele acestora, - cautare după numele unui abonat, - cautare după numărul de telefon, - adaugarea unui abonat, - stergere a unui abonat. In plus, clasa AgendaTelefonica are o metoda care descarca elementele structurii de date în fisierul “date.txt” astfel încat acesta să conţină agenda curentă de abonaţi telefonici.

28. Un magazin de jucarii isi stabileste preturile in functie de tipul jucariei: papusi, masinute, jocuri electronice si roboti, ale caror preturi sunt: 1000, 1500, 2000, 3000 lei. Tipurile de jucarii si preturile lor sunt memorate in fisierul “jucarii.txt”. Sa se scrie clasa Jucarie care implementează, cu ajutorul variabilelor, elementele prin care diferentiem un tip de jucarie de celelalte tipuri: descriere tip si pret. Să se scrie un program care, cu ajutorul unei liste sau cozi sa se creeze o lista (coada) de jucării şi sa conţina o metodă care afişează tipurile de jucării în ordine descrescătoare a preţului lor. Această metodă ar trebui să fie apelată, în cazul în care utilizatorul raspunde cu “da” la intrebarea: “Vreti sa vedeti tipurile de jucarii pe care avem in magazin?” Dacă utilizatorul răspunde cu “nu”, atunci programul ar trebui să afişeze următorul mesaj: “Introduceti un tip de jucarie:” impreuna cu toate tipurile de jucării din magazin. Utilizatorul tastează numele unui tip de jucărie şi programul afişează preţul ei.

29. Sa se scrie un program care realizeaza operatiile asupra conturilor ale unei agenţii CEC. Programul actualizeaza conturile existente, adauga conturi noi şi afişarea sumei dintr-un anumit cont. Un cont se caracterizeaza prin numar cont, numele unui depunător şi suma curentă pe care acesta o are în cont. Să se creeze o clasa Cont care implementează informatiile despre conturile dintr-o agenţie CEC şi furnizează metode de accesare a acestor informaţii. Folosind aceasta clasă şi o structură de date oarecare (care doriti) să se scrie o clasă care furnizează metode ce implementează operaţiile ce pot fi executate asupra conturilor dintr-o agenţie CEC:

- crearea unui cont. Pentru aceasta programul are nevoie de numele depunătorului şi suma cu care deschide contul (aceasta trebuie sa fie >=100 000). Cu aceste informatii, programul va crea un cont nou , generând un numar de cont nou, şi-l va adauga la structura de date folosită.

Page 4: Subiecte (INF)

- actualizarea unui cont. Programul are nevoie de numărul contului (a cărui validitate este verificată de program ) şi de suma pe care o adauga sau scoate din suma curentă.

- afişarea sumei pe care o are în cont un anumit depunător. Pentru aceasta, programul are nevoie de numărul contului şi va afişa numele depunătorului şi suma curentă din cont. Dacă numărul de cont este invalid, atunci se va afişa un mesaj de eroare.

30. Evaluarea unor expresii în notatie postfixata. Presupunem că în fişierul “expresii.dat” din directorul curent sunt memorate câteva expresii aritmetice în notatie postfixata, corecte din punct de vedere sintactic. Fiecare expresie aritmetică este memorată pe câte o linie a fişierului şi este formată din numere (cifre) şi operatorii aritmetici: +, -, *, /, div şi mod. Să se scrie un program care citeşte operatorii şi operanzii fiecărei expresii din fişier şi îi introduce într-o lista sau coada. Apoi evaluează expresia respectivă folosind o lista sau stivă (de operanzi) şi implementând următorul algoritm:

- atâta timp cât coada nu este vida: - extrage un element din coadă pe care îl notăm cu E - daca E este operand atunci pune E în stiva - daca E este operator atunci:

- extrage OP2 şi OP1 din stiva - calculeaza R = OP1 E OP2 - pune R în stiva

- scoate elementul din stivă şi îl afişează.

4. Organizarea Sistemelor de Calcul 31. Descrieţi funcţionarea unui microprocesor generic.Specificaţi părţile componente. 32. Organizarea regiştrilor şi a memoriei la microprocesorul Intel8086. 33. Performanţa sistemului de calcul. 34. Transputere. Consideraţii generale şi arhitectură. 35. Arhitecturi multiprocesor. Consideraţii generale. : definiţie, clasificare Flynn,

Enslow, organizare. 36. Calculatoare orientate pe flux de date. 37. Să se scrie un program în limbaj de asamblare care criptează/decriptează prin

translaţie de n un text introdus de la tastatură. 38. Să se scrie un program în limbaj de asamblare care afişează suma a două numere

de maxim două cifre introduse de la tastatură. 39. Să se scrie un program în limbaj de asamblare care afişează produsul a două

numere de maxim două cifre introduse de la tastatură. 40. Să se scrie un program în limbaj de asamblare care afişează pe ecran o figură

geometrică şi o animează.

Page 5: Subiecte (INF)

5. Sisteme de operare 41. Stările proceselor în sistemele cu multiprogramare şi mecanismele, bazate pe

întreruperi, pentru modificarea stării unui proces. 42. Problematica comunicării între procese prin memorie comună şi soluţia de

principiu. 43. Memoria virtuală: definiţie şi modele. Tabela de pagini văzută ca funcţie şi

mecanismul de obţinere a adresei fizice din adresa virtuală. 44. Structurile de date utilizate de sistemul de operare pentru implementarea gestiunii

fişierelor cu index-noduri. 45. Justificaţi necesitatea apelului sistem “open” (deschidere fişier). Cum sunt

utilizate rezultatele produse de executarea sa? 46. Creaţi un fişier de comenzi Linux (script) care se va lansa cu un parametru (nume

reprezentând ID-ul unui utilizator) şi va executa, succesiv, următoarele operaţii: - crearea structurii:

/home/myname DD1 DD2

DD3 DD4 DD5

DD6

- transferul controlului către utilizator pentru a-i permite editarea cu vi a unui text

ce va fi salvat în fisierul exercitiu în directorul DD4, - copierea fişierului exercitiu in DD6, - afişarea listei utilizatorilor conectaţi şi redirectarea ei către fişierul cine din DD3, - căutarea în acest fişier a utilizatorului cu numele dat ca parametru de intrare în

script şi afişarea liniei corespunzătoare acestuia, dacă e conectat, sau afişarea mesajului “ nume neconectat “ dacă nu e conectat.

47. Într-un sistem cu multiprogramare, fie procesele p1, p2 şi p3 care produc ieşiri

sub formă de caractere utilizând rutina “putc”. Ele se sincronizează folosind două semafoare: “L” şi “R”.

semaphore L=3, R=0 /*definire şi iniţializare semafoare*/ /*cod P1*/ /*cod P2*/ /*cod P3*/ L1: L2: L2: DOWN(L); DOWN(R); DOWN(R); putc(‘C’); putc(‘A’); putc(‘D’); UP(R); putc(‘B’); UP(R); goto L1; goto L2; goto L3;

Page 6: Subiecte (INF)

a. Precizaţi numărul de caractere „D” ce vor fi afişate la executarea acestui set de procese. Explicaţi.

b. Demonstraţi că secvenţa de caractere CABABDDCABCABD nu este o ieşire posibilă a acestei execuţii.

48. Într-un sistem cu multiprogramare, fie procesele p1, p2 şi p3 care produc ieşiri

sub formă de caractere utilizând rutina “putc”. Ele se sincronizează folosind două semafoare: “L” şi “R”.

semaphore L=3, R=0 /*definire şi iniţializare semafoare*/ /*cod P1*/ /*cod P2*/ /*cod P3*/ L1: L2: L2: DOWN(L); DOWN(R); DOWN(R); putc(‘C’); putc(‘A’); putc(‘D’); UP(R); putc(‘B’); UP(R); goto L1; goto L2; goto L3;

a. Indicaţi numărul minim de caractere „A” ce se pot afişa. Explicaţi. b. Demonstraţi că secvenţa de caractere CABACDBCABDD este o ieşire posibilă a

acestei execuţii. 49. Fie un sistem de operare ce execută gestiunea memoriei virtuale cu tabele de

pagini pe un singur nivel. Memoria fizică este de 1 Goct. iar adresele în cadrul programelor sunt reprezentate pe 32 biţi (adresarea făcându-se la nivel de octet). Dacă tabela de pagini are 220 intrări, calculaţi dimesiunea paginii şi numărul de biţi pe care este reprezentat numărul cadrului de pagină.

50. Câte operaţii cu discul sunt necesare pentru a aduce în memorie i-nodul fişierului /home/studenti/cursSO/subiecte.txt ? Presupuneţi că i-nodul directorului rădăcină este deja în memorie, dar nimic altceva pe parcursul căii de mai sus nu este adus în memorie. De asemenea, se presupune că fiecare director ocupă doar un bloc de pe disc. Explicaţi.

Page 7: Subiecte (INF)

6. Programare orientata pe obiect

51. Moştenire şi polimorfism. Implementarea in Java a relatiei de generalizare/specializare.

52. Clase abstracte si interfete. Realizarea mostenirii multiple prin folosirea interfetelor.

53. Clase interne. 54. Tratarea evenimentelor de catre componentele grafice AWT. 55. Colectii de obiecte.

56. Sa se scrie un program (applet) care sa ajute un elev sa invete înmulţirea a două numere formate din câte o cifră. Programul ar trebui sa genereze aleator numere intre 0 şi 9, inclusiv şi să afişeze în bara de stare a applet-ului mesaje de genul : “Cat face 6 ori 7?”

Elevul raspunde intr-un câmp de text şi apasă Enter, iar programul verifica raspunsul. Daca este corect, programul alege la intamplare unul din mesajele “Foarte bine!”, “Raspunsul este corect”, “Excelent!”, “Corect”, il afiseaza si apoi generează şi afişează o alta intrebare. Daca raspunsul este gresit, afiseaza unul din raspunsurile generate tot aleator: “Nu. Mai incearca!”, “Gresit. Mai incearca o data”, “Ai gresit, dar nu renunta”, “Nu este rezultatul corect”. Apoi lasa elevul sa raspunda la aceasta intrebare pana cand da raspunsul corect.

In plus, programul ar trebui sa contorizeze raspunsurile corecte si incorecte. Dupa ce elevul a raspuns de 10 ori, programul ar trebui sa calculeze procentul raspunsurilor corecte. Daca acest procent este mai mic de 75, se va afisa mesajul: “Ar trebui sa te meditezi” si se va reseta programul, astfel incat un alt elev sa-l incerce.

57. O companie aeriana foloseste un sistem automat de rezervare a locurilor unui avion. Sa se scrie un program care realizeaza acest lucru pentru un singur avion cu capacitatea de 10 locuri la fiecare zbor. Programul ar trebui sa afiseze urmatorul menu de alternative:

Alegeti 1 pentru sectiunea de Fumatori

Alegeti 2 pentru sectiunea de Nefumatori

Daca persoana alege 1, atunci programul ar trebui sa rezerve un loc in sectiunea fumatori (1..5). Altfel, se alege un loc la nefumatori (locurile 6-10). Apoi programul ar trebui sa afiseze un mesaj cu numarul locului si sectiunea fumatori sau nefumatori a avionului. Rezervarea unui loc ar trebui marcata printr-un 1.

Cand o sectiune este plina, programul ar trebui sa intrebe clientul daca doreste sa i se rezerve un loc la cealalta sectiune. Daca da, se face rezervarea respectiva. Altfel, se afiseaza mesajul “Urmatorul zbor este in 3 ore.” Acelasi mesaj va fi afisat si daca nu mai exista nici un loc liber.

Page 8: Subiecte (INF)

58. Să se scrie un program care afişează într-o arie de text a unei ferestre codul sursă al unei clase Java. Numele clasei este ales dintr-o lista ascunsa (memorata ca elemente ale unei componente grafice Choice sau JComboBox) din directorul curent al programului. Interfata programului este urmatoarea:

Dupa cum se observa, interfata mai contine doua butoane Previous şi Next a căror acţiune determina afişarea unor liste (in niste ferestre de dialog) ce conţin numele claselor ce au fost deschise înaintea, respectiv dupa ce codul clasei curente fost afişat. Aceste liste permit reafişarea continurilor claselor ce au mai fost afişate cel putin o dată.

59. Sa se realizeze un applet care simuleaza jocul: “Ghiceste numarul”. Applet-ul afiseaza mesajul: “Ghiceste un numar intre 1 si 1000” langa un camp de text, iar numarul ar trebui generat aleator intre 1 si 1000. Utilizatorul introduce un numar in campul de text si apasa Enter. Daca valoarea este incorecta, programul ar trebui sa afiseze in bara de stare a applet-ului unul din cele doua mesaje “Numarul introdus este prea mare. Mai incearca” sau “Numarul introdus este prea mic. Mai incearca”, in functie de numarul introdus. Apoi programul ar trebui sa stearga numarul introdus in campul respectiv. Cand utilizatorul a introdus o valoare corecta, se va afisa in bara de stare mesajul: ”Felicitari.Ai ghicit numarul!”. In plus, programul va contoriza incercarile de a ghici ale jucatorului. Daca numarul de incercari este mai mic sau egal cu 10, se va afisa mesajul: “Ori stii secretul, ori esti norocos!”. Daca jucatorul ghiceste numarul in exact 10 incercari, programul afiseaza mesajul: “Stii secretul!”, iar daca l-a ghicit in mai mult de 10 incercari, ar trebui sa afiseze: “Ar fi trebuit sa ghicesti numarul pana acum!”.

60. Proprietarul unei librării a hotărât să cumpere un program de gestiune a vânzării cărţilor ce se află în magazinul său. Toate informaţiile despre o carte: autor, titlu, editura si preţ sunt memorate în fişierul “stoc.txt”. De exemplu, acest fişier contine următoarele informatii:

N. Labiş_Moartea caprioarei_Agora_1986_50000 Tanasa, St. Andrei, Olaru_Java de la 0 la expert_ Polirom_2003_500000 I. Athanasiu et al._Java. O perspectiva pragmatica_Agora_1998_150000 B. Eckel_Thinking in Java_Prentice Hall_1998_1000000

Page 9: Subiecte (INF)

Cand se primesc cărţi in librărie, un angajat al librariei accesează programul şi introduce datele despre fiecare titlu primit cu ajutorul următoarei interfeţe grafice:

Dupa fiecare titlu introdus, angajatul apasă butonul “Adauga carte”. Cand a terminat, apasă butonul “actualizeaza stoc” care permite actualizarea fisierului stoc.txt cu noile date. In plus, programul permite căutarea şi afişarea tuturor cărtilor în ordine alfabetică de la o anumită editură. Pentru aceasta, programul afisează următoarea interfaţă grafică.:

Utilizatorul va introduce in câmpul de text „Editura” numele unei edituri si va apăsa butonul „Cauta”. Se vor afişa intr-o arie de text toate cartile acelei edituri (autor, titlu, preţ).

Page 10: Subiecte (INF)

7. Compilatoare

61. Analiza lexicala. Utilizarea expresiilor regulate pentru descrierea atomilor lexicali.

62. Analiza lexicala. Pasii de proiectare a unui analizor lexical. 63. Analiza sintactica predictiva nerecursiva. Gramatici LL(1). 64. Analiza sintactica LR. Cea mai eficienta metoda de construire a unui analizor LR. 65. Scheme de traducere orientata de sintaxa 66. Sa se scrie o specificatie JLex care rezolva numerele reale, operatorii aritmetici si

relationali, cuvintele cheie: if, else, while, until si parantezele. 67. Presupunem ca avem un limbaj de programare cu urmatoarea gramatica:

S → if E then S else S | begin SL | print E L → end | ; SL E → num = num a) Construiti un analizor predictiv recursiv pentru acest limbaj. b) Implementati in Java analizorul obtinut la pasul anterior.

68. Fie G=(N, Σ, P, S) gramatica numerelor binare zecimale: S → L.L | L L → LB | B B → 0 | 1 a) Calculati valorile functiilor PRIM si URM pentru fiecare neterminal al

gramaticii. b) Construiti tabela de analiza a unui analizor predictiv nerecursiv pentru G si

verificati daca gramatica G este LL(1). 69. Fie G=(N, Σ, P, E) gramatica cu urmatoarele productii:

E → while E do E | id:=E | E+E | id Construiti un analizor LR(1) folosind metoda LALR. Verificati daca G este o gramatica LALR. In caz negativ, eliminati conflictele luand deciziile cele mai bune din punct de vedere semantic. Verificati functionarea analizorului pentru sirul de la intrare while id do id:=id+id. Ce se obtine pe banda de iesire?

70. Sa se construiasca o schema de traducere care realizeaza traducerea expresiilor aritmetice din forma infixata in forma prefixata.

Page 11: Subiecte (INF)

8. Baze de date

71. Definiţia cheilor. Algoritmul de asistenţa proiectării cheilor pentru tipurile de obiecte din MMED şi teorema sa de caracterizare (enunţ şi demonstraţie).

72. Enunţaţi şi demonstraţi teorema principiului propagării cheilor. Daţi un exemplu. 73. Algoritmul pentru traducerea diagramelor E-A în schemele relaţionale

corespunzătoare şi teorema sa de caracterizare (enunţ şi demonstraţie). 74. Enunţaţi şi demonstraţi teorema de caracterizare a funcţiilor structurale. Daţi un

exemplu. 75. Algoritmul pentru traducerea schemelor MMED în schemele relaţionale

corespunzătoare şi teorema sa de caracterizare (enunţ şi demonstraţie). 76. Fie următoarea schemă de relaţie (şi o posibilă instanţă validă a sa):

ÎMPRUMUTURI #Împrumuturi Cărţi Cititori DateÎmprumut DateReturCerut DateReturEfectivautonumber ⊆ #Cărţi ⊆ #Persoane Date Date Date

1 1 1 15/05/2007 30/05/2007 2 2 1 15/05/2007 17/05/2007 20/05/2007

a. Care este numărul maxim teoretic posibil de chei semantice pe care le poate

avea această relaţie? b. Câte are de fapt? c. Care sunt acestea? d. De ce?

77. Fie următoarele 5 funcţii:

Continent : ŢĂRI → CONTINENTE, Ţara : STATE → ŢĂRI, NumeŢara : ŢĂRI ↔ CHAR(32), #Continent : CONTINENTE ↔ NAT(2) şi #Ţara : ŢĂRI ↔ NAT(3)

a. Care dintre ele ar putea şi care ar trebui să fie propagate unde? De ce? b. Care dintre cele propagate sunt injective? De ce? c. Este posibilă propagarea #Continent în STATE? Este acest lucru

recomandabil? De ce? d. Dar propagarea NumeŢara în STATE? De ce?

78. Fie următoarele 6 funcţii:

Ţara : LOCALITĂŢI ŢĂRI →Capitala : ŢĂRI LOCALITĂŢI ↔NumeŢara : ŢĂRI CHAR(32) ↔Populaţie : ŢĂRI→NAT(16) #Localitate : LOCALITĂŢI↔NAT(8) #Ţara : ŢĂRI NAT(3) ↔

Page 12: Subiecte (INF)

a. Există vreo funcţie f : CHAR(32) → NAT(8) care să facă comutativă următoarea diagramă? Câte asemenea funcţii sunt posibile? De ce?

b. Dacă există, în ce circumstanţe ar fi f injectivă ?

79. Fie următoarea diagramă E-A:

COND_ÎNSCRIERI Precondiţie Curs

CURSURI

IDCurs TitluCurs

a. Traduceţi-o în schema MMED corespunzătoare. b. Traduceţi-o în schema relaţională corespunzătoare. Furnizaţi o posibilă instanţă validă având cel puţin două linii pentru fiecare tabelă. c. Ce s-ar întâmpla dacă graful COND_ÎNSCRIERI ar fi ciclic? De ce? Daţi un exemplu şi un contraexemplu.

Page 13: Subiecte (INF)

80. Fie următoarea schemă şi instanţă de bază de date: ÎMPRUMUTURI

#Împrumuturi Cărţi Cititori DateÎmprumut DateReturCerut DateReturEfectivautonumber ⊆ #Cărţi ⊆ #Persoane Date Date Date

1 1 2 15/05/2007 30/05/2007 17/05/2007 2 2 2 15/05/2007 17/05/2007 20/05/2007 3 3 3 17/05/2007 18/05/2007 18/05/2007 4 1 2 25/05/2007 15/06/2007

CĂRŢI #Cărţi TitluCarte PrimAutor

autonumber ASCII(255) ⊆ #Persoane1 Se înnoptează. Se lasă ceaţă. 2 2 Opera poetică completă 1 3 Marea Teoremă a lui Fermat 3

PERSOANE #Persoane Prenume Nume

1 Lucian Blaga 2 Mihai Zamfir 3 Simon Singh

a. Proiectaţi instrucţiunile SQL ce formalizează următoarea întrebare: “Care sunt

cărţile (Titlu, Prenume şi Nume prim autor) care au fost împrumutate de cel puţin n persoane între dataÎnceput şi dataSfârşit, cu condiţia ca cel puţin un cititor să fi împrumutat fiecare asemenea carte de cel puţin două ori în perioada de timp dată?”

b. Fie n = 1, dataÎnceput = 15/05/2007 şi dataSfârşit = 30/05/2007; calculaţi răspunsul la întrebarea de mai sus pentru instanţa propusă.

9. Programarea Concuretă şi Distribuită

81. Calculul paralel, calculul concurent, calculul distribuit: defiiţii, relaţii între ei. 82. Modele şi metrici pentru evaluarea performaţelor algoritmilor concureţi. Legea lui

Amdahl 83. Situaţii de excepţie generate de concurenţă: descriere, condiţii necesare sau

suficiente de apariţie. 84. Analiya dependenţelor. Condiţiile lui Bernstein. Exemple. 85. Tehnologia RMI: relaţia RMI cu RPC, schema de funcţionare, etapele pe care le

include. 86. Problema Consumatorilor şi Producătorilor. Formulare. Soluţionare (în Java). 87. Problema filozofilor chinezi. Formulare. Soluţionare (în Java). 88. Problema Cititorilor şi Scriitorilor. Soluţionare (în Java). 89. Adunarea concurentă a N numere. Soluţionare (în Java). 90. Problema Cititorilor şi Scriitorilor. Soluţionare folosind pipe-urile (în Java).

Page 14: Subiecte (INF)

10. Reţele de calculatoare

91. Rutare dinamica: Algoritmul Dijkstra – pseudocod + exemplificare numerica

92. Rutare dinamica: Algoritmul Bellman-Ford - pseudocod + exemplificare numerica

93. Nivelul legǎtura de date: protocoalele Ethernet - IEEE 802.3; 94. Subalocarea unei adrese de retea date (Subnetting) : algoritm si exemplificare

95. Utilizarea mastilor de retea de lungime variabila (VLSM) : algoritm si

exemplificare

96. Aplicatie subnetting:

O nouă reţea este proiectată pentru companie. Folosind un IP de reţea de

Clasă C, ce mască de subreţea va pune la dispoziţie câte o subreţea utilizabilă pentru fiecare departament, în timp ce se permit suficiente adrese de host utilizabile pentru fiecare department specificat în figură? Sa se scrie adresele IP pentru toate gazdele din figura, organizate pe departamente, specificand totodata adresele de subretea si de broadcast pentru fiecare departament.

97. Considerând reteaua din figura, în care etichetele reprezenta distanta, se cere determinarea tabelei de rutare pentru nodurile 1 si 4, folosind algoritmul Dijkstra

Page 15: Subiecte (INF)

98. Considerând reteaua din figura, în care etichetele reprezenta distanta, se cere

determinarea tabela de rute completa, folosind algoritmul Bellman Ford

99. Comunicare TCP la client – Aplicatie Java 100. Comunicare TCP la server - Aplicatie Java

Page 16: Subiecte (INF)

11.Complexitatea algoritmilor

101.Prezentati algortimul de parsare CYK pentru gramaticile independente de context. Determinaţi complexitatea de timp dacă gramatica independentă de context de intrare este în forma normală Chomsky. Exemplificati pe gramatica unde S), P, b}, {a, C},B,A, ({S, G = P este

a |BA A → b | CC B→ a | AB C →

şi cuvăntul de intrare este w = baaba. 102.Demonstraţi existenţa unor limbaje ce nu sunt recursiv enumerabile. 103.Demonstraţi că problema opririi pentru maşina Turing este nedecidabilă. 104.(Teorema de accelerare liniară) Demonstraţi că pentru orice maşină Turing

M cu benzi, ce acceptă limbajul L astfel încă se poate construi o maşină Turing N cu k benzi echivalentă astfel încât

, pentru orice constantă c>0.

k 1>k f(n))(ctM =n

32n[cf(n)] ++≤Nct105.Demonstraţi că dacă M este o maşină Turing cu două benzi astfel încât

atunci, , unde c depinde de n, de f(n), de numărul de simboluri ale benzii lui M şi de numărul de stări ale lui M.

f(n)csM = )()( nfM cnct ≤

106.Răspundeţi şi argumentaţi: a) ? O(n))(logn 2 =nb) ? )2(3 nn O=c) ? 1),(2 ≥≠ rnO rn

d) ? )1010(10 22 ++=−− nnOnn

107.Demonstraţi că limbajul nu este acceptat de nici un automat finit. Construiţi şi comentaţi maşina Turing deterministă standard ce acceptă acest limbaj.

}*},{|{ bawwwL R ∈=

108.Construiţi o maşină Turing ce calculează funcţia Comentaţi construcţia.

1,2 ≥nn

109.Construiţi o masină Turing cu k>1 benzi ce acceptă limbajul . Comentaţi construcţia şi calculaţi complexitatea de

spaţiu. }1|010{ ≥= nL nnn

110.Construiţi o maşină Turing deterministă care reduce limbajul la în timp polinomial. Comentaţi

construcţia şi stabiliţi complexitatea de timp a maşinii care calculează reducerea.

}0|)({1 ≥= ibbaL ii }0|{2 ≥= ibaL ii

Page 17: Subiecte (INF)

12. Inteligenţă artificială

111.Algoritmii genetici: schema generală, exemplu de utilizare. 112.Logica predicatelor: algoritmul metodei rezoluţiilor, exemple. 113.Metode de căutare sistematică: căutarea în adâncime, căutarea în lăţime,

algoritmul A*. Descrierea algoritmilor şi compararea complexităţii lor de timp şi de spaţiu.

114.Reţelele neuronale: tipuri de reţele conform topologiei lor. Perceptronul: regulile de instruire a perceptronului. Exemplu.

115.Managementul informaţiei inexacte: utilizarea schemei Bayes. Exemplu. 116.Se consideră următoarele afirmaţii: A) Coconut is a bicuit. B) Mary is a child

who takes coconut. C) John loves children who takes coconut. D) John loves Mary. Este oare adevărată afirmaţia D), dacă presupunem că afirmaţiile A), B) şi C) sunt adevărate.

117.Scrieţi şi justificaţi un program în Prolog, care ar determina dacă un element aparţine unei liste.

118.Considerăm spaţiul ipotezelor şi spaţiul evidenţelor în cazul unui sistem medical de diagnoză. Regulile, care reprezintă relaţia dintre spaţiul de evidenţe şi spaţiul ipotezelor, sunt definite de probabilităţi condiţionate. Să se determine de ce boală suferă probabil pacientul. Spaţiul ipotezelor este determinat de: tif (T) – 0.2, febră germană (GM) – 0.3, gripă aviară (CP) – 0.5. Spaţiul evidenţelor este: oboseală (F), guturai (R), dureri de muşchi (HBA). Setul de reguli este: Regula 1: dacă simptomele indică F (cu probabilitatea 0.9) şi HBA (cu probabilitatea 0.6), atunci pacientul suferă de T. Regula 2: Dacă simptomele sunt F (cu probabilitatea 0.8), R (cu probabilitatea 0.7) şi HBA (cu probabilitatea 0.8), atunci pacientul are GM. Regula 3: Dacă simptomele sunt F (cu probabilitatea 0.6), R (cu probabilitatea 0.9) şi HBA (cu probabilitatea 0.8), atunci pacientul are CP.

119.O bază de date, care este folosită pentru reprezentarea cunoştinţelor despre cărţi, librării, şi edituri este dată şi este descrisă de fapte de tipul:

sell(Store,Publisher). /*librăria Store vinde cărţi de

la editura Publisher*/ book(Title,Publisher). /*Cartea Title este publicată de

editura Publisher*/ opened(Store). /*Librăria Store este deschisă*/ closed(Store). /*Librăria Store este închisă*/

Să se scrie interogările pentru a obţine răspunsul la următoarele tipuri de înbtrebări:

- Cine a publicat cartea „Mara”? - Care librărie vinde cărţi de la editura „Nemira”?

Scrieţi un program valid în Prolog pentru a justifica răspunsurile la întrebări. 120.Scrieţi şi justificaţi programe Prolog pentru operaţiile cu mulţimi: reuniunea,

intersecţia.

Page 18: Subiecte (INF)

13. Metode avansate de programare

121.Notiunea de clasa. Elemente structurale. Grade de acces. 122.Derivarea claselor. Derivarea simpla. Derivarea multipla. 123.Prezentati notiunea de "polimorfism" in contextul unei ierarhii ce contine o

clasa de baza si doua clase derivate. 124.Clase abstracte. 125.Redefinirea operatorilor. Principii si exemple pe tipuri de operatori. 126.Implementati clasa asociata tipului abstract de date numere Complexe care sa

permita memorarea unui numar complex, determinarea modulului acestuia precum si compararea a doua numere complexe in functie de modulul acestora. Metoda de comparare va avea urmatoarea semnatura: int compara(Complex &z1, Complex &z2);

127.Implementati clasa asociata tipului abstract de date Vector care sa permita memorarea unui vector de n numere reale. Implementati operatorii corespunzatori operatiilor de adunare a doi vectori si inmultire a unui vector cu un scalar.

128.Implementati clasa asociata tipului abstract de date Matrice care sa permita memorarea unei matrici patratice de nxm numere reale (memorarea elementelor se face pe linii). Implementati operatorii corespunzatori operatiilor de adunare si inmultire a doua matrici.

129.Implementati clasa asociata tipului abstract de date ArboreBinar. Implementati si exemplificati metoda de parcurgere inordine.

130.Implementati clasa asociata tipului abstract de date ArboreBinar. Implementati si exemplificati metoda de parcurgere preordine.

14. Programarea in Web

131.Noţiunea de sesiune şi gestiunea ei în tehnologiile ASP, PHP şi JSP/Servlet. 132.Identificarea în Java scripting la client, în ASP, în PHP şi în JSP/Servlet a

câmpurilor din formele HTML. 133.Resursă, identificator, reprezentare: definiţii şi relaţii. 134.Ciclul de viaţă al unui servlet. Explicaţii. 135.Modelul DOM-HTML. 136.Caracteristicile specifice clasei HttpServlet. Daţi un exemplu de utilizare care

să conţină atât pagina HTML din care se va genera cererea cu metoda POST cât şi codul servlet-ului ce constituie resursa accesată.

137.Caracteristicile limbajului XPath. Descrieţi rezultatul expresiei : ”//item[@type=’facultate’]/curs[text()=’Programare’]”.

138.Creaţi un document de tip XMLSchema specificând şi spaţiul de nume pentru elementele definite în acesta. Tipul de document definit cu această schemă XML conţine un element de tip şir de caractere şi un element de tip complex. Tipul complex are 2 atribute şi 2 subelemente. Unul dintre subelemente este obligatoriu şi poate să apară o singură data, cel de al doilea poate să apară, de asemenea, o singură dată dar nu este obligatoriu. Unul dintre atribute este

Page 19: Subiecte (INF)

obligatoriu, iar celălalt este opţional. Daţi un exemplu de document instanţă a tipului definit cu schema XML de mai sus.

139.Creaţi o pagină Web cu două frame-uri. Într-un frame sunt afişate trei butoane cu numele a trei cursuri. Când se solicită, prin apăsare pe buton, un curs textul acestuia apare în al doilea frame, cu condiţia ca solicitarea să fie făcută în ziua din săptămână şi între orele în care se ţine cursul.

140.Exemplificaţi pe un cod simplu, într-un limbaj de programare la server ales de voi, etapele accesului standard la o bază de date.

15. Ingineria programarii

141.Modelul de dezvoltare a software-ului Rational Unified Process. 142.Modelare business. Diagrame de activitati ale cazurilor de utilizare business. 143.Proiectarea arhitecturilor software. Aplicarea modelelor generale de

proiectare in stabilirea responsabilitatilor claselor. 144.Proiectarea cazurilor de test. 145.Conducerea proiectelor software. Construirea diagramei retea a unui proiect

software. 146.Fie cazul unui sistem software de gestiune a magaziei de marfuri a unui

magazin de cafea. In acest magazin se vând doua tipuri de cafea: boabe si macinata, ambalata in pachete. Aceste pachete se primesc in loturi de la firmele furnizoare. Pentru fiecare lot primit in magazin, sistemul va memora data primirii si numarul de kilograme ale lotului si ii va asocia un numar de identificare ce va fi unic pentru fiecare lot in parte. De asemenea, sistemul va calcula pretul de vanzare a pachetelor din lot, in functie de pretul unitar primit de la furnizor la care se adauga tva-ul. Valoarea tva-ului poate diferi de la un lot la altul, dar este aceeasi pentru toate pachetele ce apartin unui acelasi lot. In plus, sistemul va calcula data de expirare a pachetelor dintr-un anumit lot, stiind ca orice pachet de cafea are termen de valabilitate 2 ani. Dupa aceea, sistemul va adauga lotul la stocul existent in magazin. Vinderea pachetelor de cafea determina actualizarea stocului din magazin, operatie ce va fi bineinteles memorata de catre sistem. La intervale regulate de timp, sistemul genereaza rapoarte ce contin urmatoarele informatii:

- data curenta (data la care a fost generat raportul), - cantitatea disponibila in stoc, exprimata in numarul de pachete aflate in

momentul generarii raportului in stoc, - data expirarii fiecarui lot de pachete de cafea din stoc.

Pentru sistemul descris se cere:

a) Identificarea conceptelor domeniului problemei ale acestui sistem impreuna cu atributele lor principale.

b) Construirea modelului domeniului.

Page 20: Subiecte (INF)

c) Construirea unei diagrame de interactiuni (adica o diagrama de secvente sau de colaborare, la alegere) pentru operatia de sistem de calculare a pretului de vanzare a pachetelor de cafea dintr-un lot.

d) Construirea o diagrama de tranzitii de stari pentru obiectele clasei Stoc.

147.Se considera un sistem de plata a angajatilor unei firme de software. Astfel, acestia vor fi platiti dupa numarul de ore lucrate in cadrul firmei. Sistemul este format dintr-un numar de terminale care inregistreaza numarul de ore lucrate de un angajat in fiecare zi.

Asadar, una din functiile principale ale sistemului este sa memoreze timpii in care angajatii se prezinta la firma, merg in pauza, reiau lucrul dupa pauza si pleaca de la firma (dupa cum se observa, programul de lucru al unei zile contine o pauza, dar, daca doreste, un angajat poate sa nu beneficieze de aceasta). Pentru aceasta, fiecare angajat are o legitimatie cu care se identifica la un terminal al sistemului si pe care o introduce intr-o fanta a terminalului respectiv. Dupa ce angajatul executa aceasta operatie, sistemul il verifica, cautandu-l intr-o baza de date si asteapta apoi ca acesta sa aleaga tipul de activitate pe care urmeaza s-o faca, afisand o interfata ca in figura urmatoare: Apoi, terminalul inregistreaza momentul evenimentului si afiseaza ora exacta ind

icand ca este gata sa inregistreze urmatorul angajat. Se cere: a) Sa se construieasca mdoelul de robustete Jacobson al obiectelor ce

colaboreaza in cazul de utilizare a carui functionalitate este descrisa mai sus. b) Sa se proiecteze o diagrama de interactiuni pentru cazul in care un angajat se

inregistreaza la inceputul unei zile de lucru. c) Sa se construiasca modelul static rezumat cazul de utilizare descris mai sus. 148.Se considera un sistem de rezervari a biletelor la spectacole de teatru.

Rezervarile nu se fac direct la casa de bilete, ci prin intermediul unor masini specializate in acest tip de operatie. Un spectacol este identificat prin nume, dar acelasi spectacol se joaca pe o perioada de timp si maxim de doua ori in aceeasi zi. Pentru fiecare client, sistemul memoreaza numele si numarul de telefon al acestuia, pentru a-i confirma rezervarea facuta. Clientii pot avea mai multe rezervari, dar fiecare rezervare este facuta de un singur client. Rezervarile sunt de doua tipuri: serie de rezervari si rezervare individuala. Ambele presupun furnizarea de bilete, numai ca, in primul caz, este furnizat un abonament, iar in al doilea caz, un singur bilet. La fiecare spectacol sunt disponibile un numar nedeterminat de bilete, fiecare avand un loc unic.

Page 21: Subiecte (INF)

a) Sa se construiasca documentul de cerinte al sistemului. b) Sa se construiasca modelul domeniului al acestui sistem.

149. Sa consideram sistemul informatic al unei agentii de inchirieri de masini. Agentia stipuleaza contracte cu clientii privind inchirierea unei masini de un anumit tip (marca) si cu un anumit echipament instalat, prevazut din fabrica de marca respectiva (de exemplu, pachetul optional continand airbag-uri pentru toti calatorii, ferestre automate etc.). Contractele se pot incheia de client la fata locului sau se pot face rezervari in prealabil prin posta, telefon sau fax. Clientul are la dispozitie tarifele de inchiriere ale agentiei, iar rezervarea sau contractul va indica tariful ales de client. Rezervarile pot diferi de contracte. Poate diferi de exemplu perioada: clientul poate restitui masina mai devreme sau mai tarziu decat a rezervat-o. De asemenea, pentru ca la prezentarea clientului in agentie, agentia nu mai are disponibil un vehicol de tipul rezervat, contractul poate specifica un vehicol mai bun decat cel rezervat, dar la acelasi pret. La rezervare se face atat o verificare a datelor clientului, cat si a vehicolelor disponibile. Clientul poate fi unul cunoscut sau unul nou in care caz i se vor cere datele pentru a fi inregistrat. In cazul ca nu este disponibil vehicolul cu toate accesoriile cerute de client, i se cere acestuia sa specifice o alta optiune. In contract sunt prevazuti unul sau mai multi soferi. Titularul contractului nu trebuie neaparat sa fie printre ei. La momentul predarii masinii de catre agentie clientului se stipuleaza un act de predare, aditional la contract, continand starea masinii (eventuale deteriorari, kilometrajul la bord etc.) si data curenta. De asemenea se verifica carnetele de conducere ale soferilor care trebuie sa corespunda cu informatiile din actul aditional.Un act asemanator, dar de restituire, va fi intocmit la restituirea vehicolului. Si el constituie un act aditional la contract. Daca in timpul folosirii masinii, clientul a suferit/provocat unul sau mai multe accidente, actele privind aceste accidente se anexeaza actului de restituire a vehicolului. In fine, la predare se face calculul contractarea vehicolului si se emite una sau mai multe facturi (pentru timpul prevazut de inchiriere, pentru timpul suplimentar, pentru eventualele daune etc.) conform informatiilor prevazute in contract si actele aditionale. Pentru sistemul de inchiriere de vehicole descris mai sus se cere:

a) Construiti modelul conceptual al sistemului. b) Construiti diagrama de activitati a cazului de utilizare “Rezervare vehicol” cu

mentionarea obiectelor business implicate. c) Construiti o diagrama de secvente sau de colaborare pentru operatia de

rezervare: rezervare_vehicol(cod_client, tarif, marca_masina, tip_pachet_accesorii, lista_ accesorii_speciale, data, nr_zile)

150. Sa consideram un sistem de transmitere a mesajelor ce are la baza modelul expeditor-destinatar, model dat ca exemplu clasic in modelarea sistemelor concurente. Acest model presupune existenta a cel putin un expeditor care trimite spre un destinatar mesaje, unul cate unul, folosind un buffer (locatie temporara) pentru depozitarea lor. Presupunem ca suntem in cazul unui expeditor si a unui

Page 22: Subiecte (INF)

destinatar, care sunt de fapt subsisteme ale sistemului nostru. In timpul functionarii sistemului, expeditorul trece prin urmatoarele stari: - este pregatit pentru o noua transmisie, - a transmis un mesaj, - este in stare de repaus.

La randul său, destinatarul trece prin urmatoarele stari: - a receptionat un mesaj, - este pregatit pentru receptionarea altui mesaj,

- este in stare de repaus. Presupunem ca buffer-ul are o dimensiune limitata n≥1. Atunci expeditorul nu poate trimite nici un mesaj atat timp cat buffer-ul este plin, iar destinatarul nu poate primi nici un mesaj cat timp buffer-ul este vid. De aceea, in cazul ca intentioneaza sa faca o expeditie/receptie, expeditorul/destinatarul trebuie mai intai sa verifice daca buffer-ul este plin/gol si in caz negativ executa operatia, iar in caz afirmativ trece in asteptare. a) Construiti documentul de cerinte a sistemului. b) Construiti o diagrama de interactiuni (de secvente sau de colaborare) ce arata

colaborarea obiectelor in cazul scenariului de transmitere a primului mesaj de la expeditor la destinatar (adica, buffer-ul este vid inainte de a se face trimiterea).

c) Construiti diagrama completa de clase a aplicatiei. d) Construiti statechart-ul (masina de stari) pentru clasa Buffer.

16. Analiza şi Proiectarea Sistemelor Informatice

151. Procese software (Definiţie, activităti, modele) 152. Analiza şi proiectarea orientate spre obiecte a sistemelor (OOAD). Caracteristici generale. 153. OOAD. Analiza cerinţelor 154. UML. Modelare dinamică 155. UML Modelare statica 156. Şabloane de proiectare. Consideraţii generale şi clasificare. 157. Implementaţi clasa Logger care îndeplineşte funcţia de jurnal în cadrul unei aplicaţii mai mari. Obiecte Logger vor fi folosite de celelalte clase ale aplicaţiei pentru a menţine un jurnal cu operaţiile efectuate de acestea. La instanţierea unui obiect Logger, acesta deschide fişierul "lastrun.log" pentru scrierea mesajelor trimise către jurnal. Un client poate trimite mesaje în jurnal folosind metoda void write(String message). Trebuie să aveţi grijă ca în timpul unei rulări să existe o singură instanţă Logger, altfel conţinutul fişierului lastrun.log va fi invalid sau incomplet. Ce şablon de proiectare consideraţi adecvat în acest caz? Realizaţi diagrama de clase UML şi implementaţi clasa Logger. 158. În limbajul Java, clasa java.io.RandomAccessFile nu poate fi folosită în ierarhiile java.io.InputStream, java.io.OutputStream, java.io.Writer şi java.io.Reader deoarece nu este compatibile cu acestea. Găsiţi o modalitate care să permită obiectelor RandomAccessFile să fie folosite cu aceste ierarhii. Ce şablon de proiectare consideraţi adecvat în acest caz? Realizaţi diagrama de clase UML şi implementaţi clasele necesare.

Page 23: Subiecte (INF)

159. Implementaţi un modul pentru validarea unor informaţii folosind sume de control CRC32, Adler32, paritatea (folosind operaţii XOR) şi/sau alte metode. Iniţial, validarea se realizează asupra unui vector de octeţi, dar se prevede extinderea pe viitor a acestei facilităţi şi pentru fişiere, informaţii preluate din reţea, etc. fără a modifica codul iniţial (presupunem că acesta s-a pierdut sau că după compilare clientul primeşte doar codul executabil). Ce şablon de proiectare consideraţi adecvat pentru a permite evoluţia independentă a interfeţei şi funcţionalităţii modulului? Realizaţi diagrama de clase UML şi implementaţi clasele necesare. 160. Implementaţi o aplicaţie pentru desenarea formelor geometrice simple (minim necesar: puncte, linii, elipse şi dreptunghiuri). Aplicaţia trebuie să permită următoarele operaţii:

• crearea de forme geometrice (în funcţie de preferinţa utilizatorului) • gruparea anumitor forme geometrice pentru a fi modificate impreuna • modificarea culorii unei forme sau grup de forme • deplasarea unei forme sau grup de forme

Aplicaţia primeste comenzi pentru construirea imaginii finale. Comenzile pot fi: • nume = punct(x, y) - creaza un punct cu pozitia x, y si numele nume • nume = linie(x, y, w, h) - creeaza o linie cu pozitia x, y, lungime w pe axa Ox, lungime h pe axa Oy si numele nume • nume = elipsa(x, y, w, h) - creeaza o elipsa cu pozitia x, y, lungime w pe axa Ox, lungime h pe axa Oy si numele nume • nume = dreptunghi(x, y, w, h) - creeaza un drepunghi cu pozitia x, y, lungime w pe axa Ox, lungime h pe axa Oy si numele nume • nume = grup(nume1, nume2, ...) - creeaza un grup cu numele nume compus din obiectele nume1, nume2, ... • color(nume, val) - seteaza pentru obiectul nume culoarea val

• move(nume, x, y) - muta obiectul nume cu x pixeli la dreapta si y pixeli in jos (x si y pot fi negative) Ce şablon de proiectare consideraţi adecvat pentru implementarea operaţilor pe forme şi grupuri de forme? Realizaţi diagrama de clase UML

17. Algebra liniara si geometrie analitica I 161. Spaţiu vectorial: definiţie, exemple, reguli de calcul într-un spaţiu vectorial.

162. Fie V un spaţiu vectorial peste corpul K şi , două subspaţii în V. 1W 2W

- Definiţi intersecţia subspaţiilor şi . 1W 2W- Demonstraţi că este subspaţiu V. 21 WW ∩

163. Fie V un K spaţiu vectorial, fixat. Fie *Nq∈ },...,{ 1 qvvS = cu un

sistem de q vectori arbitrar aleşi din V şi Vvv q ∈},...,{ 1

},...,,,...|{ 212211 KvvvVvS qqq ∈+++∈>=< αααααα -<S> este subspaţiu vectorial al lui V; - . >⊂< SS

Page 24: Subiecte (INF)

164. Fie V un K- spaţiu vectorial finit generat, },...,{ 1 nvvB = o bazş în V şi . Demonstraţi că există şi sunt unici scalarii

Vv∈Vn ∈ααα ,...,, 21 astfel încât

....| 2211 nnvvvv ααα +++=

165. Fie V şi W două K-spaţii vectoriale finit dimensionale. Demonstraţi că dacş şi numai dacă V=W.

WV ≅

166. a) Să se determine valorile parametrului real m pentru care

B={(m,1,1),(1,m,1),(1,1,m+1)} este o bază în 3R .

b) Pentru m=2 verificaţi dacă B este o bază şi în caz afirmativ determinaţi coordonatele vectorului v=(-1,3,-4) in baza B.

c) Verificaţi dacă vectorul w=(2,-5,-1) aparţine subspaţiului generat de vectorii =(2,1,1) şi =(1,2,1). 1v 2v

167. Fie W mulţimea soluţiilor sistemului

⎩⎨⎧

=+−=−+

035032

321

321

xxxxxx

a. Arătaţi că W este un subspaţiu vectorial al lui 3R . b.Determinaţi o bazş a lui W. c. Precizaţi . VRdim

168. Fie , 33: RRf →).22,4,4(),,( 321212321 xxxxxxxxxf −−−−=

a.Demonstraţi că f este morfism de spaţii vectoriale. b. Determinaţi , unde $B$ este baza canonică a lui )( fM B

3R . c.Fie Verificaţi că B' este bază în )}1,1,0(),1,0,1(),0,1,1({ 321

' ==== vvvB 3R şi determinaţi matricea a lui f relativ la baza B'. )(' fM B

169. Se dă funcţia , 32: RRf →.),(),,,(),( 2

21221121 Rxxxxxxxxf ∈∀−= a. Arătaţi că f este morfism de spaţii vectoriale. b. Calculaţi Ker (f) şi Im(f). c.Precizaţi rangul şi defectul morfismului f.

170. Se dă matricea

).(2321

2 RMA ∈⎟⎟⎠

⎞⎜⎜⎝

⎛=

a. Scrieţi polinomul caracteristic asociat matricii A.

Page 25: Subiecte (INF)

b. Determinaţi valorile proprii, subspaţiile proprii şi vectorii proprii corespunzători fiecărei valori proprii. c. Calculaţi multiplicitştile algebrice şi geometrice corespunzătoare fiecărei valori proprii. d. Există o bază a lui 2R faţă de care matricea A să aibe forma diagonală? Justificaţi răspunsul.

18. Combinatorica si Teoria Grafurilor

171. Definiti notiunile de: a) Drum si lant intr-un graf orientat; b) Subgraful generat de o submultime de varfuri, XA ⊂ , al unui graf G = (X,

U); c) Graful partial al unui graf G = (X, U) generat de o submultime de arce

; UV ⊂d) Componente tare conexe si componente conexe ale unui graf. e) Matrice de adiacenta, matricea drumurilor si matricea distantelor directe

pentru un graf orientat. 172. Descrieti si demonstrati algoritmul Roy – Warshall, de determinare a matricei

drumurilor intr-un graf. 173. Descrieti si demonstrati algoritmul Roy – Floyd, de determinare a drumurilor si

distantelor minime intr-un graf. 174. Definiti oretea de transport, enuntati Teorema Ford-Fulkerson, definind toate

notiunile care apar in enunt si descrieti algoritmul Ford – Fulkerson. 175. Descrieti algoritmii lui Kruskal si Prim de determinare a arborelui minim pentru

un graf conex. 176. Sa se determine matricea drumurilor si componentele tare conexe pentru graful

care are matricea de adiacenta:

:= a

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

0 1 1 0 1 0 0 00 0 0 0 1 1 1 01 1 0 1 0 0 1 01 1 0 0 1 1 0 00 0 0 0 0 1 1 00 0 0 0 0 0 1 10 0 0 0 0 0 0 00 0 0 0 1 1 1 0

Page 26: Subiecte (INF)

177. Pentru ca o persoana ce are locuinta in punctul 1 sa mearga la biblioteca aflata in punctul El poate folosi mai multe mijloace de transport . Datele cuprinzand punctele intermediare prin care trece precum si timpul mediu calculat pentru a ajunge ditr-un punct in altul sun date in matricea distantelor directe data mai jos. Se cere sa se determine toate drumurile care realizeaza timpul minim cat si valoarea acestuia.

:= a

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

0 1 4 ∞ ∞ ∞∞ 0 2 5 8 ∞∞ ∞ 0 2 5 ∞∞ ∞ ∞ 0 3 5∞ ∞ ∞ ∞ 0 1∞ ∞ ∞ ∞ ∞ 0

178. Sa se determine lungimea maxima si toate drumurile pe care se realizeaza aceasta pentru graful care are matricea distantelor directe:

:= a

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

0 1 3 5 ∞ ∞ ∞ ∞∞ 0 2 ∞ ∞ ∞ 13 ∞∞ ∞ 0 ∞ 5 11 14 ∞∞ ∞ 2 0 6 8 ∞ 15∞ ∞ ∞ ∞ 0 3 ∞ 9∞ ∞ ∞ ∞ ∞ 0 2 6∞ ∞ ∞ ∞ ∞ ∞ 0 4∞ ∞ ∞ ∞ ∞ ∞ ∞ 0

179. In portul 1 se gasesc 35 vapoare care trbuie sa se deplaseze in portul 10.

Deplasarea lor se face in etape astfel incat in prima etapa sa ajunga cat mai multe dintre ele in portul 10. In drumul lor vapoarele trebuie sa mai faca cate o escala in alte porturi intermediare, notate 2,3,...,9. Conditiile de primire, aprovizionare etc. Fac sa existe o limitare a rutelor folosite. Capacitatile corespunzatoare sunt date in matricea de mai jos:

:= a

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

0 12 3 20 ∞ ∞ ∞ ∞ ∞ ∞∞ 0 ∞ ∞ ∞ 6 5 ∞ ∞ ∞∞ ∞ 0 ∞ 4 4 ∞ ∞ ∞ ∞∞ ∞ ∞ 0 5 ∞ ∞ ∞ 10 ∞∞ ∞ ∞ ∞ 0 ∞ ∞ 5 3 ∞∞ ∞ ∞ ∞ ∞ 0 3 3 ∞ ∞∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ 13∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ 10∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 12∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0

Page 27: Subiecte (INF)

Pozitiile notate cu infinit indica aici ca nu avem arc intre varfurile respective. 180. Sa se determine arborele minim pentru graful care are matricea distantelor directe:

:= a

⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢

⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥

0 6 4 11 5 10 9 136 0 4 5 7 5 8 104 4 0 6 3 3 4 6

11 5 6 0 9 2 7 65 7 3 9 0 12 2 3

10 5 3 2 12 0 11 79 8 4 7 2 11 0 3

13 10 6 6 3 7 3 0

19. Ecuaţii diferenţiale

181. Ecuaţii diferenţiale cu variabile separabile.

182. Sisteme diferenţiale liniare de ordinul I cu coeficienţi constanţi. 183. Teorema de existenţă şi unicitate a lui Picard. 184. Teorema de caracterizare a soluţiilor saturate la dreapta. 185. Stabilitatea sistemelor diferen\c tiale. Teorema Poincar\'e-Liapunov. 186. Găsiţi soluţia următoarei ecuaţii diferenţiale reductibile la o ecuaţie omogenă:

522'

−+−

=yx

yxy .

187. Găsiţi un factor integrant astfel încât următoarea ecuaţie să devină o ecuaţie cu

diferenţială totală exactă: ,0))sin()cos(())cos()sin(( =−++ dxxxxtdtxxxt

şi apoi rezolvaţi această ecuaţie. 188. Găsiţi soluţia generală a următoarei ecuaţii:

.5cos107 2''' ttexxx t−=++ 189. Să se arate că problema Cauchy

⎩⎨⎧

=≥−=

;1)0(0,4'

yxyxy

admite soluţie unică definită pe ).,0[ ∞ 190. Studiaţi stabilitatea soluţiei banale pentru următorul sistem:

Page 28: Subiecte (INF)

⎪⎩

⎪⎨⎧

−−=

+−=

.23'

2'

yxyyxx

20. Cercetări Operaţionale

191. Caracteristicile modelului de aşteptare cu o staţie de servire, sosiri Poisson şi timp de servire exponenţial in cazul staţionar.

192. Jocuri matriceale. Strategii minmax şi maxmin. Extensia aleatoare a jocului. 193. Condiţiile de optimalitate Kuhn-Tucker in programarea neliniară . 194. Metoda direcţiilor admisibile pentru programarea convexă cu restricţii liniare:

testul de optimalitate si îmbunătăţirea soluţiei. 195. Metode de punct interior. Algoritmul de scalare afină pentru o problemă de

programare liniară. 196. Se consideră problema de programare neliniară:

cu restricţiile: ⎪⎩

⎪⎨

≥+≤−+

001

),(

21

221

21

xxxx

xxMax

a) Să se scrie funcţia Lagrange asociată; b) Să se scrie condiţiile de optimalitate Kuhn-Tucker; c) Să se calculeze soluţia optimă. 197. Să se rezolve cu metoda multiplicatorilor lui Lagrange:

⎪⎩

⎪⎨

=+−=−+

−+−+−

3322

)5.12433(

321

321

2332

2221

21

xxxxxx

xxxxxxxMax

198. Să se determine punctele de extrem ale funcţiei f(x,y)= x3+y3+3xy 199. Să se rezolve: )312( 21

32

31 xxxxInf −−+

cu restricţiile:

⎩⎨⎧

≥+≥

.01

1

12

xxx

200. Se consideră un fenomen de aşteptare în care sosirile sunt poissoniene iar

serviciile sunt exponenţiale. Durata medie dintre două sosiri consecutive este de 2 minute. Numărul mediu de serviri este de 4 pe minut. Să se determine numărul

Page 29: Subiecte (INF)

mediu de clienţi aflaţi in sistem, numărul mediu de clienţi din firul de aşteptare, durata medie de aşteptare in firul de aşteptare tf , durata medie de aşteptare in sistem ts , probabilitatea ca numărul clienţilor din sistem să nu depăşească 3 şi probabilitatea ca un client să nu aştepte.


Recommended