Discrete Mathematics and Graphs, academic year 2017/18
Content:
Lectures:
- Foundation of Propositional logic, Boolean calculus.
- Foundation of Predicate logic, quantifiers, interpretation.
- Sets, cardinality of sets, countable and uncountable sets.
- Binary relations on a set, equivalence relation, partial order.
- Integers, Euclid (extended) algorithms.
- Relation modulo n, congruence classes Zn and operations on Zn.
- Algebraic operations, semigroups, groups.
- Sets together with two binary operations, Boolean algebras.
- Rings of congruence classes Zn, fields Zp.
- Undirected graphs, trees and spanning trees.
- Directed graphs, strong connectivity and acyclic graphs.
- Euler graphs and Hamiltonian graphs, coloring.
- Combinatorics.
- Reserve.
Tutorials:
- Foundation of Propositional logic, Boolean calculus.
- Foundation of Predicate logic, quantifiers, interpretation.
- Sets, cardinality of sets, countable and uncountable sets.
- Binary relations on a set, equivalence relation, partial order.
- Integers, Euclid (extended) algorithms.
- Relation modulo n, congruence classes Zn and operations on Zn.
- Algebraic operations, semigroups, groups.
- Sets together with two binary operations, Boolean algebras.
- Rings of congruence classes Zn, fields Zp.
- Undirected graphs, trees and spanning trees.
- Directed graphs, strong connectivity and acyclic graphs.
- Euler graphs and Hamiltonian graphs, coloring.
- Combinatorics.
- Reserve.
References:
- DLindsay N. Childs: A Concrete Introduction to Higher Algebra, Springer; 3rd edition (November 26, 2008), ISBN-10: 0387745270
- Richard Johnsonbaugh: Discrete Mathematics, Prentice Hall, 4th edition (1997), ISBN 0-13-518242-5
Assesment (zapocet):
Requirements: Active participation in labs and scoring at least 8 points from midterm.
Midterm: Midterm will be written during the labs in 9th week of semester, i.e. November 28th. Midterm test consists of three parts: 1. logic - propositional and predicate logic (gain max. 6 points); 2. binary relations (gain max. 6 points); and 3. solving an equation in rezidue classes (gain max. 8 points). You can obtain max. 20 points, obligatory for assesment is 8 points.
Final exam:
A necessary condition is to obtain assesment (zapocet).
Final exam contains two parts - a written part (obligatory) and an oral part (not obligatory). Written test will consist of 6 problems, max. gain 80 points, with 105 minutes allowed for solving them.
Written test:
Problem 1: Negation of a sentence of predicate logic.
Problem 2: Binary relations on a set; properties of a binary relation (reflexivity, symmetry, antisymmetry, transitivity, equivalence relation, partial order), or a composition of relations.
Problem 3: Binary operations: For a given binary operation o on a set A decide whether (A,o) is a semigroup, a monoid, or a group. Furhter questions can be put: An equality which does not have a solution, a subsemigroup (a submonoid, a subgroup).
Problem 4: Structures Zn and their subgroup of invertible elements. Order of some/all of its elements. Solving a parametric linear equation in Zn.
Problem 5: Graphs: It is necessary to understand basic notions, be able to give small examples with prescribed properties, and use some of the facts/procedures that were shown at the lecture.
Problem 6: Combinatorics: A word problem concerning enumerative combinatorics.
Oral part:
The oral part will look at theory and can bring max. 20 points; can be taken by those who gained at least 40 points in the written part.
Grading:
The resulting grade is based on three inputs. S is the number of points brought from midterm calculated as follows: if the gain M from midterm taken for the first time is at least 10, then S = M - 10 (from re-taken midterm the points are not calculated); P is the number of points from the written part; and U is the number of points from the oral part.
1) If a student gained less than 40 points from the written test, the student failed the exam.
2) If a student gained 40 or more points from the written test, then the student can take an oral exam. The grade is then determined by the total P + S + U and the following key:
Sum | Grade |
50-59 | E (sufficient) |
60-69 | D (satisfactory) |
70-79 | C (good) |
80-89 | B (very good) |
>89 | A (excellent) |