Analityczna teoria liczb, algorytmy matematyczne i analiza złożoności obliczeniowej

Konspect zajęć

I. Analityczna teoria liczb
- Liczby pierwsze i ich własności
- Definicja liczby pierwszej
- Własności liczb pierwszych
- Algorytmy służące do znalezienia liczb pierwszych
- Teoria Euklidesa
- Algorytm Euklidesa służący do znajdowania największego wspólnego dzielnika dwóch liczb
- Rozszerzony algorytm Euklidesa
- Twierdzenie Eulera
- Definicja funkcji Eulera
- Twierdzenie Eulera mówiące o resztach z dzielenia potęg
- Cykl Hamiltona i cykl Eulera
- Definicje cyklu Hamiltona i cyklu Eulera
- Sposoby znajdywania cyklu Hamiltona i cyklu Eulera w grafach
- RSA
- Algorytm RSA służący do kryptografii asymetrycznej
- Zasada działania algorytmu RSA

II. Algorytmy matematyczne
- Sortowanie
- Algorytmy sortowania (np. quicksort, mergesort, heapsort)
- Analiza złożoności obliczeniowej algorytmów sortowania
- Grafy i drzewa
- Algorytmy przeszukiwania grafów (np. DFS, BFS)
- Algorytmy minimalnego drzewa rozpinającego (np. Prim, Kruskal)
- Programowanie dynamiczne
- Definicja programowania dynamicznego
- Zastosowania programowania dynamicznego (np. algorytmy najdłuższego wspólnego podciągu, problem plecakowy)

III. Analiza złożoności obliczeniowej
- Notacja dużego O
- Definicja notacji dużego O
- Przykłady zastosowania notacji dużego O
- Klasy złożoności obliczeniowej
- Klasy złożoności P i NP
- Problemy NP-zupełne
- Algorytmy wielomianowe i niewielomianowe
- Algorytmy wielomianowe (np. algorytmy sortowania)
- Algorytmy niewielomianowe (np. algorytmy faktoryzacji liczb)