Lista temelor de proiecte de an, cerinţele şi obiectivele lucrarilor de curs la disciplina

«Structuri de Date si Algoritmi"2012

Obiective: Formarea deprinderilor corecte si perfecţionarea stilului de algoritmizare şi programare cu diverse modele

de SD in TC. Aplicarea sistematici a unor tehnici de programare şi prezentarea structurilor de date în diverse moduri: fişiere

de date, vectori, pointeri la tablouri, pointeri la structuri şi funcţii cu indirectare multipli; definirea şi implementarea unor tipuri

abstracte de date; diverse tipuri de liste (bidirecţionale, înlănţuite» stive, coci, etc.) şi arbori; tabele de dispersie; grafuri si

reţele.

Prezentarea şi exemplificarea tehnicilor de programare cu diverse clase de algoritmi: Algoritmi de căutare cu revenire

Backtracking): algoritmi "Greedy": algoritmi recursivi ş.a. Reprezentarea şi descrierea noţiunilor deshhpre complexitatea

algoritmilor şi eficienţa lor cu aplicarea programarii structurate, modulare, etc.

P. I. Cerinţele obligatorii generale:

- Temele se studiazi individual de student pe parcursul elaboririi şi se consulta cu profesoral;

In lucrare (în partea teoretici şi practici) se analizează scenariile şi eficienţa algoritmilor posibili;

Toate lucrările studenţilor trebuie sa reflecte obiectivele cu intenţiile respective pentru implementarea algoritmilor cu

diverse modele de SD şi tehnici de programare;

Toate datele de intrare/ieşire sa se salveze în fişiere şi rezultatele executării cu diferite combinaţii de SD şi algoritmi si fie

expuse în forma grafică şi în fişiere;

- Testarea programului sa se efectueze în baza setului de date şi algoritmii selectaţi;

Totul trebuie sa corespunda stasului şi obiectivelor pentru îndeplinirea lucrărilor de curs la SDA. Toate programele trebuie

sa conţină meniu (textual/grafic) cu ajutor (help) şi diverse informaţii utile şi modul de utilizare:

MENIU Aplicaţiei:

1. H - Help (informaţii utile despre program şi biblioteci, utilizate)

2. E - Editare (moduri şi tehnici de modificare (inserări, ştergeri etc.))

3. C - Salvare (programului şi rezultatelor obţinute în fişiere: input, test şi output)

4. I - încărcarea fişierelor cu SD şi parcuigerea lor.

5. A - Afişare (textual şi grafic cu informaţii utile despre moduri şi tehnici de obţinere)

6. O - Operaţii ► SUBMENIU (plus informaţii utile despre tipurile SD şi algoritmii utilizaţi)

7. S - Sortări ► SUBMENIU (informaţiile despre metodele şi algoritmii, utilizate)

8. Q - Ieşire

Conţinutul raportului lucrării. Darea de seama (tipărită şi în forma electronică pe CD) trebuie să includă: Foaia de titlu

(Modelul special de la profesor). # Sarcina lucrării. Cuprins

• Introducere.

• 1. Raportul părţii teoretice trebuie să conţină numai aspectele esenţiale ale temei:

• 1.1 Analiza succintă a domeniului, problemei şi obiectivelor cu argumente şi desene explicative,

• 1.2 Descrierea principiilor, metodelor şi tehnicilor de elaborare ale SD şi algoritmilor, utilizate în program.

• 1.3 Descrierea scenariului elaborării programului: algoritmii şi SD ale limbajului C, implementate, concret, în program.

• 2. Descrierea structurii aplicaţiei şi schemele-bloc al algoritmilor la principalele funcţii.

• 3. Analiza, testarea şi verificarea rezultatelor cu fişiere şi corespunderea obiectivelor propuse.

• Concluzii.

• Lista literaturii utilizate.

• Anexa I. Listingul programului, dotat cu comentarii.

| Anexa 2. Rezultatele rulării programului cu exemple de testare şi verificare în mod text şi grafic. Finalizarea fiecărei

lucrări pentru susţinere va consta din raport cu: prezentarea programului sursă în mapă aparte (pe suport magnetic/CD); fişier-

teste cu date de intrare (pe suport magnetic /CD); | execuţia demonstrativă a programului cu rezultatele principale înserate in

fişierul .doc al lucrării; - documentaţia lucrării conform cerinţelor obligatorii generale (P.l), conţinând şi: testele efectuate,

analiza algoritmilor implementării statice şi dinamice. In raport să fie expuse toate activităţile şi dificultăţile întâlnite pe

parcursul efectuării lucrarii de curs.

Cebanu Ghennadie Varianta _________

Elaborarea aplicaţiei "Ikebana". O florărie vrea să ajungă în Guinness book cu cel mai mare aranjament floral.

Ei au la dispoziţie t tipuri de flori, dintre care patru tipuri sunt mai speciale: gerbera, orhideea, azaleea şi hortensia.

Lucrătorii au hotărât să pună florile distanţate uniform pe mai multe rânduri, pe fiecare rând exact n flori. Nu vor

exista două rânduri identice, dar toate rândurile vor respecta anumite cerinţe:

- Ei au observat că hortensiile au o viaţă mult mai îndelungată, dacă se învecinează pe acela şi rând cu o

azalee şi cu o orhidee, indiferent dacă ordinea este azalee-hortensie-orhidee sau orhidee-hortensie-azalee.

- Gerberele vor fi amplasate în aşa fel încât între oricare două gerbere să existe cel puţin p flori, tipul lor

fiind oricare dar nu gerbera.

De exemplu dacă avem la dispoziţie t=5 tipuri de flori: azalee (notate cu a), hortensii (notate cu h), orhidee

(notate cu o), gerbere (notate cu g), şi begonii (notate cu b), între două gerbere se vor amplasa minim p=3 flori, iar

rândul va fi format din n=6 flori, atunci următoarele aranjamente florale sunt corecte: "aoaaoo", "ahohag",

"gbbbgo", "gbbbog", "bbbbbb". Următoare aranjamente nu sunt însă corecte: "ohoaha" (hortensiile nu sunt între o

orhidee şi o azalee), "gogbao" (cele două gerbere nu sunt despărţite de minim trei flori), "ahohah" (ultima hortensie

nu se învecinează cu o orhidee). Pentru n=6, p=3, t=5, numărul diferitelor aranjamente florale este 2906.

Cunoscând valorile lui n, p şi t, să se determine numărul liniilor distincte ce se pot obţine cu cerinţele de mai sus.

Salvaţi în fişiere şi afişaţi toate rezultatele.