Algorytmy i struktury danych
Informacje ogólne
Kod przedmiotu: | 17-DASD-IP1 |
Kod Erasmus / ISCED: | (brak danych) / (brak danych) |
Nazwa przedmiotu: | Algorytmy i struktury danych |
Jednostka: | Nadnotecki Instytut UAM w Pile |
Grupy: |
Moodle - przedmioty Innych jednostek |
Punkty ECTS i inne: |
0 LUB
6.00
(w zależności od programu)
|
Język prowadzenia: | (brak danych) |
Kierunek studiów: | Technologie informatyczne - studia inżynierskie |
Poziom przedmiotu: | I stopień |
Cele kształcenia: | Zapoznanie studentów z podstawowymi metodami budowy algorytmów i wykorzystaniem prostych oraz różnego rodzaju złożonych struktur danych. Wykształcenie umiejętności konstruowania średniozaawansowanych algorytmów oraz ocenę ich złożoności i poprawności. |
Rok studiów (jeśli obowiązuje): | I rok |
Wymagania wstępne w zakresie wiedzy, umiejętności oraz kompetencji: | brak |
Informacja o tym, gdzie można zapoznać się z materiałami do zajęć: | Platforma MS Teams |
Metody prowadzenia zajęć umożliwiające osiągnięcie założonych EK: | wykłady, konwersatoria, ćwiczenia, laboratoria |
Nakład pracy studenta (punkty ECTS): | 6 |
Pełny opis: |
Język algorytmiczny pojęcie zmiennej, instrukcja przypisania, instrukcje warunkowe, iteracje, operatory specjalne. Struktury tablicowe, przykłady prostych algorytmów wykorzystujących tablice jako struktury danych. Pojęcie procedury i funkcji. Deklaracja, parametry formalne, wywołanie, procedura funkcyjna (funkcja), matematyczne pojęcie rekurencji, procedury rekurencyjne. Zagadnienie złożoności i poprawności, złożoność pamięciowa, złożoność czasowa, notacja asymptotyczna, twierdzenie o rekurencji uniwersalnej, niezmiennik pętli. Podstawowe metody projektowania algorytmów metoda dziel i zwyciężaj, programowanie dynamiczne. Algorytmy sortowania sortowanie przez wstawianie, bąbelkowe, przez scalanie, szybkie, przez zliczanie. Stosy, kolejki, listy, pojęcie zbioru dynamicznego, tablicowa implementacja stosu i operacje na stosie, tablicowa implemementacja kolejki i operacje kolejkowe, lista dwukierunkowa z dowiązaniami, operacje na listach, listy z wartownikiem. Grafy, podstawowe pojęcia grafowe, reprezentacja grafów w komputerze, drzewa ukorzenione. Przykłady wykorzystania struktur dynamicznych. Problem otoczki wypukłej, przeszukiwanie grafu wszerz, przeszukiwanie grafu w głąb. Kopce, kolejki priorytetowe kopce binarne typu min i max, przywracanie własności kopca binarnego, sortowanie przez kopcowanie, implementacja kolejki priorytetowej za pomocą kopca binarnego. Drzewa wyszukiwań binarnych. Podstawowe własności drzew BST, operacje na drzewach BST, sortowanie drzewiaste. Drzewa czerwono-czarne. Podstawowe własności, operacje rotacji, wstawianie i usuwanie węzła. Haszowanie. Adresowanie bezpośrednie, tablice z haszowaniem, metoda łańcuchowa, adresowanie otwarte, funkcje haszujące, haszowanie doskonałe. Metoda zachłanna, algorytm Prima, algorytm Kruskala, algorytm Huffmana. Metoda z powrotami, problem królowych, problem sumy podzbiorów, problem plecakowy. |
Literatura: |
1. T. Cormen, Algorytmy bez tajemnic, Helion, Gliwice 2013. 2. T. Cormen, Ch. Leiserson, R. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwa Naukowo- Techniczne, Warszawa 2012. 3. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, Wydawnictwa Naukowo-Techniczne, Warszawa 2006. 4. N. Wirth, Algorytmy + struktury danych = programy, Wydawnictwa Naukowo -Techniczne, Warszawa 2000. 5. D. Knuth, Sztuka programowania, Tom 3: Sortowanie i wyszukiwanie, Wydawnictwa Naukowo-Techniczne, Warszawa 2002. 6. D. Harel, Y. Feldman, Rzecz o istocie informatyki. Algorytmika, Wydawnictwa Naukowo-Techniczne, Warszawa 2008. 7. R. Neapolitan, K. Naimipour, Podstawy algorytmów z przykładami w C++, Helion, Gliwice 2004. 8. J. Bentley, Perełki oprogramowania, Wydawnictwa Naukowo-Techniczne, Warszawa 2001. 9. V.A. Spraul, Myśl jak programista. Techniki kreatywnego rozwiązywania problemów, Helion, Gliwice 2013. 10. W. Anggoro, C++ Struktury danych i algorytmy, Helion, Gliwice 2019. |
Efekty uczenia się: |
E01-zna i stosuje podstawowe konstrukcje algorytmiczne, zapisuje je w pseudokodzie. E02-ma wiedzę w zakresie znaczenia i wykorzystania pojęcia rekurencji. E03-wykorzystuje procedury i funkcje do formułowania algorytmów, stosuje rekurencję. E04-zna i stosuje proste i złożone struktury danych, w tym struktury dynamiczne. E05-zna podstawowe techniki projektowania algorytmów i stosuje wiedzę matematyczną do formułowania i rozwiązywania zadań algorytmicznych. E06-konstruuje algorytmy dla średniozaawansowanego problemu algorytmicznego. E07-ocenia poprawność i złożoność czasową algorytmów, potrafi krytycznie ocenić skonstruowany algorytm. E08-ma świadomość ważności algorytmiki w informatyce i rozumie potrzebę dalszego kształcenia algorytmicznego. |
Metody i kryteria oceniania: |
zadania algorytmiczne podczas laboratoriów, ćwiczenia z algorytmów, zaliczenie ćwiczeń w formie testu |
Zajęcia w cyklu "Semestr zimowy 2020/2021" (zakończony)
Okres: | 2020-10-01 - 2021-02-28 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 15 godzin
Wykład, 30 godzin
Zajęcia laboratoryjne, 15 godzin
|
|
Koordynatorzy: | Karolina Skotarczak-Dobrzyńska, Jerzy Szymański | |
Prowadzący grup: | Karolina Skotarczak-Dobrzyńska, Jerzy Szymański | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie z notą Wykład - Egzamin Zajęcia laboratoryjne - Zaliczenie z notą |
Zajęcia w cyklu "Semestr zimowy 2021/2022" (zakończony)
Okres: | 2021-10-01 - 2022-02-23 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 15 godzin
Wykład, 30 godzin
Zajęcia laboratoryjne, 15 godzin
|
|
Koordynatorzy: | Karolina Skotarczak-Dobrzyńska, Jerzy Szymański | |
Prowadzący grup: | Karolina Skotarczak-Dobrzyńska, Jerzy Szymański | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie z notą Wykład - Egzamin Zajęcia laboratoryjne - Zaliczenie z notą |
Zajęcia w cyklu "Semestr zimowy 2022/2023" (zakończony)
Okres: | 2022-10-01 - 2023-02-26 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 15 godzin
Wykład, 30 godzin
Zajęcia laboratoryjne, 15 godzin
|
|
Koordynatorzy: | Karolina Skotarczak-Dobrzyńska, Jerzy Szymański | |
Prowadzący grup: | Karolina Skotarczak-Dobrzyńska, Jerzy Szymański | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie z notą Wykład - Egzamin Zajęcia laboratoryjne - Zaliczenie z notą |
Zajęcia w cyklu "Semestr zimowy 2023/2024" (zakończony)
Okres: | 2023-10-01 - 2024-02-25 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Ćwiczenia, 15 godzin
Wykład, 30 godzin
Zajęcia laboratoryjne, 15 godzin
|
|
Koordynatorzy: | Karolina Skotarczak-Dobrzyńska, Jerzy Szymański | |
Prowadzący grup: | Karolina Skotarczak-Dobrzyńska, Jerzy Szymański | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: |
Przedmiot -
Egzamin
Ćwiczenia - Zaliczenie z notą Wykład - Egzamin Zajęcia laboratoryjne - Zaliczenie z notą |
Właścicielem praw autorskich jest Uniwersytet im. Adama Mickiewicza w Poznaniu.