Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Algorytmy i struktury danych
Tok studiów:
2016/2017
Kod:
MEI-1-605-s
Wydział:
Inżynierii Metali i Informatyki Przemysłowej
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Edukacja Techniczno – Informatyczna
Semestr:
6
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
Kustra Piotr (pkustra@agh.edu.pl)
Osoby prowadzące:
Kustra Piotr (pkustra@agh.edu.pl)
Kustra Piotr (pkustra@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 podstawowe struktury danych i dynamiczne struktury informacyjne oraz sposoby ich reprezentacji w pamięci komputera EI1A_W08, EI1A_W01, EI1A_W07 Egzamin,
Udział w dyskusji,
Wykonanie ćwiczeń laboratoryjnych
M_W002 Zna podstawowe algorytmy dla rozwiązań modelowych. Zna i rozumie zasady konstrukcji algorytmów oraz oceny ich złożoności obliczeniowej. EI1A_W06, EI1A_W10, EI1A_W12, EI1A_W07 Aktywność na zajęciach,
Egzamin,
Wykonanie ćwiczeń
Umiejętności
M_U001 Potrafi korzystać z podanych źródeł wiedzy, poszukiwać innych i efektywnie wdrażać w pracach własnych gotowe algorytmy, dostępne w popularnych bibliotekach EI1A_U12, EI1A_U07, EI1A_U01, EI1A_U08 Wykonanie ćwiczeń,
Aktywność na zajęciach,
Projekt
M_U002 Potrafi zaimplemetować poznane struktury danych i algorytmy w wybranym języku programowania EI1A_U12, EI1A_U07, EI1A_U06, EI1A_U08 Egzamin,
Kolokwium,
Wykonanie ćwiczeń
M_U003 Potrafi współdziałać w zespole pracującym nad rozwiązaniem złożonego zadania algorytmicznego EI1A_U03, EI1A_U01, EI1A_U02, EI1A_U08, EI1A_U15 Wykonanie ćwiczeń,
Aktywność na zajęciach,
Wykonanie projektu,
Zaangażowanie w pracę zespołu
Kompetencje społeczne
M_K001 Potrafi, w sposób przedsiębiorczy i z poszanowaniem praw autorskich, korzystać z gotowych kontenerów bądź całych algorytmów przy rozwiązywaniu nietypowych problemów. EI1A_K03, EI1A_K01, EI1A_K04 Aktywność na zajęciach,
Egzamin,
Wykonanie ćwiczeń laboratoryjnych
M_K002 Potrafi zaprezentować samodzielnie przygotowany algorytm w formie opisu, schematu lub drzewa i programu EI1A_K05, EI1A_K04 Odpowiedź ustna,
Wykonanie ćwiczeń,
Egzamin
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 podstawowe struktury danych i dynamiczne struktury informacyjne oraz sposoby ich reprezentacji w pamięci komputera + - - - - - - - - - -
M_W002 Zna podstawowe algorytmy dla rozwiązań modelowych. Zna i rozumie zasady konstrukcji algorytmów oraz oceny ich złożoności obliczeniowej. - - - - - - - - - - -
Umiejętności
M_U001 Potrafi korzystać z podanych źródeł wiedzy, poszukiwać innych i efektywnie wdrażać w pracach własnych gotowe algorytmy, dostępne w popularnych bibliotekach - - + - - - - - - - -
M_U002 Potrafi zaimplemetować poznane struktury danych i algorytmy w wybranym języku programowania - - + - - - - - - - -
M_U003 Potrafi współdziałać w zespole pracującym nad rozwiązaniem złożonego zadania algorytmicznego - - + - - - - - - - -
Kompetencje społeczne
M_K001 Potrafi, w sposób przedsiębiorczy i z poszanowaniem praw autorskich, korzystać z gotowych kontenerów bądź całych algorytmów przy rozwiązywaniu nietypowych problemów. - - + - - - - - - - -
M_K002 Potrafi zaprezentować samodzielnie przygotowany algorytm w formie opisu, schematu lub drzewa i programu - - + - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:
  1. Podstawowa wiedza o algorytmach i strukturach danych

    Pojęcie algorytmu, analiza i projektowanie algorytmów. Złożoność obliczeniowa. Rzędy wielkości funkcji.
    Podstawowe struktury danych i ich reprezentacje; typy proste i typy złożone. Szacowanie potrzebnych zasobów pamięci.

  2. Przegląd algorytmów dla rozwiązań modelowych

    Algorytmy na liczbach. Arytmetyka prosta i modularna. Kryptografia. Haszowanie uniwersalne.
    Algorytmy sortowania: metody proste, metody szybkie.
    Algorytmy “dziel i zwyciężaj”. Algorytmy rekurencyjne.
    Grafy. Dekompozycje grafów. Ścieżki w grafach; odległości, przeszukiwania grafu; długości krawędzi, algorytm Dijkstry.
    Algorytmy zachłanne.

  3. Dynamiczne struktury i programowanie

    Struktury dynamiczne: rekurencyjne typy danych, stosy kolejki i listy, operacje na zbiorach dynamicznych. Struktury drzewiaste, drzewa wielokierunkowe.
    Wprowadzenie do programowania dynamicznego. Przykład : problem plecakowy.
    Wprowadzenie do programowania liniowego.
    NP zupełność. Algorytmy aproksymacyjne

Ćwiczenia laboratoryjne:

Projektowanie algorytmów dla zadań modelowych.
Implementacja wybranych algorytmów omawianych na wykładzie. Ocena efektywności wybranych algorytmów.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 87 godz
Punkty ECTS za moduł 3 ECTS
Udział w wykładach 28 godz
Udział w ćwiczeniach laboratoryjnych 14 godz
Przygotowanie do zajęć 15 godz
Samodzielne studiowanie tematyki zajęć 30 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

PROCENTOWA OCENA KOŃCOWA = (LPAĆ+LPK+PE+LPAW)
gdzie
LPAW -Aktywność na wykładach (obecności, dyskusje, odpowiedzi);(Max liczba punktów=15)
LPE – Liczba punktów za egzamin; (Max liczba punktów=35)
POC (procentowa ocena z ćwiczeń) =(LPK+LPAĆ)*2
przy czym
LPAĆ Aktywność na ćwiczeniach (obecności, wykonane zadania);(MAX = 30)
LPK Kolokwia, (MAX=20)

*Ocena klasyczna przyporządkowana jest procentowej zgodnie z Regulaminem Studiów w AGH *

Wymagania wstępne i dodatkowe:

Zgodnie z Regulaminem Studiów AGH podstawowym terminem uzyskania zaliczenia jest ostatni dzień zajęć w danym semestrze. Termin zaliczenia poprawkowego (tryb i warunki ustala prowadzący moduł na zajęciach początkowych) nie może być późniejszy niż ostatni termin egzaminu w sesji poprawkowej (dla przedmiotów kończących się egzaminem) lub ostatni dzień trwania semestru (dla przedmiotów niekończących się egzaminem).

Zalecana literatura i pomoce naukowe:

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein – „Wprowadzenie do algorytmów” – WNT, 2004.

Sanjoy Dasgupta, Christos Papadimitriou, Umesj Vazirani , Algorytmy, PWN Warszawa 2010

L. Banachowski, K. Diks, W. Rytter – „Algorytmy i struktury danych” – WNT, 1996, 1999

Niklaus Wirth – „Algorytmy + struktury danych = programy” – WNT, 1980, 1999, 2000

Piotr Wróblewski – „Algorytmy struktury danych i techniki programowania” – Helion, 2001

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

http://www.bpp.agh.edu.pl/

Informacje dodatkowe:

Brak