Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    High Efficiency Declarative Programming Laboratory

    A tantárgy neve magyarul / Name of the subject in Hungarian: Nagyhatékonyságú deklaratív programozás laboratórium

    Last updated: 2015. november 30.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZMB01 3 0/0/3/f 4  
    3. Course coordinator and department Dr. Mann Zoltán Ádám, Számítástudományi és Információelméleti Tanszék
    Web page of the course
    4. Instructors
    Dr. Mann Zoltán Ádám
    associate professor
    Department of Computer Science and Information Theory
    Dr. Szeredi Péter
    Department of Computer Science and Information Theory
    5. Required knowledge Basic knowledge of the Prolog programming language
    6. Pre-requisites
    NEM ( TárgyEredmény( "BMEVISZM232" , "jegy" , _ ) >= 2
    TárgyEredmény("BMEVISZM232", "FELVETEL", AktualisFelev()) > 0)

    A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

    A kötelező előtanulmányi rendek grafikus formában itt láthatók.

    Declarative Programming
    7. Objectives, learning outcomes and obtained knowledge

    Further development of the knowledge gathered in the BSc course "Declarative Programming," extending it to the area of constraint logic programming (CLP). Understanding the theoretical foundations and practical implementations of CLP, learning and exercising the methods of constraint programming.

    8. Synopsis
    1. CLP fundamentals (the CLP(X) scheme, examples), advanced Prolog concepts necessary for implementing CLP (blocking, the concept of coroutining, handling coroutines in Prolog, examples of coroutines, customized output of terms)
    2. CLP(MiniNat) case study (a quasi-CLP language for handling natural numbers), implementation of CLP(MiniNat) with the learned advanced Prolog constructs, announcement of 1st homework exercise
    3. The clpq and clpr libraries of SICStus Prolog, their usage and the basics of their operation, examples for the usage and operation of the libraries, case study: perfect rectangles
    4. Theory of constraint logic programming (CLP syntax, declarative semantics, procedural semantics, the inference process). The clpb library of SICStus Prolog (usage and operation of the library, examples)
    5. Fundamentals of CLP(FD), introduction to using the clpfd library of SICStus Prolog, theoretical background: constraint satisfaction problems (CSP), simple and composite constraints, membership constraints, arithmetic constraints, examples of using the clpfd library
    6. Levels of consistency and pruning, constraint execution, classic CSP problems (zebra problem, n queens problem, magic sequences), redundant constraints. Announcement of homework assignment
    7. Reification, propositional constraints, entailment of constraints, global arithmetic constraints, clpfd reflection predicates, FD sets, labeling (labeling predicates, labeling options, customizing labeling), announcement of the 2nd homework exercise
    8. User-defined constraints: global constraints and FD predicates. Details of defining global constraints, syntax and semantics of the hook predicate for pruning. Announcement of the 3rd homework exercise
    9. FD predicates: indexicals and ranges, further FD clauses necessary for reification, interpretation of indexicals, translating constraints to indexicals, announcement of the 4th homework exercise
    10. Built-in combinatorial constraints of the SICStus clpfd library: counting and distinctness, defining arbitrary relations (with the help of pairs, graphs, tables, automata), graph constraints, scheduling, packing. Examples for using the available constraints
    11. Debugging CLP(FD) programs with the help of the FDBG library (usage, customizing, developing custom visualizers)
    12. Advanced CLP(FD) case studies (square packing, torpedo, dominoes): modeling, selecting the variables and the constraints, efficient search
    13. CHR (Constraint Handling Rules): a generic constraint programming library, definition and execution of CHR rules, examples for using CHR
    14. Summary, buffer
    9. Method of instruction

    Lectures + lab work. In the lectures, the above topics are presented and discussed. In the lab part, students solve theoretical as well as programming exercises related to the current topic.

    10. Assessment

    During the lecture period:

    Solving the 4 homework exercises and the homework assignment. Each homework exercise counts 15%, the assignment counts 40% towards the final grade. Solutions to the homework exercises are due in two weeks after the announcement of the exercise; the solution of the assignment is to be submitted by the last day of the lecture period.

    During the exam period:


    11. Recaps

    Belated homework may be submitted by the end of the week after the lecture period, for a score reduced by 20%.

    12. Consultations By appointment
    13. References, textbooks and resources

    Course material: (in Hungarian)


    Kim Mariott, Peter J. Stuckey. Programming with Constraints: an Introduction. MIT Press, 1998.

    Pascal Van Hentenryck. Constraint Satisfaction in Logic Programming. MIT Press, 1989.

    M. Carlsson, G. Ottosson, and B. Carlson. An open-ended finite domain constraint solver. In: Programming Languages: Implementations, Logics, and Programs, pp. 191–206, 1997.

    A. Bockmayr and J. Hooker. Constraint programming. In: Handbook of Discrete Optimization, K. Aardal, G. Nemhauser, and R. Weismantel, Eds., pp. 559–600, 2005.

    14. Required learning hours and assignment
    In class
    Preparation for classes
    Preparation for midterms
    Reading assignment 24
    Preparation for final
    Total 120
    15. Syllabus prepared by
    Dr. Mann Zoltán Ádám
    associate professor
    Department of Computer Science and Information Theory
    Dr. Szeredi Péter
    Department of Computer Science and Information Theory