SylabUZ
| Course name | Foundations of discrete systems |
| Course ID | 11.9-WE-INFP-PodstSystDyskr |
| Faculty | Faculty of Computer Science, Electrical Engineering and Automatics |
| Field of study | Computer Science |
| Education profile | academic |
| Level of studies | First-cycle studies leading to Engineer's degree |
| Beginning semester | winter term 2022/2023 |
| Semester | 2 |
| ECTS credits to win | 5 |
| Course type | obligatory |
| Teaching language | polish |
| Author of syllabus |
|
| 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 | 18 | 1,2 | Exam |
| Laboratory | 15 | 1 | 9 | 0,6 | Credit with grade |
| Class | 15 | 1 | 9 | 0,6 | Credit with grade |
- zapoznać studentów z podstawowymi metodami i technikami matematyki dyskretnej stosowanymi w rożnych obszarach informatyki takich jak np. analiza algorytmów ,kryptografia i analiza danych.
- wyjaśnienie na bazie algorytmiki teorio- liczbowej podstaw złożoności obliczeniowej współczesnych algorytmów szyfrowania
- nauczenie stosowania wymienionych metod matematycznych do rozwiązywania zadań praktycznych pojawiających się w praktyce
-obsługa środowiska skryptowego Maple/Maxima
Analiza matematyczna, Algebra liniowa z geometrią analityczną, Logika dla informatyków
Wstęp: elementarne własności funkcji i ciągów (terminologia i notacja). Algebra zbiorów , algebra Boola.
Relacje: Relacje jako zbiory, relacje vs. grafy i vs. macierze. Podziały na klasy abstrakcji. Relacje porządkujące.
Procedury indukcyjne i rekurencyjne : Zachowania asymptotyczne: notacje ?, ?, o(-), O(-). Indukcja matematyczna i jej zastosowania. Wzór dwumienny Newtona. Procedury indukcyjne. Definicje i procedury rekurencyjne. Równania rekurencyjne. Liniowe równania rekurencyjne i ich rozwiązywanie. Metoda wielomianu charakterystycznego i metoda szeregów potęgowych. Funkcjonał generujący. Uniwersalne rekurencje i ich zastosowania do analizy złożoności obliczeniowych algorytmów rekurencyjnych. Algorytm Euklidesa i analiza jego złożoności obliczeniowej. Liczby Fibonacciego. Algorytmy rekurencyjne i indukcyjne.
Zagadnienia kombinatoryczne. Elementarne procedury zliczania. Podziały. Algorytmy teoriomnogościowe. Zasada szufladkowa Dirichleta. Permutacje. Kombinacje. Wariacje. Funkcje generujące. Algorytmy kombinatoryczne i ich złożoność obliczeniowa. Zastosowania do elementarnej teorii prawdopodobieństwa.
Zagadnienia teorii grafów. Grafy i grafy skierowane. Zastosowania rachunku macierzy do analizy grafów. Algorytmy na grafach skierowanych. Zagadnienia i algorytmy na grafach: przeszukiwania, sortowania, szukanie drzew rozpinających, szukanie optymalnych ścieżek. Optymalne przepływy na grafach. Problem komiwojażera.
Zagadnienia teorioliczbowe. Relacje podzielności. Arytmetyka modularna. Liniowe równania modularne. Chińskie twierdzenie o resztach. Rząd elementu: logarytm dyskretny. Problem faktoryzacji: twierdzenie Eulera i twierdzenie (małe) Fermata. Protokół kryptograficzny RSA. Testy pseudopierwszości. Test RabinaMillera.
Elementy logiki. Kwantyfikatory. Elementarny rachunek predykatów.
Zbiory nieskończone. Sieci boolowskie. Tablice Karnaugha.
Uzupełnienia. Języki formalne. Klasyczna teoria złożoności obliczeniowej. Problemy NP. i NP-zupełne.
wykład: wykład konwencjonalny
ćwiczenia: konsultacje, ćwiczenia rachunkowe
laboratorium: implementacje algorytmow do środowiska Maple
| Outcome description | Outcome symbols | Methods of verification | The class form |
Wykład - warunkiem zaliczenia jest rozwiązanie ponad 60% zadań egzaminacyjnych
Ćwiczenia - warunkiem zaliczenia jest uzyskanie oceny pozytywnej z ponad 66% realizowanych kolokwiów
Laboratorium-warunkiem zaliczenia jest uzyskanie oceny pozytywnej z ponad 66% realizowanych kolokwiów
Ocena końcowa: średnia arytmetyczna ocen z egzaminu i zaliczenia ćwiczeń i laboratorium
Modified by prof. dr hab. Roman Gielerak (last modification: 10-04-2022 08:34)
