PROPOZYCJE TEMATÓW


Poniżej znajdziecie spis proponowanych tematów na najbliższą sesję szczyrkowską. Jest to bardzo luźny zbiór rzeczy, które wydają się być ciekawe. Podczas referatu warto omówić problem złożoności omawianego algorytmu - czasem może się okazać, że będzie to jeden z niewielu prawdziwie matematycznych aspektów referatu.

Tematy wstępne:

1. Definicja algorytmu. Złożoność obliczeniowa algorytmu.
   
2. Dowodzenie poprawności algorytmu. (Temat może zainteresować osoby o bardziej teoretycznym podejściu).
   
3. Definicja algorytmu z wykorzystaniem maszyny Turinga (temat do modyfikacji przez osobę bardziej ogarniającą temat, należy podać literaturę).
   
4. Algorytmy sortujące.

Struktury danych:

1. Aksjomatyczne podejście do abstrakcyjnych struktur danych. Przykłady. (Temat dla teoretyków.)
   
2. Drzewa binarne, porządki przeglądania drzew binarnych (preorder, inorder, postorder). Przeszukiwanie binarne.
   
3. Podstawowe struktury danych: lista, stos, kolejka FIFO, kolejka priorytetowa.
   
4. Drzewa BST, drzewa AVL.

Geometria obliczeniowa:

1. Problem wyznaczania otoczki wypukłej. Algorytm Grahama, marsz Jarvisa. (Łatwy, przyjemny)
   
2. Diagramy Voronoi. (niełatwe programistycznie, ale da się zrobić)
   
3. Problem planowania ruchu robota.
   
4. Problem galerii sztuki. Triangulacja wielokąta. (trudne programistycznie)

Teoria grafów:

1. Podstawy teorii grafów. Sposoby reprezentacji grafu.
   
2. Minimalne drzewa rozpinające.
   
3. Problem najkrótszej ścieżki. Algorytm Dijkistry, algorytm Forda-Bellmana.
   
4. Problem maksymalnego przepływu.
   
5. Problem kolorowania grafów.

Równania różniczkowe:

1. Numeryczne metody rozwiązywania równań różniczkowych. Metoda Eulera, backward Euler method, metody Rungego-Kutty. Porównanie złożoności oraz precyzji omówionych metod. (Łatwe zarówno matematycznie jak i programistycznie)

Sztuczna inteligencja:

1. Sieci neuronowe. Zadanie klasyfikacji wzorców.
   
2. Algorytmy genetyczne.

Kryptografia:

1. Matematyczne podstawy kryptografii. Algorytm Euklidesa. Ciała skończone, element odwrotny w ciałach skończonych. Chińskie twierdzenie o resztach. Małe tw. Fermata.
   
2. Protokół Diffiego-Hellmana. Algorytm RSA.
   
3. Algorytmy faktoryzacji liczby naturalnej.

Inne:

1. Elementy teorii informacji. Entropia, kodowanie Huffmana.
   
2. Metody mnożenia wielomianów: algorytm Karatsuby, FFT.

Literatura:

1. Introduction to algorithms. Third edition. T. H. Cormen
   
2. Algorithms, 4th edition. Robert Sedgewick and Kevin Wayne'
   
3. Geometria obliczeniowa. Algorytmy i zastosowania. M.Berg, M.Kreveld
   
4. Metody Numeryczne. Postawy teoretyczne, aspekty praktyczne i algorytmy. E. Majchrzak, B. Mochnacki
   
5. Sieci neuronowe. S. Osowski
   
6. An introduction to neural networks. Ben Krose, Patrick van der Smagt
   
7. Cryptography and Data Security. Dorothy Elizabeth Robling Denning