Subject: Discrete Random Structures (17.DOM65L )
Study programmes of the course:
| Type of studies | Title |
|---|---|
| Doctoral Academic Studies | Mathematics in Engineering (Year: 1, Semester: Summer) |
Introduction of advanced discrete probability theory, and its application on discrete structures and combinatorial problems.
Upon completion of the course, the student should master the basic concepts of discrete probability theory, as well as basic methods for its application in solving combinatorial problems. Special attention will be devoted to random graphs.
Basics of the probabilistic method. Applications of linearity of expectation and the first moment method, graph subdivision, Ramsey numbers, independent set of vertices, colorings. The second moment method. Concentration of a parameter. Chernoff bounds. Random graphs. Appearance of a fixed subgraph, connectivity, largest clique, chromatic number, giant component, phase transition. Positional games on random graphs. Pseudo-random graphs. Lovasz-Local-Lemma, applications. Discrepancy, linear and hereditary. Coding, game theory, Liar game. Derandomization, small sample spaces. Random walks. Entropy.
Lectures, with active participation of the students, discussion, etc. A student is supposed to write a seminar paper.
| Authors | Title | Year | Publisher | Language |
|---|---|---|---|---|
| 2005 | English | |||
| 2000 | English | |||
| 2015 | English |
| Course activity | Pre-examination | Obligations | Number of points |
|---|---|---|---|
| Term paper | Yes | Yes | 20.00 |
| Oral part of the exam | No | Yes | 70.00 |
| Lecture attendance | Yes | Yes | 10.00 |
Faculty of Technical Sciences
© 2024. Faculty of Technical Sciences.
Contact:
Address: Trg Dositeja Obradovića 6, 21102 Novi Sad
© 2024. Faculty of Technical Sciences.