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 1^st 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...