menu   materiały dydaktyczne   opis kursu   informacje dodatkowe     ostatnia aktualizacja 10.2023 - Inżynieria oprogramowania W04ITE-SI0011G 10.2022 - Praca dyplomowa inżynierska       ogłoszenia Wyniki sprawdzianów z dnia 12.02.2011r.     materiały do zajęć wykłady Wstęp do algorytmów i struktur danych. Sortowanie bąbelkowe. Algorytmy liniowe - sortowanie przez zliczanie. Algorytmy liniowe c.d. - sortowanie pozycyjne. Badanie algorytmów. Algorytmy rekurencyjne „dziel i zwyciężaj” - sortowanie przez łączenie. Algorytmy rekurencyjne „dziel i zwyciężaj” c.d. Algorytm sortowania szybkiego. Algorytm sortowania przez kopcowanie. Analiza algorytmów sortowania - podsumowanie. Wyszukiwania w tablicach posortowanych. Sortowanie zewnętrzne naturalne i wielokierunkowe. Zmniejszanie liczby serii w plikach dyskowych. Sortowanie zewnętrzne polifazowe, podsumowanie algorytmów sortowania zewnętrznego. Abstrakcyjne typy danych - stos. Implementacja stosu za pomocą tablicy i rekurencyjnej struktury danych (listy wiązanej). Zastosowanie stosu do programów klienckich. Abstrakcyjne typy danych - kolejka. Implementacja kolejki za pomocą tablicy i rekurencyjnej struktury danych (listy wiązanej). Zastosowanie kolejki do programów klienckich. Abstrakcyjne typy danych - koleki priorytetowe. Implementacja kolejki za pomocą modelu tablicy-kopca i rekurencyjnej struktury danych (listy wiązanej). Zastosowanie kolejki priorytetowej do programów klienckich. Abstrakcyjne typy danych-struktury wiązane. Lista dwukierunkowa uporządkowana.Drzewa. Drzewa poszukiwań binarnych: wstawianie liści, wstawianie do korzenia, obroty w węzłach, wyważanie drzewa, przejście przez drzewo. Złożoność obliczeniowa tablic, drzew i list Drzewa zrównoważone-zstępujące drzewa 2-3-4, drzewa czerwono-czarne*. Wyszukiwanie zewnętrzne: B-drzewa. Typy złożoności obliczeniowej. Reprezentacje grafów, algorytmy grafowe: przeszukiwanie grafu „w głąb” DFS - algorytmy „z powrotami”, algorytm przeszukiwania "wszerz" BFS – obliczanie najkrótszej ścieżki z s do wszystkich osiągalnych wierzchołków metodą "podziału i ograniczeń", algorytm Floyda określania najkrótszej ścieżki w grafie metodą programowania dynamicznego. egzamin Przykładowe pytania egzaminacyjne - dodano zapowiadane przejścia przez graf! laboratorium   literatura literatura podstawowa Cormen T. H., Leiserson Ch. E., Rivest R. L., Wprowadzenie do algorytmów, Warszawa, WNT, 1998 Wirth N., Algorytmy + Struktury Danych = Programy, Warszawa, WNT, 1999 Sedgewick R., Algorytmy w C++, Warszawa, Oficyna Wydawnicza READ ME, 1999 Banachowski L., Diks K., Rytter W., Algorytmy i strukturty danych, Warszawa, WNT, 1999 literatura uzupełniająca Harel D., Rzecz o istocie informatyki, Algorytmika, Warszawa, WNT, 1992 Bentley J., Perełki oprogramowania, Warszawa, WNT, 1992