Foundation of discrete systems - course description

General information

Course name	Foundation of discrete systems
Course ID	11.9-WE-INFP-FoDS-Er
Faculty	Faculty of Computer Science, Electrical Engineering and Automatics
Field of study	Computer Science
Education profile	academic
Level of studies	Erasmus programme
Beginning semester	winter term 2017/2018

Course information

Semester	2
ECTS credits to win	4
Course type	obligatory
Teaching language	english
Author of syllabus	prof. dr hab. Roman Gielerak

Classes forms

The class form	Hours per semester (full-time)	Hours per week (full-time)	Hours per semester (part-time)	Hours per week (part-time)	Form of assignment
Lecture	30	2	-	-	Exam
Class	30	2	-	-	Credit with grade

Aim of the course

This is an introductory course in discrete mathematics.The main goal is to introduce students to ideas and techniques from discrete mathematics that are widely used in various areas of computer science,in particular in algorithms analysis ,in modern cryptography and data analysis.

-to introduce students to the basic discrete structures algorithms , in particular graph theory algorithms , number theory algorithms

- to introduce students to the basics of inductive and recurrent proceduras used in computer science

- to teach students to think logically and mathematically ,and to apply these techniques in solving typical computational problems appearing in practise

Prerequisites

Mathematical Analysis Course, Linear Algebra with Analytical Geometry foudations ,Logics for Infmatics

Scope

Introduction : elementary properties of functions and sequences.Set algebra calculus , formal calculus of proposals and the notion of abstract Bool algebra.

Basics of relation theory : the set theory notion versus digraphs notion vs matrix calculus.The equivalence and (partial ) ordering relations and their use.

Inductive and recurrent proceduras :The complete mathematical induction argument and applications.Definitions and applications of recurrence definitions .Linear recurrence equations and their solutions.The notion of inductive and recurrent algorithms , examples and their computational complexities.

Combinatorial problems and their applications :the basic definitions :permutations, combinations, variations .Applications of recurrences linear equations for solving combinatorial problems .The Dirichlet principle. Application to elementary probability theory.

Number Theory algorithms and their applications . Modular arithmetics ,liner congruencies problems and their solution. The notion of multiplicative group , theorem and function of Euler . Small Fermat theorem. Protokol RSA and its conditional security .

Introduction to graphs theory :the basic notion .The tree type of graphs :basic properties and constructions . The Euler graphs , Hamilton path notion .Graph colouring problem.Applications in computer science problems.

Teaching methods

traditional lectures

- computational exercises

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

Lecture - the passing condition is to obtain a positive mark from the final exam in written form

Computational exercises : the passing condition is to obtain positive marks from all midterm tests

Notes

Modified by prof. dr hab. Roman Gielerak (last modification: 22-04-2018 11:57)

Generate PDF for this page