1DI1302 - Algorytmy i struktury danych

Nazwa w drugim języku: 

Algorithms and Data Structures

Cel przedmiotu: 

Zapoznanie studenta z następującymi zagadnieniami: metody tworzenia algorytmów i dowodzenia ich poprawności, pojęcie złożoności obliczeniowej czasowej i pamięciowej, najczęściej używane struktury danych: listy, drzewa, kopce, tablice, grafy, hasze i związane z nimi algorytmy, relacja pomiędzy danymi i algorytmami, podstawowe abstrakcyjne typy danych: kolejki, zbiór, słownik. Wybrane algorytmy przetwarzania danych: sortowanie tablic, operacje na drzewach binarnych i BST, kompresja, algorytmy dla grafów, wyszukiwanie wzorca. Problemy NP trudne, NP-zupełność, sztuczna inteligencja jako metoda rozwiązywania problemów o wielkiej złożoności obliczeniowej.
Kurs jest podstawą do tworzenia oprogramowania we wszystkich językach imperatywnych. Przygotowuje studenta do pracy jako projektant oprogramowania, programista, analityk oprogramowania.

Treści kształcenia: 

Podstawowe pojęcia, złożoność obliczeniowa. Analiza algorytmów i dowodzenie poprawności. Algorytmy sortowania tablic. Sortowanie o złożoności liniowej. Struktury wykorzystujące wskaźniki: listy, drzewa, grafy. Listy liniowe, drzewa wyważone, haszowanie. Opakowywanie struktur danych, abstrakcyjne typy danych. Kontenery w Javie. Wybrane algorytmy kompresji. Programowanie dynamiczne. Wybrane algorytmy działające na grafach. Wyszukiwanie wzorca w napisach. Algorytmy ewolucyjne. Problemy NP-zupełne.

Bibliografia: 

1. Cormen, Leiserson, Rivest, Stein - Wprowadzenie do algorytmów, wyd. 2, WNT 2004;
2. Lafore - Java. Algorytmy i struktury danych, Helion 2003
3. Knuth - Sztuka programowania, WNT 2002

Metody oceny: 

Zgodnie z regulaminem kursu.

Uwagi: 

Przedmioty na których bazuje dany przedmiot (prerekwizyty):

• [1DI1206] Języki i metody programowania 2
• [1DI1108] Języki i metody programowania 1