|
HU Credits:
5
Degree/Cycle:
1st degree (Bachelor)
Responsible Department:
Young Scientist
Semester:
2nd Semester
Teaching Languages:
Hebrew
Campus:
E. Safra
Course/Module Coordinator:
Dr. Alex Gourevich
Coordinator Office Hours:
Teaching Staff:
Dr. Alex Gourevich,
Mr. Ben Baskin
Course/Module description:
1. Logic – Boolean operations, truth tables, propositional calculus and semantic
2. Set theory – operations on sets, Cartesian product, functions
3. Relations - equivalence and order relations, partially ordered sets
4. Counting problems – counting with and without order importance, set partitions
5. Identities - the binomial and multinomial formulas, combinatorial and algebraic proofs
6. Reflection method - Catalan numbers
7. Inclusion-exclusion principal – enumeration surjective maps, enumeration permutations without fixed point, Euler’s function
8. Induction and recursion – proofs by complete induction, solving of combinatorial problems with the aid of recursion, Fibonacci numbers
9. Pigeonhole principle – Erdos-Szekeres theorem
10.Asymptotic analysis - asymptotic analysis of combinatorial problems
11. Graphs – paths, connectivity, cycles, trees, bipartite graphs, Eulerian trails and cycles, Hamiltonian trails and cycles, matching, Hall's marriage theorem, colored graphs, Ramsey theory
Additional topics may be studied.
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(%):
80%
Teaching arrangement and method of instruction:
lecture + exercise session
Course/Module Content:
1. Logic – Boolean operations, truth tables, propositional calculus and semantic
2. Set theory – operations on sets, Cartesian product, functions
3. Relations - equivalence and order relations, partially ordered sets
4. Counting problems – counting with and without order importance, set partitions
5. Identities - the binomial and multinomial formulas, combinatorial and algebraic proofs
6. Reflection method - Catalan numbers
7. Inclusion-exclusion principal – enumeration surjective maps, enumeration permutations without fixed point, Euler’s function
8. Induction and recursion – proofs by complete induction, solving of combinatorial problems with the aid of recursion, Fibonacci numbers
9. Pigeonhole principle – Erdos-Szekeres theorem
10.Asymptotic analysis - asymptotic analysis of combinatorial problems
11. Graphs – paths, connectivity, cycles, trees, bipartite graphs, Eulerian trails and cycles, Hamiltonian trails and cycles, matching, the marriage theorem, colored graphs, Ramsey theory
Additional topics may be studied.
Required Reading:
none
Additional Reading Material:
Grading Scheme :
Written / Oral / Practical Exam 90 %
Submission assignments during the semester: Exercises / Essays / Audits / Reports / Forum / Simulation / others 10 %
Additional information:
|
