Variante si bareme
| Student | Varianta |
|---|---|
| alecserazvan21@stud.ase.ro | Bareme si subiecte |
| alecualexandru26@stud.ase.ro | Bareme si subiecte |
| alexandruana26@stud.ase.ro | Bareme si subiecte |
| andreescuiustin26@stud.ase.ro | Bareme si subiecte |
| andreivictor26@stud.ase.ro | Bareme si subiecte |
| apostolescuioana26@stud.ase.ro | Bareme si subiecte |
| atanasiudarius26@stud.ase.ro | Bareme si subiecte |
| auterifrancesco26@stud.ase.ro | Bareme si subiecte |
| baicudavid26@stud.ase.ro | Bareme si subiecte |
| balaurualin26@stud.ase.ro | Bareme si subiecte |
| baloivasile26@stud.ase.ro | Bareme si subiecte |
| barbumario26@stud.ase.ro | Bareme si subiecte |
| borcosdaria26@stud.ase.ro | Bareme si subiecte |
| boteanuamalia26@stud.ase.ro | Bareme si subiecte |
| bulatamarius26@stud.ase.ro | Bareme si subiecte |
| bungeteduard26@stud.ase.ro | Bareme si subiecte |
| buteanmara26@stud.ase.ro | Bareme si subiecte |
| chiraneduard26@stud.ase.ro | Bareme si subiecte |
| chiritadarius26@stud.ase.ro | Bareme si subiecte |
| cicudavid26@stud.ase.ro | Bareme si subiecte |
| ciobotarualexandru26@stud.ase.ro | Bareme si subiecte |
| ciolacuflorian26@stud.ase.ro | Bareme si subiecte |
| ciucamaria26@stud.ase.ro | Bareme si subiecte |
| codesculucian26@stud.ase.ro | Bareme si subiecte |
| condratoana26@stud.ase.ro | Bareme si subiecte |
| craciunescumara26@stud.ase.ro | Bareme si subiecte |
| craciuntheodor26@stud.ase.ro | Bareme si subiecte |
| davidbianca26@stud.ase.ro | Bareme si subiecte |
| diaconitaandreea26@stud.ase.ro | Bareme si subiecte |
| dimamatei26@stud.ase.ro | Bareme si subiecte |
| dincarares26@stud.ase.ro | Bareme si subiecte |
| dinudaniel26@stud.ase.ro | Bareme si subiecte |
| dinuvlad26@stud.ase.ro | Bareme si subiecte |
| ditescumarius26@stud.ase.ro | Bareme si subiecte |
| dolhanfederica26@stud.ase.ro | Bareme si subiecte |
| dorinm@ase.ro | Bareme si subiecte |
| dragusaneduard26@stud.ase.ro | Bareme si subiecte |
| dragusinantonia26@stud.ase.ro | Bareme si subiecte |
| dumitrumihai26@stud.ase.ro | Bareme si subiecte |
| dumitrustefan26@stud.ase.ro | Bareme si subiecte |
| dumitruvictor26@stud.ase.ro | Bareme si subiecte |
| enachevictoria26@stud.ase.ro | Bareme si subiecte |
| farcasvlad26@stud.ase.ro | Bareme si subiecte |
| gavrilescuradu26@stud.ase.ro | Bareme si subiecte |
| georgescubianca26@stud.ase.ro | Bareme si subiecte |
| gheorghemihai26@stud.ase.ro | Bareme si subiecte |
| gheorghiuiarina26@stud.ase.ro | Bareme si subiecte |
| gherghemaria26@stud.ase.ro | Bareme si subiecte |
| gogosanudavid26@stud.ase.ro | Bareme si subiecte |
| husneacdavid26@stud.ase.ro | Bareme si subiecte |
| iacobvlad26@stud.ase.ro | Bareme si subiecte |
| iazuclara26@stud.ase.ro | Bareme si subiecte |
| iftodigreta26@stud.ase.ro | Bareme si subiecte |
| ioneric26@stud.ase.ro | Bareme si subiecte |
| iordachecristina26@stud.ase.ro | Bareme si subiecte |
| istratemarius26@stud.ase.ro | Bareme si subiecte |
| ivaneric26@stud.ase.ro | Bareme si subiecte |
| jederandrei26@stud.ase.ro | Bareme si subiecte |
| jipaandreea26@stud.ase.ro | Bareme si subiecte |
| lengyelvlad26@stud.ase.ro | Bareme si subiecte |
| lintemihai26@stud.ase.ro | Bareme si subiecte |
| lobellomattia26@stud.ase.ro | Bareme si subiecte |
| marinescuraluca26@stud.ase.ro | Bareme si subiecte |
| mariniustin26@stud.ase.ro | Bareme si subiecte |
| marinserban26@stud.ase.ro | Bareme si subiecte |
| micumihai26@stud.ase.ro | Bareme si subiecte |
| mihalacheamalia26@stud.ase.ro | Bareme si subiecte |
| misircutina26@stud.ase.ro | Bareme si subiecte |
| mitrescualexandru26@stud.ase.ro | Bareme si subiecte |
| mogaalexandru26@stud.ase.ro | Bareme si subiecte |
| nedelescuvictor26@stud.ase.ro | Bareme si subiecte |
| nicodimrobert26@stud.ase.ro | Bareme si subiecte |
| nicolaedaria26@stud.ase.ro | Bareme si subiecte |
| olteanudaria26@stud.ase.ro | Bareme si subiecte |
| orboceamatei26@stud.ase.ro | Bareme si subiecte |
| paturanthomas26@stud.ase.ro | Bareme si subiecte |
| pavelmarian26@stud.ase.ro | Bareme si subiecte |
| pazuandrei26@stud.ase.ro | Bareme si subiecte |
| petrestefan26@stud.ase.ro | Bareme si subiecte |
| popescu1david26@stud.ase.ro | Bareme si subiecte |
| puscalauvlaicu26@stud.ase.ro | Bareme si subiecte |
| raducatalin26@stud.ase.ro | Bareme si subiecte |
| rusuanisia26@stud.ase.ro | Bareme si subiecte |
| satnoianumihnea26@stud.ase.ro | Bareme si subiecte |
| savinpatrick26@stud.ase.ro | Bareme si subiecte |
| simavlad26@stud.ase.ro | Bareme si subiecte |
| simionalexandra26@stud.ase.ro | Bareme si subiecte |
| stefanescuandreea26@stud.ase.ro | Bareme si subiecte |
| stefanoiualexia26@stud.ase.ro | Bareme si subiecte |
| stoianingrid26@stud.ase.ro | Bareme si subiecte |
| stoicastefan26@stud.ase.ro | Bareme si subiecte |
| stoicateodor26@stud.ase.ro | Bareme si subiecte |
| subtiricaluca25@stud.ase.ro | Bareme si subiecte |
| tancaumaximilian26@stud.ase.ro | Bareme si subiecte |
| tanrikuludan26@stud.ase.ro | Bareme si subiecte |
| vanghelescumiruna26@stud.ase.ro | Bareme si subiecte |
| vedelbogdan26@stud.ase.ro | Bareme si subiecte |
| vladandrei26@stud.ase.ro | Bareme si subiecte |
| vlaicuioana26@stud.ase.ro | Bareme si subiecte |
| zincaanca26@stud.ase.ro | Bareme si subiecte |
Examen Cercetari Operationale - Set 2
Student: dolhanfederica26@stud.ase.ro
Rezolvati pe hartie. Aratati etapele algoritmilor.
1. Kruskal
Determinati arborele partial de cost minim si costul total.
| A – B: 25 | A – E: 14 | A – F: 17 | B – C: 30 |
| B – E: 6 | B – G: 19 | C – D: 9 | C – F: 32 |
| C – G: 11 | D – G: 20 | D – H: 10 | E – F: 7 |
| E – H: 37 | F – G: 12 | F – H: 21 | G – H: 4 |
Muchii neorientate. La egalitate, ordonare lexicografica.
Intrebari suplimentare (5)
- Care este muchia acceptata cu numarul 4? [Raspuns: C-D]
- Care este ultima muchie acceptata? [Raspuns: A-E]
- Care este prima muchie analizata? [Raspuns: G-H]
- Care este ponderea celei de-a patra muchii acceptate? [Raspuns: 9]
- Cate componente raman dupa a treia muchie acceptata? [Raspuns: 5]
Arbore minim: G-H, B-E, E-F, C-D, D-H, F-G, A-E | Cost: 62
Urma: G-H (4) DA; B-E (6) DA; E-F (7) DA; C-D (9) DA; D-H (10) DA; C-G (11) NU; F-G (12) DA; A-E (14) DA;
2. Dijkstra
Determinati drumul minim de la S la T si lungimea lui.
| S – A: 16 | S – B: 8 | S – D: 10 | A – C: 2 |
| A – E: 7 | A – F: 12 | B – C: 5 | B – D: 4 |
| B – F: 11 | C – E: 14 | C – G: 4 | D – F: 3 |
| D – G: 2 | E – F: 16 | E – T: 15 | F – G: 7 |
| F – T: 10 | G – T: 11 |
Muchii neorientate. La egalitate, se fixeaza nodul lexicografic mai mic.
Intrebari suplimentare (5)
- Care este al 5-lea nod fixat? [Raspuns: C]
- Care este predecesorul final al nodului T? [Raspuns: G]
- Care este eticheta nodului D dupa prima iteratie? [Raspuns: 10]
- Cate arce contine drumul minim S-T? [Raspuns: 3]
- Care este al treilea nod al drumului minim S-T? [Raspuns: G]
Drum: S -> D -> G -> T | Lungime: 23
Ordinea fixarii: S B D G C F A E T
3. Flux maxim - Ford-Fulkerson
Trei surse S1, S2, S3 alimenteaza trei destinatii D1, D2, D3. Determinati fluxul maxim si o repartizare optima.
Folositi nodul fictiv O (sursa unica) si Z (destinatia unica). Capacitatile O-Si sunt disponibilurile surselor, capacitatile Si-Dj sunt cele din tabel, iar capacitatile Dj-Z sunt cererile maxime ale destinatiilor. Nu este obligatorie satisfacerea tuturor cererilor.
| Sursa / Destinatie | D1 | D2 | D3 | Disponibil |
|---|---|---|---|---|
| S1 | 7 | 4 | 3 | 13 |
| S2 | 6 | 12 | 6 | 9 |
| S3 | 5 | 4 | 1 | 14 |
| Cerere maxima | 14 | 13 | 13 | - |
Pentru intrebarile despre drumurile de crestere folositi Ford-Fulkerson cu BFS (Edmonds-Karp). La explorare, ordinea nodurilor este O, S1, S2, S3, D1, D2, D3, Z. Se admit si arce reziduale inverse.
Intrebari suplimentare (5)
- Care este fluxul final pe arcul S1-D1? [Raspuns: 6]
- Care este fluxul final pe arcul S3-D1? [Raspuns: 5]
- Care este fluxul final pe arcul S3-D3? [Raspuns: 1]
- Care este valoarea fluxului dupa prima crestere? [Raspuns: 7]
- Cate drumuri de crestere foloseste algoritmul BFS? [Raspuns: 11]
Flux maxim: 32 | Taietura minima: 32
| Sursa | D1 | D2 | D3 |
|---|---|---|---|
| S1 | 6 | 4 | 3 |
| S2 | 3 | 5 | 1 |
| S3 | 5 | 4 | 1 |
Drumuri de crestere:
- O -> S1 -> D1 -> Z; +7; total 7
- O -> S1 -> D2 -> Z; +4; total 11
- O -> S1 -> D3 -> Z; +2; total 13
- O -> S2 -> D1 -> Z; +6; total 19
- O -> S2 -> D2 -> Z; +3; total 22
- O -> S3 -> D1 -> Z; +1; total 23
- O -> S3 -> D2 -> Z; +4; total 27
- O -> S3 -> D3 -> Z; +1; total 28
- O -> S3 -> D1 -> S1 -> D3 -> Z; +1; total 29
- O -> S3 -> D1 -> S2 -> D2 -> Z; +2; total 31
- O -> S3 -> D1 -> S2 -> D3 -> Z; +1; total 32
Taietura minima: O->S1, O->S2, S3->D1, S3->D2, S3->D3