1. SylabUZ
2. Wydział Informatyki, Elektrotechniki i Automatyki
3. semestr zimowy 2018/2019
4. WIEiA - oferta ERASMUS / 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  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

 

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

Metody kształcenia

-traditional  lectures

-  computational  exercises  

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

Literatura podstawowa

  1 .Discrete Mathematics ,Ross K.A. , Wright  ( 3^rd  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, (6^th  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: 06-04-2018 16:51)