--------------------------

pentru studentii anului II

--------------------------

1. Problema labirintului (1 student)

---------------------

Dat un labirint, sa se gaseasca un drum intre intrare si iesire. Sa

se gaseasca drumul minim intre intrare si iesire. Sa se gaseasca

toate drumurile intre intrare si iesire.

2. Problema misionarilor si canibalilor (2 studenti)

------------------------------------

Trei misionari si trei canibali trebuie sa treaca un rau cu o barca

in care pot incapea cel mult doua persoane (nu exista poduri, raul nu

se poate trece inot si barca nu poate merge singura). Daca numarul

canibalilor depaseste numarul oamenilor, atunci acestia din urma vor

fi mancati (lucru ce nu trebuie sa se intample). Sa se gaseasca o

strategie de traversare (program C) a raului astfel incat

sa fie toti nevatamati.

+ Problema durilor si domnisoarelor

---------------------------------

Trei domnisoare impreuna cu cei trei prieteni "duri" ai lor doresc sa

mearga la plaja. Ei dispun insa doar de o masina sport cu numai doua

locuri. Scrieti un program C astfel incat toti sa ajunga

la plaja, stiind insa ca nici o fata nu poate calatori cu un baiat

(exceptandu-l desigur pe prietenul ei). Se cunoaste in plus si

faptul ca toate persoanele implicate detin permis de conducere.

3. Triunghiul Puzzle (2 studenti)

-----------------

Triunghiul Puzzle (numit uneori si arborele puzzle de Craciun)

contine 15 oua si are urmatoarea forma triunghiulara

o

o o

o o o

o o o o

o o o o o

In fiecare astfel de gaura este deci un ou. Jucatorul trebuie sa ia

un ou, apoi trebuie sa sara peste alt ou, luand bineinteles si oul

sarit. Sa se gaseasca o strategie (program C) de scoatere

a oualor astfel incat in final sa ramana exact un ou.

Generalizare: Alte configuratii

-------------

Foc Cruce Plus

--- ----- ----

___ ___ ___

|ooo| | | | |

__|ooo|__ __| o |__ __| o |__

| ooo | | ooo | | o |

| o o | | o | | ooooo |

|__ __| |__ o __| |__ o __|

| | | | | o |

|___| |___| |___|

Piramida Diamant Solitar

-------- ------- -------

___ ___ ___

| | | o | |ooo|

__| o |__ __|ooo|__ __|ooo|__

| ooo | | ooooo | | ooooooo |

| ooooo | | ooo ooo | | ooo ooo |

|_ooooooo_| |__ooooo__| |_ooooooo_|

| | |ooo| |ooo|

|___| |_o_| |ooo|

4. Colorarea hartilor (1 student)

------------------

Fie o harta cu vecini colorati distincti. Pentru anumite configuratii

arbitrare aratati ca sunt suficiente patru culori pentru colorarea

hartii.

5. Arbori partiali (subgraf partial) ai unui graf (2 studenti)

----------------------------------------------

Fie G=(V,E) un (multi)graf. Sa se descrie un program C pentru:

i) testarea daca G' este subgraf al lui G;

ii) testarea daca A este arbore in G;

iii) enumerarea (si numararea) tuturor arborilor dintr-un graf.

Aplicatii in chimie (structuri comune pentru molecule).

6. Arbori partiali de cost minim (1 student)

------------------------------------------

Fie G=(V,E) un graf. Sa se descrie un program C pentru determinarea

arborelui partial de cost minim folosind algoritmii lui Prim si Kruskal.

7. Arborescente partiale de cost minim (1 student)

-----------------------------------------------

Fie G=(V,E) un digraf. Sa se descrie un program C pentru determinarea

arborescentei partiale de cost minim folosind algoritmul lui Edmonds.

8. Problema orarului (facultate) (2 studenti)

-----------------------------

Se da o lista de profesori cu optiunile lor, o lista de sali

disponibile si anii de studii cu anumite restrictii (de exemplu:

intre orele 12-16, studentii trebuie sa aiba doua ore libere).

Sa se gasesca o euristica de descriere a unui astfel de orar (care sa

fie si consistent).

9. Metode de sortare (1 studenti)

-----------------

Quicksort. Interclasare. Bubble sort. Heapsort.

10. Minesweeper (2 studenti)

-----------

Se da o tabla dreptunghiulara cu m linii si n coloane. Fiecare celula

dispune de un capac care ascunde o bomba. Daca ridicam capacul si

gasim bomba, atunci am pierdut. In caz contrar, gasim un numar ce

reprezinta cardinalul vecinilor ce ascund bomba.

De exemplu, locului x de mai jos:

a b a

a x b

a a a

ii corespunde numarul 2 (b semnifica bomba, iar a semnifica spatii goale).

Sa se gaseasca o strategie de castig (care consta in identificarea

tuturor bombelor de pe tabla) precum si o interfata grafica "frumoasa".

Cazuri numerice: m=8, n=8, b=10; sau

m=16, n=16, b=40; sau

m=19, n=30, b=99;

unde prin b am notat numarul total de bombe.

11. Poker (2 studenti)

-----

Reprezentare grafica. (documentatie)

12. Problema reginelor (1 student)

------------------

Generarea permutarilor. Problema reginelor.

13. Aplicatii ale fluxului maxim in teoria grafurilor (2 studenti)

-------------------------------------------------

Sa se calculeze:

- numarul de stabilitate si de cuplaj in grafuri bipartite;

- recunoasterea secventelor digrafice;

- determinarea numarului de muchie conexiune;

- determinarea numarului de conexiune.

(documentatie)

14. Stabila maxima (1 student)

--------------------

Fie G=(V,E) un graf (digraf). Sa se scrie programe C pentru generarea

multimilor stabile maximale;

15. Drum si circuit hamiltonian (1 student)

---------------------------

Fie G=(V,E) un graf (digraf). Sa se scrie programe C pentru drumuri si

circuite hamiltoniene si euleriene.

16. Generari de submultimi (2 studenti)

----------------------

Generarea produsului cartezian, submultimilor, combinarilor,

aranjamentelor, partitiilor unei multimi finite.

17. Centrate (2 studenti)

--------

Code Break, Master Mind (interfata si algoritm de castig)

(documentatie)

18. Lucrul cu liste si arbori (1 student)

-------------------------

Scrieti un program C care sa defineasca operatiile principale asupra

listelor (stergerea capului listei, inserarea normala a unui element

nou in coada, inserarea si stergerea unui element in lista dupa o

pozitie data). De asemenea, scrieti si un predicat pentru stergerea unui

nod specificat intr-un arbore binar dat. Gasiti un subarbore ST

intr-un arbore T si inlocuiti-l printr-un alt subarbore CH.

19. Structura algebrica de grup (1 student)

---------------------------

Scrieti un program C care testeaza daca o structura

algebrica este grup.

20. Demonstrarea automata a teoremelor (2 studenti)

----------------------------------

Scrieti un program C pentru calculul propozitional, care

sa utilizeze macar urmatorii conectori: echivalenta, implicatia,

disjunctia, conjunctia, negatia.

21. Rezolutia Robinson (1 student)

------------------

Utilizand algoritmul de satisfiabilitate al Juliei Robinson pentru o

formula booleana F (in FNC) scrieti un program C care sa

testeze daca F este satisfiabila.

22. Arbori binari <-> liste (1 student)

-----------------------

Construiti un predicat de linearizare a unui arbore binar intr-o

lista si un predicat de reconstituire a unui arbore binar dintr-o

lista.

23. Schimbarea banilor (1 student)

------------------

Fie A_n=Aa_1, a_2, ..., a_nS o multime finita de tipuri de monezi

(a_i numar natural). Pentru fiecare tip, exista o infinitate de

monezi. Pentru un C dat, sa se determine numarul minim de monezi care

dau exact suma C.

24. Acoperire de grafuri (1 student)

--------------------

Fie G=(V,E) un graf. O acoperire a nodurilor lui G este o submultime

U<=V astfel incat fiecare muchie este incidenta la cel putin un varf

din U. Sa se scrie un program C care determina o acoperire

cu numar minim de varfuri.

25. Algoritmi de analiza lexicala (2 studenti)

-------------------------------

Implementarea algoritmilor de analiza lexicala (AFD, AFN, ST, expresii

regulate).

26. Algoritm de analiza sintactica LL(1) (1 student)

------------------------------------

Implementarea algoritmului de analiza sintactica LL(1).

27. Algoritm de analiza sintactica de precedenta (1 student)

--------------------------------------------

Implementarea algoritmului de analiza sintactica pentru gramatici de

precedenta.

28. Calculator de buzunar (1 student)

---------------------

Implementarea in C a unui mini-calculator folosind gramatica expresiilor

artimetice cu atribute.

29. Problema mariajului (2 studenti)

-------------------

Se considera n barbati (b_1, b_2, ..., b_n), n femei (f_1, f_2, ...,

f_n) si doua functii P,Q:A1,...,nSxA1,...nS -> (0,infinit) cu

semnificatia:

P(i,j) = gradul de preferinta al lui b_i pentru f_j

Q(i,j) = gradul de preferinta al femeii f_i pentru b_j

Sa se scrie un program C care genereaza n perechi de tip

(b,f) astfel incat suma preferintelor sa fie maxima.

30. Pentomin (2 studenti)

--------

Se considera urmatoarele 12 figuri: (documentatie)

Sa se scrie un program C care sa determine toate

aranjarile de figuri care formeaza un dreptunghi (sau alt poligon cu

laturile paralele cu axele).

31. Mutarea calului (1 student)

---------------

Se considera o tabla de sah n x n pe care se plaseaza arbitrar un cal

pe pozitia (x,y). Sa se determine n^2-1 mutari ale calului astfel

incat fiecare pozitie a tablei sa fie vizitata exact o data.

32. Cele mai apropiate perechi (1 student)

--------------------------

Date n puncte in plan, sa se determine o pereche de puncte care sunt

cele mai apropiate in sensul distantei. Daca exista mai multe

perechi, se va determina una dintre ele.

33. Cautare in plan (2 studenti)

---------------

Se considera un graf in plan cu varfurile coordonate intregi si

arcele segmente de dreapta paralele cu axele de coordonate. Acest

graf imparte planul intr-un numar finit de regiuni marginite si o

regiune nemarginita. Se mai considera dat un punct z=(u,v). Sa se

scrie un program C care determina regiunea la care

apartine z. (Reprezentare grafica)

34. Infasuratoarea convexa (2 studenti)

----------------------

Date N puncte in plan, sa se scrie un program care determina un

poligon convex de arie minima ce contine in interior aceste puncte.

(Reprezentare grafica)

35. Derivare formala (2 studenti)

----------------

Se considera expresii algebrice construite cu constante reale,

operatorii -, +, *, /, ln, exp, o si variabilele x, u, v, .... Sa se

scrie un program C care determina expresia derivatei utilizind regulile:

D(a) ---> a

D(x) ---> 1

D(-u) ---> -D(u)

D(u+v) ---> D(u) + D(v)

D(u-v) ---> D(u) - D(v)

D(u*v) ---> D(u)*v + u*D(v)

D(u/v) ---> (D(u)*v - u*D(v))/(v*v)

D(ln(u)) ---> D(u)/u

D(exp(u)) ---> D(u)*exp(u)

D((f o g)(u)) ---> D(f)(g(u))*D(g)(u)

36. Interiorul poligonului (2 studenti)

----------------------

Sa se scrie un program C care pentru un poligon simplu dat

in plan, determina numarul minim de virfuri astfel incat reuniunea

campurilor interne de vizibilitate acopera tot interiorul poligonului.

37. Cuvinte incrucisate (1 student)

-------------------

Reprezentare grafica.