Mobilité EUt+
Retour

Page du cours ✏️


Special Mathematics I - UTCN
CS3.00

Description
 | Combinatorics (1): counting principles and methods
 | Combinatorics (2): Counting problems using recurrence relations. Recurrences and generating functions.
 | Discrete probabilities (1): Axiomatic definition of probability. General formulas and properties. Interpretation of probabilities. Examples.
 | Discrete probabilities (2): Conditional probabilities. Formula on total probability and Bayes formula.
 | Discrete probabilities (3): Classical probability schemes. Discrete random variables.
 | Discrete probabilities (4): Expected value, variance. Examples of discrete random variables with their expected value and variance.
 | Discrete probabilities (5): Weak law of large numbers. Markov theorem, Chebyshev theorem, Poisson theorem. Examples and applications.
 | Graph theory (1): Directed and undirected graphs, multigraphs: definitions, notations, general properties. Examples of problems which can be modelled with graphs. Euler’s theorem.
 | Graph theory (2): Walks, trails, paths, cycles. Connectivity in graphs. Isomorphic graphs. Subgraphs. Examples of graphs. Operations with graphs. Trees: general properties.
 | Graph theory (3): Trees, directed trees, rooted trees, spanning trees, minimum spanning trees (MST) in weighted graphs. Algorithms for MST: Prim, Kruskal, Edmonds – Chu-Liu.
 | Graph theory (4): DFS (depth-first-search) and BFS (breadth-first- search) trees. Properties of BFS trees. Minimum path, Dijkstra’s algorithm.
 | Graph theory (5): Binary trees, Huffman’s algorithm. Greedy algorithms. Property of matroid.
 | Graph theory (6): Matchings. Bipartite graphs. Matchings in bipartite graphs. Maximum matching and complete matching: Hall’s and Berge’s theorems.
 | Graph theory (7): Transportation networks. Flows and cuts. Max flow min cut theorem.

Crédits ECTS
5

Langue d'enseignement
English

Langue d'examen
English

Langue des supports pédagogiques
English

Acquis d'apprentissage fondamentaux

Entité de gestion (faculté)
Automation and Computer Science Faculty - UTCN