Předmět Automatizované řešení úloh s omezeními (ARUO)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu ARUO - Automatizované řešení úloh s omezeními, Vysoká škola báňská - Technická univerzita Ostrava (VŠB-TU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Student po úspěšném absolvování předmětu:- rozumí základním pojmům z oblasti "constraint processing"- umí klasifikovat praktické problémy spadající do dané oblasti- umí k praktickému problému nalézt relevantní proměnné a exaktně zformulovat příslušná omezení- má přehled o obecných metodách řešení- má přehled o dostupných softwarových nástrojích pro řešení úloh s omezeními- má zkušenost s vyřešením praktického problému s pomocí jednoho z těchto nástrojů
Osnova
Osnova přednášek:1. Praktické příklady problémů s omezeními a nástin obecných metod řešení. Exaktní formulace problémů ilustrovanána příkladu Huffmanovo-Clowesova ohodnocení scény.2. Sítě omezení a jejich grafové reprezentace, speciální tvary sítí.3. Šíření omezení (hranová konzistentnost, globální omezení), příslušné algoritmy.4. Řešení úloh pomocí backtrackingu, algoritmy pro zlepšení dopředné fáze backtrackingu.5. Algoritmy pro zlepšení zpětné fáze backtrackingu.6. Problém SAT, jeho NP-úplnost, využití SATu při řešení úloh s omezeními.7. Polynomiálně řešitelné varianty problému SAT, příslušné polynomiální algoritmy.8. Řešení obecného problému SAT, algoritmy DPLL, stochastické, ...9. Optimalizační problémy, využití backtrackingu (Branch and Bound), metody eliminace košíků.10. Využití pravděpodobnostních sítí pro nejistá omezení (na příkladu medicinských diagnóz).11. Plánování, rozvrhování - možná paradigmata, varianty kriteriální funkce.12. Aproximační algoritmy (na příkladu problému obchodního cestujícího).13. Shrnutí učiva, stručný přehled dalších možných témat z oblasti úloh s omezeními.Osnova cvičení na počítačové učebně:1. Procvičení exaktní formulace problémů. Úvodní seznámení s nástrojem Gecode - řešičem úloh s omezeními.2. Gecode - tvorba modelu problému.3. Gecode - využití různých metod prohledávání implementovaných v tomto nástroji.4. Formulace problému ve formě vstupu po řešič SAT. Úvodní seznámení s MiniSAT - jednoduchým řešičem SAT.5. Řešení praktických problémů za pomocí MiniSAT.6. Stochastické metody prohledávání. Práce se stochastickými řešiči SAT.7. Nástroje pro řešení SAT při tvorbě vlastních programů.8. Další dostupné řešiče SAT, jejich společné a odlišné rysy, přehled formátů vstupních souborů pro řešiče SAT.9.-10. Jiné dostupné softwarové nástroje pro řešení úloh s omezeními, jejich přehled, možnosti, vlastnosti.11. Konzultace domácích úkolů.12. Odevzdání domácích úkolů.13. Písemný zápočtový test.
Literatura
- Rina Dechter: Constraint Processing, Morgan Kaufmann, 2003
Požadavky
Žádné
Garant
Ing. Martin Kot, Ph.D.
Vyučující
Ing. Martin Kot, Ph.D.doc. Ing. Zdeněk Sawa, Ph.D.