Wyższa Szkoła Technologii Informatycznych w Katowicach

http://www.wsti.edu.pl e-mail: [e-mail]

Zagadnienia tematyczne z przedmiotu Algorytmy i struktury danych

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.

26. Sortowanie przez proste wybieranie.

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.

---