Algorytmy i struktury danych

Zagadnienia do egzaminu

1. Proces tworzenia i uruchamiania programów.

2. Pojęcia: algorytm, program.

3. Sposoby reprezentacji algorytmów.

4. Własności algorytmów.

5. Badanie całkowitej poprawności algorytmu.

6. Podstawowe bloki algorytmów: bloki warunkowe, pętle.

7. Własności tablic. Tworzenie tablic jedno- i dwuwymiarowych w programach.

8. Pojęcia: graf, graf skierowany, graf prosty, graf z wagami, graf spójny, graf acykliczny, drzewo

(wolne), drzewo z korzeniem, drzewo binarne.

9. Sposoby reprezentacji grafów.

10. Podstawowe cechy notacji: O, Ω, Θ.

11. Pojęcie złożoności obliczeniowej algorytmów.

12. Porównanie złożoności obliczeniowych.

13. Niezmiennik pętli – definicja, zastosowania.

14. Podstawowe cechy i budowa struktur: stos, kolejka, lista powiÄ…zana (jednokierunkowa,

dwukierunkowa).

15. Pojęcia: funkcja, procedura. Definiowanie funkcji i procedur.

16. Pojęcie rekurencji.

17. Przykłady algorytmów rekurencyjnych.

18. Metody projektowania algorytmów (dla każdej metody: idea, podstawowe własności, przykłady):

○ metoda dziel i zwyciężaj,

â—‹ programowanie dynamiczne,

○ metoda zachłanna.

19. Algorytmy wyszukiwania (ogólne zasady działania, własności):

â—‹ wyszukiwanie liniowe,

â—‹ wyszukiwanie binarne.

20. Algorytmy wyszukiwania (ogólne zasady działania, własności):

â—‹ sortowanie przez selekcjÄ™,

â—‹ sortowanie przez wstawianie,

â—‹ sortowanie bÄ…belkowe,

â—‹ sortowania szybkie.

21. Algorytmy przeszukiwania tekstu (ogólne zasady działania, własności):

â—‹ przeszukiwanie proste,

â—‹ algorytm Rabina-Karpa,

â—‹ algorytm Knutha-Morrisa-Pratta.

22. Pojęcia: drzewo rozpinające, minimalne drzewo rozpinające.

23. Algorytmy grafowe (ogólne zasady działania, własności, zastosowania):

○ przeszukiwanie w głąb,

â—‹ przeszukiwanie wszerz,

â—‹ algorytm Kruskala,

â—‹ algorytm Prima,

â—‹ algorytm Dijkstry.