|
HU Credits:
5
Degree/Cycle:
1st degree (Bachelor)
Responsible Department:
mathematics
Semester:
1st Semester
Teaching Languages:
Hebrew
Campus:
E. Safra
Course/Module Coordinator:
Dr. A Gurevich
Coordinator Office Hours:
Tue, 14-15
Teaching Staff:
Dr. Alex Gourevich
Prof Eran Nevo
Mr. Moshe White
Mr.
Course/Module description:
1. Logic – Boolean operations, truth tables, propositional calculus and semantic
2. Set theory – operations on sets, Cartesian product, relations and functions, equivalence and order relations, partially ordered sets
3. Counting problems – counting with and without order importance, set partitions
4. Identities - the binomial and multinomial formulas, combinatorial and algebraic proofs
5. Inclusion-exclusion principal – enumeration surjective maps, enumeration permutations without fixed point, Euler’s function
6. Induction and recursion – proofs by complete induction, solving of combinatorial problems with the aid of recursion, Fibonacci numbers, solving recurrence relations, Catalan numbers, reflection method
7. Pigeonhole principle – Erdos-Szekeres theorem
8. Graphs – paths, connectivity, cycles, trees, bipartite graphs, planar graphs, polyhedrons, Euler’s formula, Eulerian trails and cycles, Hamiltonian trails and cycles, matching, the marriage theorem
9. Graphs with additional structures – enumeration labeled trees, Cayley’s formula, coloured graphs, Ramsey theory
10. Infinite sets – countable sets, Cantor diagonal, Koenig’s lemma
Course/Module aims:
Providing basic notions of Discrete Math and developing the ability to solve problems.
Learning outcomes - On successful completion of this module, students should be able to:
solve elementary problems in set theory, combinatorics, and graph theory.
Attendance requirements(%):
none
Teaching arrangement and method of instruction:
Lecture + exercise
Course/Module Content:
1. Logic – Boolean operations, truth tables, propositional calculus and semantic
2. Set theory – operations on sets, Cartesian product, relations and functions, equivalence and order relations, partially ordered sets
3. Counting problems – counting with and without order importance, set partitions
4. Identities - the binomial and multinomial formulas, combinatorial and algebraic proofs
5. Inclusion-exclusion principal – enumeration surjective maps, enumeration permutations without fixed point, Euler’s function
6. Induction and recursion – proofs by complete induction, solving of combinatorial problems with the aid of recursion, Fibonacci numbers, solving recurrence relations, Catalan numbers, reflection method
7. Pigeonhole principle – Erdos-Szekeres theorem
8. Graphs – paths, connectivity, cycles, trees, bipartite graphs, planar graphs, polyhedrons, Euler’s formula, Eulerian trails and cycles, Hamiltonian trails and cycles, matching, the marriage theorem
9. Graphs with additional structures – enumeration labeled trees, Cayley’s formula, coloured graphs, Ramsey theory
10. Infinite sets – countable sets, Cantor diagonal, Koenig’s lemma
Required Reading:
none
Additional Reading Material:
Nati Liniel, Michal Parnas,
Discrete Mathematics (Hebrew)
Course/Module evaluation:
End of year written/oral examination 90 %
Presentation 0 %
Participation in Tutorials 0 %
Project work 0 %
Assignments 10 %
Reports 0 %
Research project 0 %
Quizzes 0 %
Other 0 %
Additional information:
none
|
