Cflp

Laborator

 

Facultatea de Automatica şi Calculatoare

Departamentul de Calculatoare


 
  Lucrarea 8 Lucrarea 9 Lucrarea 10 Lucrarea 11 Lucrarea 12 Lucrarea 13 Proiect Orar


  Lucrarea 9
 

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.

2. Operaţii cu arbori AVL

Se va scrie un program LISP care permite efectuarea următoarelor operaţii în arbori AVL:

  • înserare,
  • ştergere,
  • vizualizare.

Resurse HTML despre arbori AVL:
http://oopweb.com/Algorithms/Documents/AvlTrees/Volume/AvlTrees.htm
http://www.cis.ohio-state.edu/~gurari/course/cis680/cis680Ch10.html
http://www.informatik.uni-mannheim.de/~cjk/publications/ed-media98/node11.html
http://laplace.snu.ac.kr/~pos7hink/Courses/C++-Reference/AVLTree/AVL.html

Dificultate estimată: medie.
Efort de programare: mare.

 

3. Codificare, decodificare folosind arbori Huffmann

Sa se implementeze un program utilitar de compresie-decompresie a datelor, pe baza algoritmului lui Huffmann.

 

http://www.cs.utt.ro/~chirila/labs/sdaa/lab04/sdaa04html
http://bigfoot.cs.utt.ro/~cami/sdaa/sdaa/l4.html

Dificultate estimată: medie.
Efort de programare: mare.

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.

6. Derivare simbolică

Se va realiza derivarea simbolică în raport cu o variabilă şi optimizarea (simplificarea) a expresiei rezultate. Se permite citirea expresiei de derivat într-o formă mai uşor interpretabilă de program (de ex. forma prefix).
Exemplu: 3*X^3 rezultă 9*X^2.

Resurse HTML despre derivare:
http://www.math2.org/math/derivatives/tableof.htm
http://www.math2.org/math/derivatives/identities.htm
http://www.sosmath.com/tables/derivative/derivative.html
http://www.karlscalculus.org/divrules.html
http://web.mit.edu/wwmath/calculus/differentiation/table.html
http://www.sosmath.com/tables/derivative/derivative.html

Dificultate estimată: medie.
Efort de programare: medie.

7. Integrare simbolic

Se va realiza integrarea simbolică în raport cu o variabilă.
Se permite citirea expresiei de integrat într-o formă mai uşor interpretabilă de program (forma prefix). Se va urmării tratarea cazurilor cât mai general posibile.

Exemplu: 2*X rezultă X^2+C.

Resurse HTML despre integrare:
http://www.karlscalculus.org/calc11_1.html
http://www.karlscalculus.org/calculus.html
http://www.karlscalculus.org/calc11_1.html
http://www.math2.org/math/integrals.htm

Dificultate estimată: dificilă.
Efort de programare: medie.

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:

  1. 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.
  2. Nu poate fi plasat un disc de dimensiune mare pe unul de dimensiune mai mica.
  3. 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.

16. Calculul operaţional simbolic. Transformarea Laplace directă şi indirectă

Se va aplica transformarea Laplace directă şi indirectă a unei o funcţii.
Se permite citirea functiei într-o forma mai uşor interpretabilă de program (forma prefix).
Exemplu: t rezultă 1/s^2.

Resurse HTML despre transformata Laplace:
http://www.sosmath.com/tables/laplace/laplace.html
http://www.swarthmore.edu/NatSci/echeeve1/Ref/Laplace/Table.html
http://www.vibrationdata.com/Laplace.htm
http://www.sosmath.com/diffeq/laplace/table/table.html
http://www.stanford.edu/class/ee102k/laplace-table.pdf

Dificultate estimată: dificilă.
Efort de programare: mare.

17. Calculul operaţional simbolic. Transformarea Z directă şi indirectă.

Se va aplica transformarea Z directă şi indirectă a unei o funcţii.
Se permite citirea functiei într-o forma mai uşor interpretabilă de program (forma prefix).
Exemplu: n rezultă z/(z-1)^2.

Resurse HTML despre transformata Z:
http://www.swarthmore.edu/NatSci/echeeve1/Ref/Laplace/Table.html
http://cnx.rice.edu/content/m10119/latest/

Dificultate estimată: dificilă.
Efort de programare: mare.

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