Proiect: Problema Vertex Cover

Conținutul arhivei

Arhiva proiectului include următoarele:

1. Raportul

   • Fișier PDF intitulat Raport_Proiect.pdf.
   • Include descrierea problemei, metodologia aplicată, analiza complexității, exemple de teste și concluzii.

2. Cod sursă

   • Directorul src/ conține cele 3 implementări în cod Python utilizate pentru rezolvarea problemei Vertex Cover, cât și Makefile-ul pentru evaluare.
   • Fişiere incluse:
     • brute-force.py
     • deterministic.py
     • probabilistic.py
     • Makefile

3. Teste

   • Directorul tests/ include testele utilizate pentru validarea soluției.
   • Fişiere incluse:
     • 20 de teste: cazuri particulare + exemple aleatoare.

---

Cum se pot evalua soluțiile

Pentru evaluarea soluțiilor am scris un fișier Makefile pentru bash. Am folosit benchmarking tool-ul hyperfine, configurat cu 10 iterații de warm-up și 20 de iterații per algoritm, pentru fiecare algoritm în parte. Rezultatele obținute pentru fiecare test în parte se vor afla la calea ../benchmarks/test-i: în fișierele .md se află informații strict despre timpul de rulare, pe când în fișierele .out se află și output-ul pentru fiecare iterație.

---

Surse externe utilizate

• GeeksforGeeks - explicație și exemplu pentru problema Vertex Cover
• Pseudocod și demonstrația factorului de aproximare pentru soluția deterministică
• Pseudocod și demonstrația factorului de aproximare pentru soluția probabilistică
• ChatGPT: Utilizat pentru generarea automată a testelor aleatoare(fără cazuri speciale)