UIN1065 Chapters in Discrete Mathematics I

Faculty of Philosophy and Science in Opava
Winter 2013
Extent and Intensity
2/0/0. 3 credit(s). Type of Completion: z (credit).
Teacher(s)
doc. Ing. Petr Sosík, Dr. (lecturer)
Guaranteed by
doc. Ing. Petr Sosík, Dr.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Prerequisites (in Czech)
MU10132 || MU10216 || MU10232
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
The course offers an introduction to a sequence of elegant methods of discrete mathematics which are useful, among others, when: (a) evaluating time and space complexity of recursive algorithms (b) analysing the behavior of algorithms calculating with real numbers (c) analysing algorithms of artificial intelligence (d) examining reliability of algorithms.
Syllabus
  • 1. Recurrent problems: the concept of recurrence, closed form and a proof of its correctness. Sample problems: Hanoi towers, lines in the plane, Josephus problem and its generalization. Repertoire method.
    2. Manipulation with sums: notation and transformation of indices, allowed re-arrangements, Iverson notation. Associative, commutative and distributive law.
    3. Multiple sums, dependent and independent indices. Simplification of multiple sums. Generalized associative, commutative and distributive law.
    4. Sums and recurrences: mutual transformations of sums and recurrences, the summation factor method, the perturbation method.
    5. Operations of difference a summation as a discrete parallel of differencial and integral calculus. Their applications in evaluation of sums and recurences.
Literature
    recommended literature
  • MATOUŠEK, J., NEŠETŘIL, J. Kapitoly z diskrétní matematiky. Karolinum, Praha, 2000. info
  • GRAHAM, R., KNUTH, D., PATASHNIK, O. Concrete Mathematics. Addison-Wesley, New York, 1992. info
Assessment methods
Oral exam
Language of instruction
Czech
Further comments (probably available only in Czech)
The course can also be completed outside the examination period.
Teacher's information
1. Solution to all homework assignments during the semester.
2. Solution to the final set of homework assignments, consultation of eventual problems.
The course is also listed under the following terms Winter 1993, Winter 1994, Winter 1995, Winter 1996, Winter 1997, Winter 1998, Winter 1999, Winter 2000, Winter 2001, Winter 2002, Winter 2003, Winter 2004, Winter 2005, Winter 2006, Winter 2007, Winter 2008, Winter 2009, Winter 2010, Winter 2011, Winter 2012, Winter 2014.
  • Enrolment Statistics (Winter 2013, recent)
  • Permalink: https://is.slu.cz/course/fpf/winter2013/UIN1065