Informatique II
Informatique II/Computer Science II for Life Scientists
Copies of all slides are available at the `vente de cours'
I  What happens in a computer?
Summary of Part I
week 1

Part I1: Overview, Brain vs. Computer, aims of course
Binary representation, machine language
week 2
 Part I2:
From assembly language to highlevel languages:
scanning, parsing, code generation.
Gates, Switches, and Logic.
week 3
 Part I3:
gatelevel arithmetic: addition, subtraction, multiplication
Gatelevel Memory; Architecture  putting elements together
II  What is computation?
Summary of Part II
week 4
 Part II1:
What is computation, algorithic tasks.
Computability, Tiling problem, halting problem.
week 5
 Part II2:
Undecidability of halting problem (with proof).
Universal Turing Machine.
week 6
 Part II  3:
Computable problems: order of complexity;
search and sort algorithms
Exponential time, intractable problems, NP complete problems,
fast certification
week 7
 Part II4:
Dynamic Programming: games, statevalue, pathplanning.
Dynamic Programming: sequence alignment, bioinformatics,
NeedlemanWunsch algo
III What is information?
Summary of Part III
week 8  this part is taught in week 11 (because of a Thursday holiday)
 Part III1:
Information theory:
basic questions; idea of coding
Parity code, Hamming code,
Shannon's noisy channel coding theorem
week 9 
 Part III2:
Information theory: Entropy,
probability of typical sequence
Entropy, Huffman graphs,
Shannon's source coding theorem
week10
 Part II3:
Information as entropy reduction;
noisy channel coding.
week 11  in these lectures the contents of week 8 are integrated
 Part III4:
Compression: Huffman code; Lempel Ziv code;
Entropy as lower bound; compression in practice.
What is intelligence?
week 12
 Part IV 1:
Artificial Intelligence:
basic questions;
language recognition, grammar and semantics, knowledge representation;
graphs, full search and heuristic search, expert
systems and games;
week 13
 Part IV 2
Pattern recognition;
Turing Test;
Animal intelligence,
Braitenberg vehicles, obstacle avoidance,
reflex based robots, clustering;
back to
main page of course: Informatique II >