Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licență
FISA DISCIPLINEI
| MID0024 | Programare bazată pe restricţii |
| Titularii de disciplina |
Prof. Dr. POP Horia Florin, hfpop cs.ubbcluj.ro |
| Obiective |
|
Multe probleme computationale pot fi descrise ca restrictii impuse asupra solutiilor posibile. Programarea Bazata pe Restrictii (Constraint Programming) este o tehnica de rezolvarea problemelor care lucreaza prin incorporarea acestor restrictii într-un mediu de programare. Programarea Bazata pe Restrictii opereaza cu metode din inteligenta artificiala, programarea logica si cercetarile operationale. A fost aplicata cu succes în mai multe domenii, precum planificare, lingvistica computationala si biologie computationala.
Scopul acestui curs este de a crea o întelegere a conceptelor fundamentale din domeniul programarii bazate pe restrictii; de a dezvolta deprinderi în modelarea si rezolvarea problemelor de acest tip; de a dezvolta deprinderi de a folosi tehnici avansate de realizare a algoritmilor. Cursul are atât o componenta teoretica, orientata pe cunoasterea domeniului si a problematicilor relevante, precum si o componenta practica, orientata pe studiul diferitelor probleme tipice, sisteme, platforme sau biblioteci de programare bazata pe restrictii. |
| Continutul |
|
1. Introducere (curs 1)
1.1 Ce este o problema de satisfacerea restrictiilor? 1.2 Definitia formala a CSP 1.3 Reprezentarea restrictiilor si CSP binare 1.4 Concepte despre grafe 1.5 Exemple si aplicatii ale CSP 1.6 Programare bazata pe restrictii 2. Rezolvarea CSP - Trecere în revista (curs 2) 2.1 Introducere 2.2 Reducerea problemei 2.3 Cautarea solutiilor 2.4 Sinteza solutiilor 2.5 Caracteristicile diferitelor probleme de CSP 3. Concepte fundamentale ale CSP (curs 3) 3.1 Introducere 3.2 Concepte privind satisfiabilitatea si consistenta 3.3 Legatura dintre consistenta si satisfiabilitate 3.4 (i, j)-consistenta 3.5 Redundanta restrictiilor 3.6 Alte concepte despre grafe 4. Reducerea problemei (curs 4, 5) 4.1 Introducere 4.2 Algoritmi care realizeaza consistenta de nod (NC) si arc (AC) 4.3 Algoritmi care realizeaza consistenta de drum (PC) 4.4 Post-conditii pentru algoritmii PC 4.5 Algoritm pentru realizarea k-consistentei 4.6 Consistenta adaptiva 4.7 Realizarea consistentei în mod paralel/distribuit 5. Strategii de cautare de baza pentru rezolvarea CSP (curs 6, 7) 5.1 Introducere 5.2 Strategii generale de cautare 5.3 Strategii look-ahead 5.4 Strategii care preiau informatii în timpul cautarii 5.5 Algoritmi hibrizi si Truth maintenance 5.6 Compararea algoritmilor 6. Ordini de cautare în CSPs (curs 8, 9) 6.1 Introducere 6.2 Ordonarea variabilelor în cautare 6.3 Ordonarea valorilor în cautare 6.4 Ordonarea inferentelor în cautare 7. Exploatarea caracteristicilor specifice problemelor (curs 10, 11) 7.1 Introducere 7.2 Descompunerea problemei 7.3 Recunoasterea si cautarea în k-arbori 7.4 Reducerea problemei prin eliminarea restrictiilor redundante 7.5 Cycle-cutsets, Multimi stabile si Pseudo-Tree-Search 7.6 Metoda Tree-clustering 7.7 j-width si cautare Backtrack-bounded 7.8 CSP cu restrictii numerice binare 8. Metode de cautare stochastica pentru CSP (curs 12) 8.1 Introducere 8.2 Hill-climbing 8.3 Abordari conexioniste 9. Sinteza solutiilor (curs 13) 9.1 Introducere 9.2 Algoritmul lui Freuder pentru sinteza solutiei 9.3 Algoritmul de invazie a lui Seidel 9.4 Algoritmul Essex pentru sinteza solutiei 9.5 Cand se face sinteza solutiilor 10. Optimizare in CSP (curs 13) 10.1 Introducere 10.2 Problema de optimizare prin satisfacerea restrictiilor 10.3 Problema partiala de satisfacerea restrictiilor Lucrare scrisa (curs 14) Planificarea laboratoarelor 1. (Tema 1) Rezolvarea unor probleme tipice de CSP în C++ si Java (lab 1-3) 2. (Tema 2) Implementarea si testarea metodelor din cursurile 3-5 si utilizarea functiilor pentru abordarea problemelor de la tema 1 (lab 4-6) 3. (Tema 3) Implementarea si testarea metodelor din cursurile 6-9 si utilizarea functiilor pentru abordarea problemelor de la tema 1 (lab 7-9) 4. (Tema 4) Instalarea si testarea unor biblioteci de CSP in C++ si Java (lab 10-11) 5. (Tema 5) Rezolvarea unor probleme tipice de CSP folosind bibliotecile instalate la tema 4 (lab 12-14) |
| Bibliografie |
|
[1] Edward P.K. Tsang, Foundations of Constraint Satisfaction, Academic Press, London and San Diego, 1993, ISBN 0-12-701610-4, http://cswww.essex.ac.uk/CSP/edward/FCS.html
[2] Roman Bartak, On-line Guide to Constraint Programming, http://ktiml.mff.cuni.cz/~bartak/constraints/ [3] Grzegorz Kondrak, A Theoretical Evaluation of Selected Backtracking Algorithms, University of Alberta, 1994 Optional references [1] Constraint programming: introduction, http://www.aiai.ed.ac.uk/links/constr.html [2] Some challenges for constraint programming http://www.clip.dia.fi.upm.es/~herme/con.html (ACM Computing Surveys) [3] Visual constraint programming tool: Oz explorer http://citeseer.nj.nec.com/schulte97oz.html [4] Algorithms for constraint satisfaction problems: A survey AI magazine, 1992, 13/1 [5] Constraint satisfaction algorithms, BA Nadel, Computational Intelligence, Vol 5, 1989, pp 188-224. [6] Constraint satisfaction, AK Mackworth, Encyclopaedia of AI, Volume I, Stuart C Shapiro (ed), John Wiley and Sons, 1987, pp 205-211. [7] Partial constraint satisfaction, EC Freuder and RJ Wallace, AI, vol 58, 1992, pp 21-70. (special issue on constraint based reasoning). [8] Rina Dechter, Constraint Processing. Morgan Kaufmann Publishers, 2003. [9] Kim Marriott and Peter J. Stuckey, Programming with Constraints. An Introduction. The MIT Press, 1998. [10] Thom Frühwirth and Slim Abdennadher, Essentials of Constraint Programming. Springer-Verlag, 2003. [11] Krzystof R. Apt, Principles of Constraint Programming. Cambridge University Press, 2003. [12] Philippe Baptiste, Claude Le Pape and Wim Nuijten, Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Kluwer Academic Publishers, 2001. |
| Evaluare |
|
Nota finala se determina în felul urmator: 20% activitatea de laborator (nota A); 20% documentatiile, programele si proiectele realizate (nota L); 60% lucrarea scrisa (nota F; curs 14).
Sunt valabile regulamentele oficiale ale universitatii în legatura cu prezenta studentilor la activitatile didactice si cu cazurile de copiat si plagiat. Absentele nemotivate de pâna la 20% din activitatea de laborator se accepta fara obiectii, dar întârzierea în predarea lucrarilor de laborator se penalizeaza. Lucrarile de laborator se predau în forma scrisa la sfârsitul orei de laborator când predarea este planificata. Promovarea examenului este este conditionata de cerinta ca note F sa fie cel putin 5. |
| Legaturi: | Syllabus-urile tuturor disciplinelor Versiunea in limba engleza a acestei discipline Versiunea in format rtf a acestei discipline |