- français
- English
Fiches de cours
Advanced information, computation, communication I
CS-101
Enseignant(s) :
Aberer KarlLangue:
English
Remark
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:- Recognize if there is a mistake in a (simple) proof
- Apply general problem-solving techniques
- Recognize the mathematical structures present in applications
- Apply simple recursion and use it to design recursive algorithms
- Apply the tools studied in class to solve problems
- Demonstrate familiarity with mathematical reasoning
- Solve linear recurrences and use generating functions
- Argue about (un)countability
- Formulate complete, clear mathematical proofs
Transversal skills
- Assess one's own level of skill acquisition, and plan their on-going learning goals.
- Continue to work through difficulties or initial failure to find optimal solutions.
- Demonstrate the capacity for critical thinking
Teaching methods
Ex cathedra lectures
Expected student activities
Studying the book, test your understanding by making the exercises, ask questions
Assessment methods
Final exam (100%), 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 (Negar Foroutan, Banaei Mohammadreza). Furthermore, you are always welcome to drop me an email (karl.aberer@epfl.ch) 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, 8th ed, McGraw-Hill 2019. (You should be able to find the pdf on the web.)
Ressources en bibliothèque
Websites
Moodle Link
Dans les plans d'études
- SemestreAutomne
- Forme de l'examenEcrit
- Coefficient
7 - Matière examinée
Advanced information, computation, communication I - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenEcrit
- Coefficient
7 - Matière examinée
Advanced information, computation, communication I - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
- SemestreAutomne
- Forme de l'examenEcrit
- Coefficient
7 - Matière examinée
Advanced information, computation, communication I - Cours
4 Heure(s) hebdo x 14 semaines - Exercices
2 Heure(s) hebdo x 14 semaines
- Semestre
Semaine de référence
Lu | Ma | Me | Je | Ve | |
---|---|---|---|---|---|
8-9 | CO1 | ||||
9-10 | |||||
10-11 | INJ218 INM10 INM11 INM200 INM202 INR219 | ||||
11-12 | |||||
12-13 | |||||
13-14 | |||||
14-15 | |||||
15-16 | |||||
16-17 | CO1 | ||||
17-18 | |||||
18-19 | |||||
19-20 | |||||
20-21 | |||||
21-22 |
légende
- Semestre d'automne
- Session d'hiver
- Semestre de printemps
- Session d'été
- Cours en français
- Cours en anglais
- Cours en allemand