Font size
WorksheetsProg2
Total questions: 16
Worksheet time: 3hrs 40mins
Milyen típusú algoritmusra igaz a következő kijelentés: "Élj a mának"
Backtracking
Mohó / Greedy
Dinamikus
Branch and Bound
Egy n csomópontú fa esetén a fa csomópontjainak száma:
n
n(n+1)/2
2^n
2^(n) -1
Egy n csomópontú fa esetén a fa részfeladatainak száma:
n
n(n+1)/2
2^n
2^(n) -1
Milyen típusú algoritmusra igaz a következő kijelentés: "Legbizonyosabban úgy találod el a verebet, ha ágyúval lősz a fára"
Backtracking
Mohó / Greedy
Dinamikus
Branch and Bound
Az x^n=x^(n/2)*x^(n/2) felbontás hatékonyabb algoritmust eredményez, mint az x n=x^(n-1)*x. Ez milyen típusú algoritmus?
Divide-and-conquer / Oszd meg és uralkodj
Decrease-and-conquer / Kicsinyitsd és uralkodj
Transform-and-conquer / Alakítsd át és uralkodj
Backtracking
Adott lkkt(m,n) = (m*n) / lnko(m,n).
Ez milyen típusú algoritmus?
Divide-and-conquer / Oszd meg és uralkodj
Decrease-and-conquer / Kicsinyitsd és uralkodj
Transform-and-conquer / Alakítsd át és uralkodj
Backtracking
DFS (mélységi bejárás) esetén mi lesz a bejárás végeredménye az adott irányított gráfban?
1, 2, 5, 7, 8, 3, 6, 9, 11, 12, 15, 19, 20, 13, 16, 21, 22, 14, 17, 18, 10, 4
1, 2, 5, 7, 8, 3, 6, 9, 11, 12, 19, 15, 20, 13, 16, 21, 22, 14, 17, 18, 10, 4
1, 2, 5, 7, 8, 12, 11, 3, 6, 9, 18, 14, 17, 10, 13, 16, 21, 22, 20, 15, 19, 4
1, 2, 4, 7, 8, 12, 11, 3, 6, 9, 18, 14, 15, 10, 13, 16, 21, 22, 20, 17, 19, 5
DFS (mélységi bejárás) esetén mi lesz a bejárás végeredménye az adott irányítatlan gráfban?
1, 2, 5, 7, 8, 3, 6, 9, 11, 12, 15, 19, 20, 13, 16, 21, 22, 14, 17, 18, 10, 4
1, 2, 5, 7, 8, 12, 11, 3, 6, 9, 18, 14, 17, 10, 13, 16, 21, 22, 20, 15, 19, 4
1, 2, 5, 7, 8, 3, 6, 9, 11, 12, 19, 15, 20, 13, 16, 21, 22, 14, 17, 18, 10, 4
1, 2, 4, 7, 8, 12, 11, 3, 6, 9, 18, 14, 15, 10, 13, 16, 21, 22, 20, 17, 19, 5
BFS (szélességi bejárás) esetén mi lesz a bejárás végeredménye az adott irányított gráfban?
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20, 16, 17, 18, 19, 21, 22
1, 2, 5, 7, 8, 3, 6, 9, 11, 12, 19, 15, 20, 13, 16, 21, 22, 14, 17, 18, 10, 4
1, 2, 3, 4, 8, 5, 6, 10, 11, 12, 7, 9, 13, 14, 20, 15, 19, 18, 16, 22, 17, 21
1, 2, 4, 7, 8, 12, 11, 3, 6, 9, 18, 14, 15, 10, 13, 16, 21, 22, 20, 17, 19, 5
BFS (szélességi bejárás) esetén mi lesz a bejárás végeredménye az adott irányítatlan gráfban?
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 20, 16, 17, 18, 19, 21, 22
1, 2, 5, 7, 8, 3, 6, 9, 11, 12, 19, 15, 20, 13, 16, 21, 22, 14, 17, 18, 10, 4
1, 2, 3, 4, 8, 5, 6, 10, 11, 12, 7, 9, 13, 14, 20, 15, 19, 18, 16, 22, 17, 21
1, 2, 4, 7, 8, 12, 11, 3, 6, 9, 18, 14, 15, 10, 13, 16, 21, 22, 20, 17, 19, 5
Mi igaz a Backtracking eljárásra? / Mikor használjuk?
Amikor a feladat összes megoldásában érdekeltek vagyunk
Gyakran „nyers erő” megközelítésnek számít
Optimalizálási feladatok: generáljuk az összes potenciális megoldást, és optimumot keressük ezek között
Az igéretes függvény a megoldás kulcsa
Igaz-e a következő
állítás?
Egy gráf akkor és csak akkor Euler-gráf, ha összefüggő és bármely csúcsának a foka páros.
Igen
Nem
Jelöld be a helyes állitásokat.
A Hamilton-út a gráf minden pontját tartalmazza (egyszer és csakis egyszer).
A Hamilton-kör a gráf minden pontját többször is tartalmazhatja.
Ha egy gráf tartalmaz Hamilton-kört akkor Hamilton-gráfnak nevezzük.
Mi igaz a Mohó stratégiára?
Jelöld be a helyes állitásokat.
Mindig az adott lépésben optimálisnak látszó (legígéretesebb) döntést hozzuk – Nem számolva az esetleges hosszú távú következményekkel
Úgy gondolkodunk, hogy a lokális optimum majd globális optimumhoz vezet
A mohó megoldás mindig eredményes megoldáshoz vezet.
Milyen típusú algoritmusra igaz a következő kijelentés: „Minden napnak elég a maga baja” „Amit vet az ember, azt fogja aratni is”
Backtracking
Mohó / Greedy
Dinamikus
Branch and Bound
Jelöld be a minimális feszitőfa tulajdonságait.
Ha egy gráfban minden él költsége különböző, akkor a feszítő fa egyértelmű.
Ha C kör a gráfban, akkor a legnagyobb költségű éle tartozik egy minimális költségű feszítő fához.
Duálisan, ha C vágás, akkor a legkisebb költségű éle az összes minimális költségű feszítő fának.
Ha a gráfban van egy egyértelmű legkisebb költségű él, akkor a gráf minimális költségű feszítő fáinak mindegyike tartalmazni fogja ezt az élt.
