logo Insalogo Insa

Fundamentals in Computer Science


Program (detailed contents)


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.


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:




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...