| |
Subiecte
|
|
Proiecte
Reguli
Cerinţe
- se va realiza un program interactiv;
-
documentatie.
Documentatia va avea urmatoarea structura:
Pagina de titlu - Proiect LISP - titlul proiectului,
numele si grupa studentului, anul;
Descrierea problemei (cerinte);
Consideratii teoretice (descrierea structurii de date
si a operatiilor asupra ei, descrierea algoritmului, fragmente de cod
Lisp);
Consideratii de implementare (module, functii si
descirerea lor, legatura intre functii, schema logica, probleme de
implementare si solutiile gasite);
Bibliografie;
Listing program - optional.
Evaluare
Fiecare temă poate fi aleasa doar o dată pe grupă de laborator
(una din cele 17 teme ).
Proiectele se vor prezenta între 23.05-28.05 (saptămâna 13), la orele
de laborator corespunzător programării.
La evaluarea proiectelor se ţine cont de:
- Originalitatea rezolvării
- Completitudinea abordării
- Corectitudinea programului
- Dificultatea problemei
După prezentare, sursa proiectelor va fi trimise prin email pe adresa
paul_zinca@yahoo.com sau ftulba@cs.utt.ro cu subjectul numărul de proiect urmat de numele
autorului (de ex.: 1 Paul Zinca). Ele vor fi supuse de o verificare
automată a orgininalităţii. Proiectele care rezultă că sunt preluate (de
la colegi sau de la alţi ani) nu vor fi acceptate (nota 3). Pentru
detectarea proiectelor asemănătoare este folosit Moss de la
Universitatea California, Berkeley.
Indicaţii
La multe proiecte găsiţi linkuri utile, dar care nu sunt neapărat
acoperitoare; necesitând documentarea suplimentară a proiectului.
Enunţuri
| 1. Operaţii cu arbori binari ordonaţi |
|
Se va scrie un program LISP care permite efectuarea
următoarelor operaţiuni în arbori binari ordonaţi:
- înserare,
- ştergere,
- căutare,
- parcurgere în
- preordine,
- inordine,
- postordine.
Se va alege o structură de dată corespunzătoare pentru
efectuarea performantă a operaţiilor.
Dificultate estimată: medie.
Efort de programare:
medie.
|
| 4. Expresii infix şi prefix |
Să se realizeze transformarea unei expresii matematice
din forma infix în forma prefix şi invers, precum şi evaluarea
expresiilor.
Operatori permişi: +, - *, -, ^, apel de
funcţie.
Se va verifica corectitudinea parantezelor.
Dificultate estimată: medie.
Efort de programare:
mare. |
| 5. Operaţii cu matrici rare |
|
Să se implementeze:
- citirea şi afişarea unei matrici rare,
- operaţiile de
- adunare,
- scădere,
- produs matrice cu scalar,
- produs matrice cu vector,
- produs a două matrici,
- invers,
- transpusă
În structura de date folosită se vor memora doar elementele
nenule a matricilor.
Dificultate estimată:
uşoară.
Efort de programare: mare.
|
| 8. Operaţii cu polinoame |
|
Se vor implementa operaţiile de
- adunare,
- scădere,
- înmulţire,
- împărţire
între polinoame.
Dificultate estimată: uşoară.
Efort de programare:
medie.
|
| 9. Operaţii cu numere întregi foarte lungi |
|
Numerele întregi, în baza 10, se vor memora ca liste
de cifre. Se vor implementa operaţiile de:
- adunare,
- scădere,
- înmulţire,
- împărţire
Dificultate estimată: uşoară.
Efort
de programare: uşoară.
|
| 10. Factorizare în factori primi |
|
Sa se scrie un program care:
- factorizeaza în termeni primi numere naturale
- calculeaza cel mai mare divizor comun şi cel mai mic multiplu
comun a mai multor numere date ca numere sau ca produs de factori,
folosind algoritmul din şcoala generală, bazată pe termeni primi
Dificultate estimată: uşoară.
Efort de programare:
medie.
|
| 11.Problema comis-voiajorului (traveling salesman problem) |
Se dă un număr N de oraşe
precum şi distantele dintre oraşele care au un drum direct între
ele. Să se determine traseul minim de parcurgere a tuturor oraşelor
pornind din oraşul X, astfel încât traseul
să se termine tot în X.
Resursă
HTML:
http://www.pcug.org.au/~dakin/tsp.htm
Dificultate
estimată: medie.
Efort de programare: medie. |
| 12. Problema
turnurilor din Hanoi |
|
Se dă un număr de trei
turnuri, identificate cu a, b si c. Turnul
a contine n discuri de dimensiuni diferite aranjate în ordine
crescatoare în raport cu dimensiunea lor. Problema consta în a
transfera discurile de pe a pe c pastrând ordinea de asezare a
discurilor. Discurile se pot transfera de pe un turn pe altul dupa
urmatoarele reguli:
- Transferul consta din mai multe mutari de
discuri. La o mutare se ia un singur disc de pe un turn si se muta
pe altul.
- Nu poate fi plasat un disc de dimensiune
mare pe unul de dimensiune mai mica.
-
Pentru transferarea discurilor de pe un turn pe altul se poate
folosi cel de-al treilea turn pentru manevra
(adica pentru a pune pe el temporar anumite discuri).
Resursă
HTML:
http://www.cs.ubbcluf.ro/~afanea/predare_facultate/
sem1/algoritmica_seminar/curs_html
http://www.upg-ploiesti.ro/curs_multimedia/conv713.htm
Dificultate
estimată: medie.
Efort de programare: medie.
|
| 13. Numere raţionale |
|
Se vor implementa funcţiile de transformare din numere
zecimale în numerele raţionale şi invers (Ex. 2.5 <-> 25 / 10 sau
0.(3) <> 1/3). Se vor
implementa operaţiile de
- adunare,
- scădere,
- înmulţire,
- împărţire
cu numere raţionale.
Dificultate
estimată: medie.
Efort de programare: uşoară.
|
| 14. Sortări prin interclasare |
|
Se vor implementa sortările prin interclasarea cu 3
bezi, interclasarea echilibrată, interclasarea naturală şi
interclasarea multiplă echilibrată. Se va permite urmărirea
interactivă a paşilor de execuţie.
Resurse
HTML:
http://labs.cs.utt.ro/labs/sdaa/html/sda/l5.html
Dificultate
estimată: uşoară.
Efort de programare: mare.
|
| 15. Gestiune de mărfuri |
|
Să se implementeze un sistem de evidenţă a mărfurilor
dintr-un magazin. Se vor trata:
- introducerea de noi produse în evidenţă
- vânzarea unor produse
- vizualizarea evidenţei
Se va aprecia generalitatea
abordării.
Dificultate estimată: medie.
Efort de
programare: medie.
|
Sumar
Proiect
1. Operaţii cu arbori binari ordonaţi
Proiect
2. Operaţii cu arbori AVL
Proiect
3.
Codificarea, decodoficarea folosind arbori Huffmann
Proiect
4. Expresii infix şi prefix
Proiect
5. Operaţii cu matrici rare
Proiect
6. Derivare simbolică
Proiect
7. Integrare simbolică
Proiect
8. Operaţii cu polinoame
Proiect
9. Operaţii cu numere întregi foarte lungi
Proiect
10. Descopunere în factori primi
Proiect
11. Problema comis-voiajorului
Proiect
12. Problema turnurilor
din Hanoi
Proiect
13. Numere raţionale
Proiect
14. Sortări prin interclasare
Proiect
15. Gestiune de mărfuri
Proiect
16. Transformarea Laplace directă şi indirectă
Proiect
17. Transformarea Z directă şi
indirectă. |