Automated Reasoning, A.A. 2020/21


BLENDED (october) and on-line COURSE - MATERIAL ON MICROSOFT TEAMS

MON 8:30-10:30, room A013
WED 8:30-10:30, room A013
(general material and references HERE)

Program

  1. 28/09/2020. Course Introduction. The role of knowlegde representation and problem solving in Artificial Intelligence. Motivation lectures By Peter Stuckey and by By Pascal Van Hentenryck. A remark by Michael Trick (see slides on Teams) See ICLP2020 invided talks on FACEBOOK ICLP2020
  2. 30/09/2020. CSP/COP and their equivalence. NP hardness of CSP. Search space and naive search techniques. SAT solving. Examples of encoding. DIMACS format. Use MiniSAT or clingo as a SAT solver. Sudoku solved by SAT as a sat solver (example of instance).
  3. 5/10/2020. Brief introduction to Local Search. Solving COPs with (Integer) Linear Programming.
    Constraint rewriting rules. Proof rules: domain reduction rules, Transformation, and introduction rules.
  4. 7/10/2020. Derivation and constraint propagation. Node consistency. Arc consistency. Bounds Consistency. Directional Arc/Bounds Consistency. Hyperarc (and Bounds) consistency. Path Consistency.
  5. 12/10/2020. Constraint Solving. SAT solving: unit propagation and DPLL. Constrained Search: prop labeling trees. MINIZINC. Minizinc (download the tutorial).
  6. 14/10/2020. Minizinc modeling: Simple examples: Minizinc model of N-Queens, some alphametic problems, Magic Squares, Schur Numbers (Ramsey) problems.
  7. 19/10/2020. Brief analysis of the FlatZinc code. Code factoring using predicactes. Sudoku, Knapsack, Hamming codes: breaking symmetries, Timetabling.
  8. 21/10/2020. Two examples from Biology: Haplotype Inference and (simplified) Protein Folding.
  9. 26/10/2020. Advanced search strategies. Restart. LNS. Application to the protein folding encoding. Global constraints. Global constraints catalog. TSP. (Cumulative) Scheduling.
  10. 28/10/2020. Global constraints. Hyper arc consistency and its asymptotical complexity. All different constraints. Bipartite Graph and matchings. Berge and Regin Theorems. Maximum matchings.

    ON LINE

  11. 02/11/2020. Polynomial propagation of the alldifferent constraint.

    Historical Introduction to Logic Programming for Knowledge Representation and Reasoning.

  12. 4/11/2020. Syntax of Logic Programming: terms, atoms, rules. Intuitive semantics of rules. Logic Programs. ``finite world'' programs and infinite programs. Examples in Prolog.
  13. 9/11/2020. Semantics of Logic (Programming). Universes, Interpretations, Models, Logical Consequences. Herbrand models. Minimum model of Definite Clause Programs. Fixpoint general results. Minimum and Maximum fixpoint of the TP operator.
  14. 11/11/2020. Denotational Semantics. Fixpoint general results. Minimum and Maximum fixpoint of the TP operator. General programs. The loss of monotonicity.
  15. 16/11/2020. Completion of a general program and its Herbrand models. 3-valued semantics. The notion of stable model. Examples. Constraints (or denials).
  16. 18/11/2020. Encoding non-determinism. The problem of existence of a stable model. NP completeness main result. ASP solving pipeline and main solvers. Grounding. Domain predicates and range restrictedness.
  17. 23/11/2020. Programming in ASP. Intervals, Cardinality Constraints, and Aggregates. Encoding CSP with ASP: N-Queens, k-coloring, Magic Square, Telethon schedule ASP encodings)
  18. 25/11/2020. Encoding CSP with ASP: Schur Numbers, Hamilton Circuit, Hamming Codes, Sudoku, friendly football Tournament, Haplotype inference, Protein Structure Prediction.
  19. 30/11/2020. Commonsense reasoning. An introduction by Baral and Gelfond. Automated reasoning with ASP. wolf-cabbage-goat puzzle, the zebra puzzle.
  20. 2/12/2020. Automated reasoning with ASP. "jobs puzzle", the three barrels, the Hanoi Tower, Lloyd's puzzle, and other games. Representing ans solving Smullyan's logic puzzles (ASP encodings)
  21. 7/12/2020. KR languages, expressivity and complexity. Definitite, General, Disjunctive programs. The notions of Stable model and the complexity ot establishing its existence.
  22. 9/12/2019. Action Description Languages. Brief history. Syntax and semantics of the language B. Static and Dynamuc caudak laws. Examples
  23. 14/01/2020. Complexity results. The language B and its encoding in ASP and in SAT/Constraint Programming. For other material, see This page and in particular, This one)
  24. 16/12/2020?. Introduction to multiagent epistemic planning and its encoding in ASP (lesson in collaboration with Francesco Fabiano)
  25. 21/12/2020?. ASP SOLVING. A quick view inside ASP solvers. Clause Learning basics. Unfounded Sets. (lesson in collaboration with Andrea Formisano)
``Recent'' work of the CLPLAB on Constraint and Logic Programming. Some slides of the "recent" presentations of the works at meetings.
Home Page