Fundamentals in Computer Science
Presentation
Program (detailed contents)
[FP-Caml]
The students undergo practical work and assessments dedicated to basic concepts used in functional programming (curried functions, closures, pattern matching, recursion, variant data types, parametric polymorphism, …) before working on a small programming project.
[FL-Prolog part]
-Propositionnal logic
- Syntax and semantics
- Truth table method
- Method of analytic tableaux
- Hilbert deduction system – derivations and proofs
First order predicate calculus
- Resolution principle and refutation based demonstration
- Prenex normal form, skolemization, most general unifiers
- Herbrand Base, Herbrand universe
Logic programming in Prolog
- Linear resolution for definite clauses
- Negation by failure
- Recursive clauses
- Main built-in Predicates
- Applications and extensions
[AA part]
Main principles of generic algorithms are presented. Their features are compared, taking into account classes of problems, optimization strategies and complexity.
Objectives
Heterogeneous course grouping three parts :
- Functionnal Programming – Caml (“FP- Caml”)
- Logic and Prolog Logic programming (“FL- Prolog”)
- Advanced Algorithmics (« AA »)
At the end of this module, the student will understand and will be able to explain:
[FP-Caml]
Students are expected to:
- understand and write pure functional programs,
- design recursive functions to iterate over recursive data types,
- define variants or parameterized types,
- more generally think in terms of higher-order functions in order to write reusable codes.
- describe the semantics of simple lambda terms
- have a basic theoretical understanding of the type systems theory
[FL-Prolog part]
- translate natural language statements into formulas of propositional logic and of 1st order predicate calculus
- apply several methods in order to check the validity and the consistency of some formulas
- explain the fundamentals of Prolog language and logic programming.
- design a Prolog program and trace its execution
[AA Part]
Some paradigms in algorithmics for discrete optimization :
- Exhaustive enumeration
- Divide and Conquer
- Dynamic Programming
- Greedy Algorithms
Needed prerequisite
First and second year courses on Algorithms & Programming
Form of assessment
The evaluation of outcome prior learning is made as a continuous training during the semester. According ot the teaching, the assessment will be different: as a written exam, an oral exam, a record, a written report, peers review...