http://www.wsti.edu.pl e-mail: wsti@wsti.edu.pl
Algorytmy i struktury danych
1. Pojęcie typu danych.
2. Proste typy danych – liczbowe, znakowe, logiczne.
3. Tablice
4. Rekordy
5. Zbiory
6. Pliki.
7. Reprezentacja struktur danych.
8. Pojęcie algorytmu.
9. Cechy i rodzaje algorytmów.
10. Metody zapisu algorytmu: opis słowny, schematy blokowe.
11. Weryfikacja poprawności algorytmów.
12. Pojęcie niezmiennika, metoda Floyda.
13. Złożoność obliczeniowa algorytmów – pamięciowa i czasowa.
14. Złożoność czasowa średnia, pesymistyczna.
15. O-notacja dla złożoności algorytmów.
16. Przykład szacowania złożoności czasowej.
17. Podział algorytmów ze względu na złożoność.
18. Wyszukiwanie liniowe.
19. Wyszukiwanie binarne.
20. Rola wartownika w wyszukiwaniu.
21. Haszowanie.
22. Minimalna, doskonała funkcja haszująca.
23. Metody przezwyciężania kolizji.
24. Wyszukiwanie wzorca w tekście.
25. Sortowania przez proste wstawianie.
27. Sortowanie bąbelkowe.
28. Metoda dziel i zwyciężaj ‑ sortowanie szybkie.
29. Sortowanie drzewiaste.
30. Sortowanie stogowe.
31. Abstrakcyjne struktury danych ‑ listy.
32. Abstrakcyjne struktury danych – stosy.
33. Abstrakcyjne struktury danych – kolejki.
34. Realizacja fizyczna list, stosów i kolejek.
35. Grafy – definicja, cechy, rodzaje.
36. Reprezentacje grafów skierowanych i nieskierowanych.
37. Pojęcie i definicje drzew.
38. Cechy drzew – wysokość, moment, rząd itd.
39. Drzewa binarne, reprezentacja tablicowa.
40. Operacje na drzewach ‑ wstawianie, usuwanie węzłów, równoważenie drzewa.
41. Sposoby reprezentacji grafów.
42. Podstawowe operacje na grafach, przeszukiwanie grafu w głąb, wszerz.
43. Poszukiwanie najkrótszej ścieżki w grafie.
44. Programowanie dynamiczne.
45. Minimalne drzewo rozpinające.
46. Problem komiwojażera.
47. Algorytmy zachłanne.
48. Rekurencja – silnia, liczby Fibonacchiego.
49. Rekurencja w definicjach drzew i list.
50. Realizacja silni i liczb Fibonacchiego bez rekurencji.
51. Fraktale – trójkąt Sierpińskiego i krzywa Hilberta.
fazer999999999