menu   materiały dydaktyczne   opis kursu   informacje dodatkowe     ostatnia aktualizacja 10.2023 - Inżynieria oprogramowania W04ITE-SI0011G 10.2022 - Praca dyplomowa inżynierska       autor kursu dr inż. Zofia Kruczkiewicz     zespół dydaktyczny dr inż. Marek Piasecki dr inż. Paweł Rogaliński dr inż. Robert Wójcik     semestralny wymiar godzin wykład - 20 godzin laboratorium - 20 godzin     wymagania wstępne Podstawy informatyki - INK9011 Praktyka programowania - INK9100 Pracownia programowania - INK9114     opis kursu Przedmiot dotyczy tworzenia koncepcji, projektu i implementacji algorytmów z uwzględnieniem analizy ich złożoności strukturalnej i obliczeniowej oraz dowodu poprawności. W ramach kursu omawiane są podstawowe algorytmy przetwarzające struktury danych o dostępie indeksowanym, sekwencyjnym oraz rekurencyjnym. Dla każdej z grup są prezentowane kolejno algorytmy: sortowania tablic i wyszukiwania w tablicach, sortowania plików, przetwarzania dynamicznych struktur nieuporządkowanych (stosy, kolejki. listy) i struktur uporządkowanych (listy, drzewa) oraz algorytmy grafowe.     zawartość tematyczna kursu wykład Wprowadzenie do algorytmów i struktur danych - 1h Abstrakcyjna koncepcja algorytmu, projekt i implementacja algorytmu, przykład sortowania bąbelkowego - 1h Algorytmy sortowania w czasie liniowym: przez zliczanie, pozycyjne - 2h Algorytmy sortowania typu "dziel i zwyciężaj": przez scalanie, szybkie - 2h Algorytm sortowania przez kopcowanie, kolejki priorytetowe - 1h Algorytmy wyszukiwania: sekwencyjnego, binarnego - 1h Algortmy sortowania zewnętrznego przez: łączenie naturalne, łączenie wielokierunkowe, łączenie polifazowe - 3h Algorytm zmniejszania liczby serii - 1h Rekurencyjne nieuporządkowane struktury danych: stosy, kolejki, listy jedno- i dwukierunkowe - 2h Rekurencyjne uporządkowane struktury danych: listy, drzewa poszukiwań binarnych - 2h Wyważanie drzew poszukiwań binarnych, drzewa wielokierunkwe - 2h Algorytmy grafowe: przeszukiwanie wszerz, przeszukiwanie wgłąb - 2h laboratorium Laboratorium obejmuje zestaw ćwiczeń dotyczących: implementacji algorytmów sortowania tablic zawierających różne typy elementów oraz pomiar czasu ich trwania implementacji algorytmów sortowania plików o różnej zawartości oraz pomiar czasu ich trwania implementacji algorytmów przetwarzania dynamicznych nieuporządkowanych struktur danych: stosów, kolejek i list oraz pomiar czasu ich trwania implementacji algorytmów przetwarzania dynamicznych uporządkowanych struktur danych: list oraz drzew binarnych i wielokierunkowych oraz pomiar czasu ich trwania implementacji algorytmów grafowych