Proiect Algoritmi Grafuri ponderate

PROIECT - ALGORITMI GRAFURI PONDERATE ( cerinte, barem de notare )

Clasa a XI-a E, Prof Isabela Coman

1. Alegeti una dintre teme

Alegeti unul din algoritmii prezentati mai jos

Roy Floyd ( Drumuri minime )

Cautarea drumului minim intre oricare 2 noduri ale unui graf - ( obtinem o matrice drumurilor in care orice element a[i][j] e drumul minim de la i la j )

Dijkstra ( Drumuri minime de sursa unica )

Cautarea drumului minim intre un nod fixat x si oricare nod al grafului - obtinem un vector in care in care orice element d[i] reprezinta costul minim de la nodul fixat x la nodul i. Dijkstra poate fi folosit doar in grafuri care au toate muchiile nenegative. Algoritmul este de tip Greedy

Bellman ( Drumuri minime de sursa unica ) -OPTIONAL

- Similar cu Dijkstra, admite si costuri negative

2. Formati echipe

Realizati proiectul in echipe de cate 2, maxim 3 elevi; in echipa sa fie cel putin un incepator si un avansat; fiecare participant va prezenta contributia sa la proiect. Numele elevilor din echipa trebuie sa apara pe prima pagina a proiectului.

3. Continut

Studiu de caz - Definirea algoritmul

Porniti prezentarea de la exemple de probleme din viata reala. Puteti enunta mai multe probleme care se rezolva cu algoritmul propus

Descriere algoritm si studiul complexitatii

Descrieti algoritmul in pasi, prin exemple grafice.

Implementare

Prezenta diferite forme de implementare:

• diferite modalitati de a fi furnizate datele de intrare
• diferite modalitati de reprezentare interna a grafului, ex: cu matrice de adiacenta, liste de adiacenta...
• implementari diferite a tipurilor de date ex: liste alocate dinamic versus liste STL
• diferite cerinte: de pilda daca algoritmul afla drumul cel mai scurt intre doua puncte, putem avea sa zicem * variante de cerinte: sa se afiseze lungimea maxima, sau sa se afiseze drumul minim si anume succesiunea nodurilor prin care trece drumul.
• algoritmi de complexitate diferita. Daca problema voastra admite o rezolvare simpla printr-un algoritm de complexitate de timp de n^3 de exemplu, scrieti intai aceasta rezolvare, apoi propuneti algoritmi mai efisienti, explicand modul in care a fost eficientizat algoritmul

4. Forma de prezentare Proiect

Va recomand sa va prezentati proiectele sub forma unor pagini web. Puteti de asemenea sa folositi si pagini web, insa va va fi mai greu sa incadrati codul in slide-uri. Puteti insea animatii sau filmuletze pentru o mai buna vizualizare grafica a algoritmului. Puneti pe prima pagina componenta echipei, prof. indrumator.

5. Bibliografie

Enumerati sursele de informare intr-o pagina dedicata special bibliografiei

Barem de notare

Istoric -                          0.5p
Bibliografie                       0.5p
Studiu de caz                        1p 
Implementare                         3p ( minim 3 modalitati de implementare )
Studiul Complexitatii                1p 
Prezentare Ingrijita                 1p 
Discurs de sustinere al proiectului  1p
Puncte din oficiu                    2p