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   materiały do zajęć Wykłady Program wykładów i ćwiczeń - pierwszy semestr. Wprowadzenie do algorytmów-algorytmy liniowe, algorytmy z rozgałęzieniami. Sortowanie bąbelkowe, czasochłonność algorytmu. Sortowanie przez zliczanie, czasochłonność algorytmu. Sortowanie przez kopcowanie, złożoność algorytmu, podsumowanie algorytmów sortowania. Wyszukiwanie sekwencyjne, wyszukiwanie binarne bez powtórzeń. Sortowanie zewnętrzne - przez łączenie naturalne. 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 - 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 - słowniki (listy symboli). Implementacja słownika za pomocą tablicy indeksowanej kluczem. Zastosowanie słownika do programów klienckich. Podsumowanie algorytmów - część 1. Algorytmy "dziel i zwyciężaj". Rekurencja, sortowanie szybkie i przez łączenie. Sortowanie zewnętrzne przez łączenie wielokierunkowe, implementacja w C/C++. Sortowanie zewnętrzne polifazowe. Wyszukiwanie binarne dla ciągów posortowanych z powtórzeniami elementów. Analiza złożoności algorytmów sortowania szybkiego, kopcowego i przez łączenie 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.- Dodano wyjaśnienie w algorytmie BFS. Algorytmy zachłanne - Algorytmy Prima i Dijkstry. Rozszerzono ilustrację algorytmu Prima. Laboratorium Ćwiczenia Wprowadzenie do algorytmów. Sortowanie przez selekcję i wstawianie. Sortowanie pozycyjne, wyszukiwanie binarne bez powtórzeń. Zmniejszanie liczby serii w plikach dyskowych -zmiany w dniu 24.04.07r.. 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 - lista nieuporządkowana. Implementacja listy nieuporządkowanej za pomocą tablicy i rekurencyjnej struktury danych (listy wiązanej). Abstrakcyjne typy danych - lista uporządkowana. Implementacja listy uporządkowanej za pomocą tablicy i rekurencyjnej struktury danych (listy wiązanej). Laboratorium z Języków Programowania 1 Wprowadzenie. Wprowadzenie do programowania w C/C++. Pętle, instrukcje warunkowe. Pętle, instrukcje warunkowe, tablice, sekwencyjne zapisywanie i odczytywanie tablicy. Pętle, instrukcje warunkowe, sekwencyjne i niesekwencyjne zapisywanie i odczytywanie tablicy. Pętle, instrukcje warunkowe, sekwencyjne i niesekwencyjne zapisywanie i odczytywanie tablicy cd. (Funkcje bez parametrów i z parametrami.) Sprawdzian. Tablica dwuwymiarowa znakow, sortowanie pozycyjne. (Funkcje bez parametrów i z parametrami.) Tablice znaków -łańcuchy. (Funkcje bez parametrów i z parametrami.) Literatura N. Wirth - Algorytmy+Struktury Danych = Programy, WNT Warszawa 1999 R. Sedgewick - Algorytmy w C++, Oficyna Wydawnicza READ ME - Warszawa, 1999 T.H. Cormen, Ch E. Leiserson, R.L. Rivest - Wprowadzenie do algorytmów, WNT Warszawa 1997, 1998 L Banachowski, K.Diks, W. Rytter - Algorytmy i struktury danych, WNT Warszawa, 1999 D. Harel - Rzecz o istocie informatyki, Algorytmika, WNT Warszawa, 1992 J. Bentley - Perełki oprogramowania, WNT Warszawa, 1992