1. SylabUZ
2. Wydział Nauk Inżynieryjno-Technicznych
3. semestr zimowy 2021/2022
4. Informatyka - Program Erasmus pierwszego stopnia
5. Foundation of discrete systems

Wygeneruj PDF dla tej strony

Foundation of discrete systems - opis przedmiotu

Cel przedmiotu

 

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  procedures 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

-to introduce  students  to the  Maple  system

 

 

Wymagania wstępne

Zapisz zmiany

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

Zakres tematyczny

 

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 procedures: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. Applications to elementary probability theory.

Number Theory algorithms and  their  applications .Modular arithmetics, liner congruency problems, and their solution. The  notion of a 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.

Metody kształcenia

traditional  lectures

-  computational  exercises  

-laboratory: computational  experiments  in Maple

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu	Symbole efektów	Metody weryfikacji	Forma zajęć

Warunki zaliczenia

 

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

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

 

Literatura podstawowa

1 .Discrete Mathematics ,Ross K.A. , Wright  ( 3rd  edition ) Prentice Hall Inc. 1992

2.  Introduction to  algorithms , Cormen , T.H. , Leiserson , Ch.E , Rivest R.L .,MIT 1990

3.Discrete Mathematics and it's  Applications ,  K.H. Rosen, (6th  edition ) ,Mc Graw-Hill ,Inc.New  York , 2007

Literatura uzupełniająca

"Discrete Mathematical Structures with  Applications  to Computer  Science "  , McGraw Hill , 1975

Uwagi

Zmodyfikowane przez prof. dr hab. Roman Gielerak (ostatnia modyfikacja: 14-07-2021 12:56)