https://www.algopedia.ro/wiki/index.php?action=history&feed=atom&title=Proiect_Algoritmi_Grafuri_ponderateProiect Algoritmi Grafuri ponderate - Revision history2026-04-13T19:08:21ZRevision history for this page on the wikiMediaWiki 1.44.2https://www.algopedia.ro/wiki/index.php?title=Proiect_Algoritmi_Grafuri_ponderate&diff=16286&oldid=prevBella: /* PROIECT - ALGORITMI GRAFURI PONDERATE */2019-05-28T00:59:36Z<p><span class="autocomment">PROIECT - ALGORITMI GRAFURI PONDERATE</span></p>
<p><b>New page</b></p><div>= PROIECT - ALGORITMI GRAFURI PONDERATE ( cerinte, barem de notare ) =<br />
Clasa a XI-a E, <br />
Prof Isabela Coman<br />
<br />
<br />
== 1. Alegeti una dintre teme == <br />
Alegeti unul din algoritmii prezentati mai jos <br />
==== Roy Floyd ( Drumuri minime ) ====<br />
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 )<br />
<br />
==== Dijkstra ( Drumuri minime de sursa unica )====<br />
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. <br />
Dijkstra poate fi folosit doar in grafuri care au toate muchiile nenegative.<br />
Algoritmul este de tip Greedy<br />
==== Bellman ( Drumuri minime de sursa unica ) -OPTIONAL ====<br />
- Similar cu Dijkstra, admite si costuri negative <br />
==== Prim ( Determinarea arborelui partial de cost minim) ==== <br />
==== Kruskal( Determinarea arborelui partial de cost minim) ====<br />
<br />
== 2. Formati echipe == <br />
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.<br />
Numele elevilor din echipa trebuie sa apara pe prima pagina a proiectului.<br />
<br />
== 3. Continut == <br />
==== Studiu de caz - Definirea algoritmul ====<br />
Porniti prezentarea de la exemple de probleme din viata reala. Puteti enunta mai multe probleme care se rezolva cu algoritmul propus<br />
==== Istoric ====<br />
==== Descriere algoritm si studiul complexitatii ====<br />
Descrieti algoritmul in pasi, prin exemple grafice.<br />
<br />
==== Implementare ==== <br />
Prezenta diferite forme de implementare: <br />
* diferite modalitati de a fi furnizate datele de intrare <br />
* diferite modalitati de reprezentare interna a grafului, ex: cu matrice de adiacenta, liste de adiacenta... <br />
* implementari diferite a tipurilor de date ex: liste alocate dinamic versus liste STL <br />
* 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. <br />
* 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 <br />
== 4. Forma de prezentare Proiect == <br />
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.<br />
Puteti insea animatii sau filmuletze pentru o mai buna vizualizare grafica a algoritmului.<br />
Puneti pe prima pagina componenta echipei, prof. indrumator.<br />
<br />
== 5. Bibliografie == <br />
Enumerati sursele de informare intr-o pagina dedicata special bibliografiei<br />
<br />
= Barem de notare =<br />
Istoric - 0.5p<br />
Bibliografie 0.5p<br />
Studiu de caz 1p <br />
Implementare 3p ( minim 3 modalitati de implementare )<br />
Studiul Complexitatii 1p <br />
Prezentare Ingrijita 1p <br />
Discurs de sustinere al proiectului 1p<br />
Puncte din oficiu 2p</div>Bella