Fiches de cours 2017-2018

PDF
 

Advanced information, computation, communication I

CS-101

Enseignant(s) :

Lenstra Arjen

Langue:

English

Remarque

This course focuses on the foundational, discrete mathematics core of advanced computation.

Summary

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.

Content

I. Mathematical reasoning: propositional logic, propositional functions, quantifiers, rules of inference; this includes very basic logic circuits.
II. Sets and counting: cardinalities, inclusion/exclusion principle, sequences and summations.
III. Algorithms and complexity: basic algorithms, computational complexity, big-O notation and variants, countability.
IV. Number representations such as binary and hexadecimal and (postponed to 2nd semester) basic number theory: modular arithmetic, integer division, prime numbers, hash functions, pseudorandom number generation; applications.
V. Induction and recursion: mathematical induction, recursive definitions and algorithms.
VI. Basic combinatorial analysis: permutations, binomial theorem, basic generating functions.
VII. Basic probability: events, independence, random variables, Bayes' theorem.
VIII. Structure of sets: relations, equivalence relations, power set.
IX. (time permitting) Elementary graph theory: graphs, Euler and Hamilton paths, Dijkstra's algorithm, spanning trees.

Keywords

Propositional logic, counting, complexity, big-O, number representations, sets, matrices, modular arithmetic, induction, basic probabilities, Bayes theorem, combinatorial analysis, recurrences, generating functions, countability, graph theory.

Learning Outcomes

By the end of the course, the student must be able to:

Transversal skills

Teaching methods

Ex cathedra (blackboard) lectures

Expected student activities

Studying the book, test your understanding by making the exercises, ask questions

Assessment methods

Midterm exam (30%) and final exam (70%), both mostly (and possibly exclusively) multiple choice

Supervision

Office hours No
Assistants Yes
Forum No
Others

A list of students assistants and their contact data will be made available on the moodle page for this course, along with an assignment of each registered student to one of the student assistants.

If you have a question, first contact the student assistant assigned to you. If that does not help, contact one of the teaching assistants (Marguerite Delcourt, Dusan Kostic and Benjamin Wesolowski). Furthermore, you are always welcome to stop by at my office (INJ330, no office hours, I'm available when I'm there) for any type of question related to this course or your study at EPFL.

Never hesitate to ask questions before, during or after the lectures!

 

Resources

Bibliography

"Discrete Mathematics and Its Applications", Kenneth H. Rosen, 7th ed, McGraw-Hill 2012. (You should be able to find the pdf on the web.)

Ressources en bibliothèque
Websites
Moodle Link

Dans les plans d'études

Semaine de référence

 LuMaMeJeVe
8-9 CO1   
9-10    
10-11    INJ218
INM10
INM11
INM200
INM202
11-12    
12-13     
13-14     
14-15     
15-16     
16-17    CO1
17-18    
18-19     
19-20     
20-21     
21-22     
 
      Cours
      Exercice, TP
      Projet, autre

légende

  • Semestre d'automne
  • Session d'hiver
  • Semestre de printemps
  • Session d'été
  • Cours en français
  • Cours en anglais
  • Cours en allemand