Wstęp do informatyki II (potok I) 1000-112bWI2a
1. Elementy analizy złożoności obliczeniowej: Rozmiar zadania. Złożoność czasowa i pamięciowa. Rząd złożoności. Wpływ rzędu złożoności na praktyczną przydatność algorytmu. Obliczanie złożoności prostych algorytmów (sortowanie i wyszukiwanie binarne). Obliczanie złożoności algorytmów rekurencyjnych (pamięciowej i czasowej). (3 wykłady).
2. Abstrakcyjne struktury danych i metody ich implementacji: Stosy, kolejki, kolejki priorytetowe. Przykłady użycia (algorytm Heap-Sort). Implementacja tablicowa. Wskaźniki. Dynamiczna alokacja pamięci. Listy. Listowa implementacja stosu, kolejki i kolejki priorytetowej. Drzewa binarnych wyszukiwań. (4 wykłady)
3. Grafy i algorytmy grafowe: Grafy i ich reprezentacje. Podstawowe algorytmy grafowe. Przeszukiwanie w głąb i wszerz. (4 wykłady)
4. Informacja o problemach NP-zupełnych i nierozstrzygalnych. (1 wykład).
Rodzaj przedmiotu
Założenia (opisowo)
Literatura
1. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych. WNT, Warszawa 2002. Podręcznik do nauki wybranego języka programowania.
2. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Wprowadzenie do algorytmów, WNT, Warszawa, 2005.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: