Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Algorytmy i struktury danych
Tok studiów:
2014/2015
Kod:
IIN-1-202-s
Wydział:
Informatyki, Elektroniki i Telekomunikacji
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka
Semestr:
2
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
Faliszewski Piotr (faliszew@agh.edu.pl)
Osoby prowadzące:
dr inż. Gajęcki Marek (mag@agh.edu.pl)
Faliszewski Piotr (faliszew@agh.edu.pl)
Kurdziel Marcin (kurdziel@agh.edu.pl)
Krótka charakterystyka modułu

Opis efektów kształcenia dla modułu zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Powiązania z EKK Sposób weryfikacji efektów kształcenia (forma zaliczeń)
Wiedza
M_W001 Zna i rozumie podstawowe mechanizmy i techniki konstruowania algorytmów IN1A_W03 Egzamin
M_W002 Zna i rozumie podstawowe mechanizmy analizy algorytmów IN1A_W03 Egzamin
M_W003 Dysponuje wiedzą na temat złożonych struktur danych IN1A_W03 Egzamin
M_W004 Dysponuje wiedzą na podstawowych algorytmów IN1A_W03 Egzamin
Umiejętności
M_U001 Potrafi rozwiązywać zadania algorytmiczne IN1A_U07 Kolokwium
M_U002 Potrafi stosować złożone struktury danych IN1A_U07 Kolokwium
Matryca efektów kształcenia w odniesieniu do form zajęć
Kod EKM Student, który zaliczył moduł zajęć wie/umie/potrafi Forma zajęć
Wykład
Ćwicz. aud
Ćwicz. lab
Ćw. proj.
Konw.
Zaj. sem.
Zaj. prakt
Zaj. terenowe
Zaj. warsztatowe
Inne
E-learning
Wiedza
M_W001 Zna i rozumie podstawowe mechanizmy i techniki konstruowania algorytmów + - - - - - - - - - -
M_W002 Zna i rozumie podstawowe mechanizmy analizy algorytmów + - - - - - - - - - -
M_W003 Dysponuje wiedzą na temat złożonych struktur danych + - - - - - - - - - -
M_W004 Dysponuje wiedzą na podstawowych algorytmów + - - - - - - - - - -
Umiejętności
M_U001 Potrafi rozwiązywać zadania algorytmiczne - + - - - - - - - - -
M_U002 Potrafi stosować złożone struktury danych - + - - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:

1. Wprowadzenie do algorytmiki (2 godz.)
Analiza algorytmu. Złożoność obliczeniowa.

2. Algorytmy sortowania (6 godz.)
Podstawowe pojęcia. Klasyfikacja metod. Sortowania proste. Sortowania szybkie. Dolne ograniczenie złożoności sortowania. Sortowania liniowe. Mediany i statystyki pozycyjne.

3. Elementarne struktury danych (6 godz.)
Warstwa abstrakcji i warstwa implementacji. Elementarne struktury: tablica, lista odsyłaczowa, drzewa wskaźnikowe, stos, kolejka, kolejka priorytetowa, zbiór, zbiory rozłączne, kopiec, drzewa binarne, drzewa BST i ich warianty, lista z przeskokami, struktura słownikowa, B-drzewa.

5. Tablice z haszowaniem (2 godz.)
Funkcje mieszające. Metoda łańcuchowa rozwiązywania kolizji. Adresowanie otwarte i rozwiązywanie kolizji poprzez adresowanie liniowe, mieszanie wielokrotne. Reorganizacja tablic z haszowaniem.

6. Elementarne techniki algorytmiczne (6 godz.)
Metoda dziel i zwyciężaj. Algorytmy zachłanne. Programowanie dynamiczne.

7. Grafy (8 godz.)
Podstawowe definicje. Reprezentacja w pamięci. Grafy skierowane i nieskierowane. Przeszukiwania grafu w głąb i wszerz. Złożoność przeszukiwań. Algorytmy grafowe.

Ćwiczenia audytoryjne:

1. Proste metody sortowania (3 godz.)
2. Sortowania szybkie i liniowe (3 godz.)
3. Elementarne struktury danych (6 godz.)
4. Tablice z haszowaniem (2 godz.)
5. Algorytmy zachłanne (3 godz.)
6. Programowanie dynamiczne (5 godz.)
7. Implementacja i przeszukiwanie grafów (2 godz.)
8. Algorytmy grafowe (6 godz.)

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 150 godz
Punkty ECTS za moduł 6 ECTS
Udział w wykładach 30 godz
Udział w ćwiczeniach audytoryjnych 30 godz
Samodzielne studiowanie tematyki zajęć 60 godz
Przygotowanie sprawozdania, pracy pisemnej, prezentacji, itp. 30 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Ocena dla studentów, którzy otrzymali pozytywną ocenę z ćwiczeń © oraz egzaminu (E) w odpowiednich pierwszych terminach, ocena końcowa wynosi max((C+E)/2, 3.5). (Jeśli (C+E)/2 nie jest regulaminową oceną, to ocena zaokrąglana jest w strone korzystniejszą dla studenta).

Jeśli któraś z ocen (C lub E) została zdobyta w terminie późniejszym, to ocena końcowa wynosi nie więcej niż 3.0.

Wymagania wstępne i dodatkowe:

Znajomość matematyki (systemy pozycyjne, kombinatoryka, logarytmy, itp.)
Podstawowa znajomość programowania w C.

Zalecana literatura i pomoce naukowe:

1. „Wprowadzenie do algorytmów” Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wydawnictwo Naukowe PWN, 2012.
2. „Algorytmy” R. Sedgewick, K. Wayne, Helion 2012.
3. „Algorytmy” S. Dasgupta, C. Papadimitriou, U. Vazirani, Wydawnictwa Naukowe PWN 2010.

Publikacje naukowe osób prowadzących zajęcia związane z tematyką modułu:

Nie podano dodatkowych publikacji

Informacje dodatkowe:

Brak