Informatique II/Computer Science II for Life Scientists

• 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
  
  

week 4

• 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, fast certification
  

• Part II-4: Dynamic Programming: games, state-value, path-planning.
  Dynamic Programming: sequence alignment, bioinformatics, Needleman-Wunsch algo
  

week 8 - this part is taught in week 11 (because of a Thursday holiday)

• Part III-1: Information theory: 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
  

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

• 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;