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
Part I-1: Overview, Brain vs. Computer, aims of course
Binary representation, machine language
- Part I-2:
From assembly language to high-level languages:
scanning, parsing, code generation.
Gates, Switches, and Logic.
- Part I-3:
gate-level arithmetic: addition, subtraction, multiplication
Gate-level Memory; Architecture - putting elements together
II - What is computation?
Summary of Part II
- Part II-1:
What is computation, algorithic tasks.
Computability, Tiling problem, halting problem.
- Part II-2:
Undecidability of halting problem (with proof).
Universal Turing Machine.
- Part II - 3:
Computable problems: order of complexity;
search and sort algorithms
Exponential time, intractable problems, NP complete problems,
- Part II-4:
Dynamic Programming: games, state-value, path-planning.
Dynamic Programming: sequence alignment, bioinformatics,
III- What is information?
Summary of Part III
week 8 - this part is taught in week 11 (because of a Thursday holiday)
week 9 -
- Part III-1:
basic questions; idea of coding
Parity code, Hamming code,
Shannon's noisy channel coding theorem
- Part III-2:
Information theory: Entropy,
probability of typical sequence
Entropy, Huffman graphs,
Shannon's source coding theorem
week 11 - in these lectures the contents of week 8 are integrated
- Part II-3:
Information as entropy reduction;
noisy channel coding.
- Part III-4:
Compression: Huffman code; Lempel Ziv code;
Entropy as lower bound; compression in practice.
What is intelligence?
- Part IV -1:
language recognition, grammar and semantics, knowledge representation;
graphs, full search and heuristic search, expert
systems and games;
- Part IV -2
Braitenberg vehicles, obstacle avoidance,
reflex based robots, clustering;
main page of course: Informatique II -->