1. Proces tworzenia i uruchamiania programów.
Zadanie do wykonania -> Algorytm projekt programu-> tekst programu (plik źródłowy)-> plik wykonywalny programu-kod maszynowy (Plik Binany)-> system operacyjny komputer
2. Pojęcia: algorytm, program.
Algorytm – przepis prowadzący do rozwiązania określonego zadania.
Program – zapis algorytmu i danych w konkretnym języku programowania. Przetwarza określone dane wejściowe w dane wyjściowe.
3. Sposoby reprezentacji algorytmów.
Język naturalny. Lista kroków. Drzewo algorytmu. Schemat blokowy. Pseudokod (mniej formalny, bardziej intuicyjny system notacji). Kod w języku programowania.
4. Własności algorytmów.
Skończoność (realizowany ciąg operacji powinien mieć swój koniec). ● Określoność (operacje oraz porządek ich wykonywania powinny być ściśle określone). ● Ogólność (algorytm powinien odnosić się nie tylko do jednego szczególnego przypadku, ale do pewnej klasy zadań). ● Efektywność (algorytm powinien prowadzić do rozwiązania możliwie najprostszą drogą).
5. Badanie całkowitej poprawności algorytmu.
Algorytm jest całkowicie poprawny jeśli dla każdych danych wejściowych spełniających wymagane warunki wstępne zatrzymuje się i daje poprawny wynik. ● Dowód poprawności algorytmu: – udowodnienie własności stopu (dla każdych danych wejściowych spełniających wymagane warunki wstępne algorytm zatrzymuje się), – udowodnienie częściowej poprawności (jeśli algorytm zatrzymuje się to daje poprawny wynik). Całkowita poprawność = własność stopu + częściowa poprawność
6. Podstawowe bloki algorytmów: bloki warunkowe, pętle.
7. Własności tablic. Tworzenie tablic jedno- i dwuwymiarowych w programach
Tablica jest zbiorem elementów tego samego typu. ● Każdy element jest identyfikowany przez indeks (numer pozycji na której się znajduje). ● W pamięci komputera tablica zajmuje ciągły obszar komórek pamięci. ● Tablica charakteryzuje się bezpośrednim dostępem do elementów. Dostęp ten uzyskuje się poprzez podanie odpowiednich indeksów elementów.
8. Pojęcia: graf, graf skierowany, graf prosty, graf z wagami, graf spójny, graf acykliczny, drzewo(wolne), drzewo z korzeniem, drzewo binarne.
Graf-(lub graf nieskierowany) G składa się z niepustego skończonego zbioru wierzchołków (węzłów) V oraz skończonego zbioru krawędzi E będących nieuporządkowanymi parami elementów ze zbioru V.
Graf skierowany G składa się z niepustego skończonego zbioru wierzchołków (węzłów) V oraz skończonego zbioru krawędzi E będących uporządkowanymi parami elementów ze zbioru V.
Grafem prostym nazywany jest graf, który nie zawiera zarówno pętli jak i krawędzi równoległych
Graf z wagami (skierowany lub nieskierowany) G składa się ze zbioru wierzchołków V, zbioru krawędzi E oraz funkcji wagowej w przyporządkowującej każdej krawędzi ze zbioru E liczbę rzeczywistą.
Graf spójny jest grafem w którym istnieje ścieżka z u do v dla każdego wierzchołka u oraz v.
Graf acykliczny jest grafem, który nie zawiera cykli.
Drzewo (lub drzewo wolne) T jest grafem prostym, który jest acykliczny i spójny.
Drzewo z korzeniem jest drzewem z wyróżnionym jednym wierzchołkiem nazywanym korzeniem.
Drzewo binarne jest drzewem z korzeniem, w którym każdy wierzchołek ma co najwyżej dwa wierzchołki potomne.
9. Sposoby reprezentacji grafów. Macierz sąsiedztwa, graf
10. Podstawowe cechy notacji: O, Ω, Θ.
11. Pojęcie złożoności obliczeniowej algorytmów.
Złożoność obliczeniowa algorytmu określana jest przez zasoby systemu komputerowego (przede wszystkim czas działania i ilość zajmowanej pamięci) niezbędne do realizacji algorytmu. ● Rodzaje złożoności obliczeniowej:– złożoność czasowa, – złożoność pamięciowa.
● Złożoność obliczeniowa (czasowa i pamięciowa) algorytmu podawana jest jako funkcja rozmiaru danych wejściowych n.
12. Porównanie złożoności obliczeniowych.
Złożoność logarytmiczna O(log n)● Złożoność liniowa O(n)● Złożoność liniowo-logarytmiczna O(n log n)● Złożoność kwadratowa O(n2)● Złożoności wielomianowe O(n3), O(n4), ...● Złożoność wykładnicza O(2n)● Złożoność silnia O(n!)
13. Niezmiennik pętli – definicja, zastosowania.
Niezmiennik instrukcji iteracyjnej (pętli) –warunek opisujący wartości zmiennych w trakcie wykonywania algorytmu taki, że:– jest on spełniony na początku instrukcji iteracyjnej, – każde powtórzenie instrukcji iteracyjnej zachowuje go, – jest on spełniony po zakończeniu instrukcji iteracyjnej.
Zastosowanie: aby móc stwierdzić, czy pętla działa zgodnie z oczekiwaniami.
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.
blejt14