Variante si bareme

StudentVarianta
alecserazvan21@stud.ase.roBareme si subiecte
alecualexandru26@stud.ase.roBareme si subiecte
alexandruana26@stud.ase.roBareme si subiecte
andreescuiustin26@stud.ase.roBareme si subiecte
andreivictor26@stud.ase.roBareme si subiecte
apostolescuioana26@stud.ase.roBareme si subiecte
atanasiudarius26@stud.ase.roBareme si subiecte
auterifrancesco26@stud.ase.roBareme si subiecte
baicudavid26@stud.ase.roBareme si subiecte
balaurualin26@stud.ase.roBareme si subiecte
baloivasile26@stud.ase.roBareme si subiecte
barbumario26@stud.ase.roBareme si subiecte
borcosdaria26@stud.ase.roBareme si subiecte
boteanuamalia26@stud.ase.roBareme si subiecte
bulatamarius26@stud.ase.roBareme si subiecte
bungeteduard26@stud.ase.roBareme si subiecte
buteanmara26@stud.ase.roBareme si subiecte
chiraneduard26@stud.ase.roBareme si subiecte
chiritadarius26@stud.ase.roBareme si subiecte
cicudavid26@stud.ase.roBareme si subiecte
ciobotarualexandru26@stud.ase.roBareme si subiecte
ciolacuflorian26@stud.ase.roBareme si subiecte
ciucamaria26@stud.ase.roBareme si subiecte
codesculucian26@stud.ase.roBareme si subiecte
condratoana26@stud.ase.roBareme si subiecte
craciunescumara26@stud.ase.roBareme si subiecte
craciuntheodor26@stud.ase.roBareme si subiecte
davidbianca26@stud.ase.roBareme si subiecte
diaconitaandreea26@stud.ase.roBareme si subiecte
dimamatei26@stud.ase.roBareme si subiecte
dincarares26@stud.ase.roBareme si subiecte
dinudaniel26@stud.ase.roBareme si subiecte
dinuvlad26@stud.ase.roBareme si subiecte
ditescumarius26@stud.ase.roBareme si subiecte
dolhanfederica26@stud.ase.roBareme si subiecte
dorinm@ase.roBareme si subiecte
dragusaneduard26@stud.ase.roBareme si subiecte
dragusinantonia26@stud.ase.roBareme si subiecte
dumitrumihai26@stud.ase.roBareme si subiecte
dumitrustefan26@stud.ase.roBareme si subiecte
dumitruvictor26@stud.ase.roBareme si subiecte
enachevictoria26@stud.ase.roBareme si subiecte
farcasvlad26@stud.ase.roBareme si subiecte
gavrilescuradu26@stud.ase.roBareme si subiecte
georgescubianca26@stud.ase.roBareme si subiecte
gheorghemihai26@stud.ase.roBareme si subiecte
gheorghiuiarina26@stud.ase.roBareme si subiecte
gherghemaria26@stud.ase.roBareme si subiecte
gogosanudavid26@stud.ase.roBareme si subiecte
husneacdavid26@stud.ase.roBareme si subiecte
iacobvlad26@stud.ase.roBareme si subiecte
iazuclara26@stud.ase.roBareme si subiecte
iftodigreta26@stud.ase.roBareme si subiecte
ioneric26@stud.ase.roBareme si subiecte
iordachecristina26@stud.ase.roBareme si subiecte
istratemarius26@stud.ase.roBareme si subiecte
ivaneric26@stud.ase.roBareme si subiecte
jederandrei26@stud.ase.roBareme si subiecte
jipaandreea26@stud.ase.roBareme si subiecte
lengyelvlad26@stud.ase.roBareme si subiecte
lintemihai26@stud.ase.roBareme si subiecte
lobellomattia26@stud.ase.roBareme si subiecte
marinescuraluca26@stud.ase.roBareme si subiecte
mariniustin26@stud.ase.roBareme si subiecte
marinserban26@stud.ase.roBareme si subiecte
micumihai26@stud.ase.roBareme si subiecte
mihalacheamalia26@stud.ase.roBareme si subiecte
misircutina26@stud.ase.roBareme si subiecte
mitrescualexandru26@stud.ase.roBareme si subiecte
mogaalexandru26@stud.ase.roBareme si subiecte
nedelescuvictor26@stud.ase.roBareme si subiecte
nicodimrobert26@stud.ase.roBareme si subiecte
nicolaedaria26@stud.ase.roBareme si subiecte
olteanudaria26@stud.ase.roBareme si subiecte
orboceamatei26@stud.ase.roBareme si subiecte
paturanthomas26@stud.ase.roBareme si subiecte
pavelmarian26@stud.ase.roBareme si subiecte
pazuandrei26@stud.ase.roBareme si subiecte
petrestefan26@stud.ase.roBareme si subiecte
popescu1david26@stud.ase.roBareme si subiecte
puscalauvlaicu26@stud.ase.roBareme si subiecte
raducatalin26@stud.ase.roBareme si subiecte
rusuanisia26@stud.ase.roBareme si subiecte
satnoianumihnea26@stud.ase.roBareme si subiecte
savinpatrick26@stud.ase.roBareme si subiecte
simavlad26@stud.ase.roBareme si subiecte
simionalexandra26@stud.ase.roBareme si subiecte
stefanescuandreea26@stud.ase.roBareme si subiecte
stefanoiualexia26@stud.ase.roBareme si subiecte
stoianingrid26@stud.ase.roBareme si subiecte
stoicastefan26@stud.ase.roBareme si subiecte
stoicateodor26@stud.ase.roBareme si subiecte
subtiricaluca25@stud.ase.roBareme si subiecte
tancaumaximilian26@stud.ase.roBareme si subiecte
tanrikuludan26@stud.ase.roBareme si subiecte
vanghelescumiruna26@stud.ase.roBareme si subiecte
vedelbogdan26@stud.ase.roBareme si subiecte
vladandrei26@stud.ase.roBareme si subiecte
vlaicuioana26@stud.ase.roBareme si subiecte
zincaanca26@stud.ase.roBareme si subiecte

Examen Cercetari Operationale - Set 2

Student: dumitrumihai26@stud.ase.ro

Rezolvati pe hartie. Aratati etapele algoritmilor.

1. Kruskal

Determinati arborele partial de cost minim si costul total.

ABCDEFGH
Ponderile muchiilor
A – B: 6A – E: 26A – F: 20B – C: 37
B – E: 18B – G: 32C – D: 22C – F: 12
C – G: 5D – G: 10D – H: 16E – F: 31
E – H: 3F – G: 29F – H: 35G – H: 15

Muchii neorientate. La egalitate, ordonare lexicografica.

Intrebari suplimentare (5)

  1. Care este muchia acceptata cu numarul 1? [Raspuns: E-H]
  2. Care este muchia acceptata cu numarul 2? [Raspuns: C-G]
  3. Care este a treia muchie analizata? [Raspuns: A-B]
  4. Care este suma ponderilor primelor trei muchii acceptate? [Raspuns: 14]
  5. Cate componente raman dupa a treia muchie acceptata? [Raspuns: 5]

Arbore minim: E-H, C-G, A-B, D-G, C-F, G-H, B-E | Cost: 69

Urma: E-H (3) DA; C-G (5) DA; A-B (6) DA; D-G (10) DA; C-F (12) DA; G-H (15) DA; D-H (16) NU; B-E (18) DA;

2. Dijkstra

Determinati drumul minim de la S la T si lungimea lui.

SABDCEFGT
Ponderile muchiilor
S – A: 14S – B: 7S – D: 2A – C: 10
A – E: 7A – F: 9B – C: 4B – D: 10
B – F: 5C – E: 12C – G: 2D – F: 9
D – G: 13E – F: 8E – T: 4F – G: 14
F – T: 13G – T: 11

Muchii neorientate. La egalitate, se fixeaza nodul lexicografic mai mic.

Intrebari suplimentare (5)

  1. Care este al 2-lea nod fixat? [Raspuns: D]
  2. Care este al 5-lea nod fixat? [Raspuns: F]
  3. Care este lungimea drumului minim S-T? [Raspuns: 23]
  4. Care este eticheta nodului D dupa prima iteratie? [Raspuns: 2]
  5. Cate arce contine drumul minim S-T? [Raspuns: 4]

Drum: S -> D -> F -> E -> T | Lungime: 23

Ordinea fixarii: S D B C F G 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 / DestinatieD1D2D3Disponibil
S19111113
S251299
S356114
Cerere maxima14914-

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)

  1. Care este capacitatea taieturii minime? [Raspuns: 34]
  2. Care este fluxul final pe arcul S3-D1? [Raspuns: 5]
  3. Cu cat creste fluxul pe primul drum de crestere? [Raspuns: 9]
  4. Care este valoarea fluxului dupa prima crestere? [Raspuns: 9]
  5. Care sunt arcele taieturii minime? [Raspuns: O->S1, O->S2, S3->D1, S3->D2, S3->D3]

Flux maxim: 34 | Taietura minima: 34

SursaD1D2D3
S1409
S2531
S3561

Drumuri de crestere:

  1. O -> S1 -> D1 -> Z; +9; total 9
  2. O -> S1 -> D2 -> Z; +4; total 13
  3. O -> S2 -> D1 -> Z; +5; total 18
  4. O -> S2 -> D2 -> Z; +4; total 22
  5. O -> S3 -> D2 -> Z; +1; total 23
  6. O -> S3 -> D3 -> Z; +1; total 24
  7. O -> S3 -> D1 -> S1 -> D3 -> Z; +5; total 29
  8. O -> S3 -> D2 -> S1 -> D3 -> Z; +4; total 33
  9. O -> S3 -> D2 -> S2 -> D3 -> Z; +1; total 34

Taietura minima: O->S1, O->S2, S3->D1, S3->D2, S3->D3