SylabUZ

# Foundation of discrete systems - opis przedmiotu

Informacje ogólne
 Nazwa przedmiotu Foundation of discrete systems Kod przedmiotu 11.9-WE-INFP-FoDS-Er Wydział Wydział Informatyki, Elektrotechniki i Automatyki Kierunek WIEiA - oferta ERASMUS / Informatyka Profil - Rodzaj studiów Program Erasmus pierwszego stopnia Semestr rozpoczęcia semestr zimowy 2018/2019
Informacje o przedmiocie
 Semestr 2 Liczba punktów ECTS do zdobycia 4 Typ przedmiotu obowiązkowy Język nauczania angielski Sylabus opracował prof. dr hab. Roman Gielerak
Formy zajęć
 Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia Wykład 30 2 - - Egzamin Ćwiczenia 30 2 - - Zaliczenie na ocenę

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

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

-  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  ( 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: 06-04-2018 16:51)