- Nazwa przedmiotu:
- Introduction to Discrete Mathematics
- Koordynator przedmiotu:
- Tomasz Traczyk
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia I stopnia
- Program:
- Computer Science
- Grupa przedmiotów:
- Technical Courses
- Kod przedmiotu:
- EIDM
- Semestr nominalny:
- 1 / rok ak. 2015/2016
- Liczba punktów ECTS:
- 6
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 60 hrs total of supervised learning, split into 30 hrs lectures and 30 hrs tutorials. Another 60 to 80 hrs (estimated) and average student will have to devote to the subject in order to:
- memorize necessary definitions, theorems, formulas (20-30 hrs)
- practice problem solving, doing homework problems and developing skills necessary to master the material covered. (40-50 hrs)
Total: 120-140
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 2
- Język prowadzenia zajęć:
- angielski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- 2
- Formy zajęć i ich wymiar w semestrze:
-
- Wykład30h
- Ćwiczenia30h
- Laboratorium0h
- Projekt0h
- Lekcje komputerowe0h
- Wymagania wstępne:
- None
- Limit liczby studentów:
- 60
- Cel przedmiotu:
- Students should acquire working knowledge of mathematical logic and set algebra, combinatorial analysis, graph theory and recursion.
- Treści kształcenia:
- Introduction (4h): Propositions, prepositional calculus, tautologies. Propositional functions and quantifiers. Sets, operations on sets, generalized union and intersection of sets
Relations (6h): Cartesian product of sets. Relations as subsets of the Cartesian product of sets. Equivalence relations, equivalence classes. Ordering relations, partial and total orders, minimal, maximal, least and largest elements, chains and antichains. Well ordered sets. The Induction Theorem.
Congruence modulo n (4h): Remainder lemma, residues modulo n. Addition and multiplication modulo n. Properties of addition and multiplication mod n.
Functions (4h) Functions as relations. One-to-one and onto functions. Image and inverse image of a set by a function. Order preserving (increasing) functions. The concept of a fixed point.
Combinatorics (6h): Basic combinatorial principles. Newton binomial formula. Pigeon-hole principle. Inclusion-exclusion principle. Generating functions. Number of subsets of a set, number of fixed-size subsets, number of permutations, number of functions from one set into another.
Graphs (4): Graphs, subgraphs, induced and spanning subgraphs, paths and cycles. Connectivity, Menger theorem. Eulerian graphs, Hamilton graphs. Planar graphs, Kuratowski theorem. Coloring of graphs.
Recurrence relation (2): Recursive equations. Recursive methods in enumeration.
- Metody oceny:
- Two midterm exams for 20 points each.
A final exam worth 50 points.
Students are expected to show activity during classes. They can get up to 10 points for that.
The points are summed-up, and the student is awarded a
C for 51 points,
C+ for 61,
B for 71,
B+ for 81 and
A for 91 points or more
- Egzamin:
- tak
- Literatura:
- To be chosen
- Witryna www przedmiotu:
- http://studia.elka.pw.edu.pl/
- Uwagi:
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Efekt EIDMA_W01
- Students know the basic concepts of discrete mathematics, such as combinatorial objects including combinations, and permutations, and graphs.
Weryfikacja: Two written midterm tests and a written final exam
Powiązane efekty kierunkowe:
K_W01
Powiązane efekty obszarowe:
T1A_W01, T1A_W02, T1A_W03, T1A_W07
Profil ogólnoakademicki - umiejętności
- Efekt EIDMA_U01
- The student can enumerate basic combinatorial objects, i.e. subsets, permutations, sequences and functions. They can use generating functions to enumerate more complex sets. They are able to solve simple recursive equations.
Weryfikacja: Two written midterm tests and a written final exam
Powiązane efekty kierunkowe:
K_U02
Powiązane efekty obszarowe:
T1A_U02
- Efekt EIDMA_U02
- Students can verify connectivity of a graph, find an Eulerian cycle, use Kruskal's algorithm to find a cheapest spanning tree in a graph.
Weryfikacja: Two written midterm tests and a written final exam
Powiązane efekty kierunkowe:
K_U02
Powiązane efekty obszarowe:
T1A_U02