Moduł oferowany także w ramach programów studiów:
Informacje ogólne:
Nazwa:
Algorytmy i struktury danych
Tok studiów:
2016/2017
Kod:
MIS-1-201-s
Wydział:
Inżynierii Metali i Informatyki Przemysłowej
Poziom studiów:
Studia I stopnia
Specjalność:
-
Kierunek:
Informatyka Stosowana
Semestr:
2
Profil kształcenia:
Ogólnoakademicki (A)
Język wykładowy:
Polski
Forma i tryb studiów:
Stacjonarne
Strona www:
 
Osoba odpowiedzialna:
dr hab. Szeliga Danuta (szeliga@agh.edu.pl)
Osoby prowadzące:
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 oraz klasy metod algorytmicznych. Potrafi korzystać z podanych źródeł literatury oraz poszukiwać własnych IS1A_W07 Aktywność na zajęciach,
Egzamin,
Wykonanie ćwiczeń,
Wykonanie ćwiczeń laboratoryjnych,
Zaliczenie laboratorium
M_W002 Zna i rozumie podstawowe algorytmy rozwiązań dla zagadnień modelowych. Zna pojęcie złożoność obliczeniowej algorytmu IS1A_W07 Aktywność na zajęciach,
Egzamin,
Wykonanie ćwiczeń,
Wykonanie ćwiczeń laboratoryjnych
Umiejętności
M_U001 Potrafi zastosować poznane struktury danych i algorytmy do rozwiązywania zadań algorytmicznych oraz oszacować złożoność obliczeniową przyjętego rozwiązania IS1A_U16 Aktywność na zajęciach,
Egzamin,
Udział w dyskusji,
Wykonanie ćwiczeń,
Wykonanie ćwiczeń laboratoryjnych
M_U002 Potrafi zaimplementować podstawowe struktury danych i algorytmy w wybranym języku programowania IS1A_U16 Aktywność na zajęciach,
Wykonanie ćwiczeń laboratoryjnych,
Zaangażowanie w pracę zespołu
M_U003 Wykazuje gotowość do pracy zespołowej nad tworzeniem rozwiązania dla rozpatrywanego problemu algorytmicznego IS1A_U16 Aktywność na zajęciach,
Wykonanie ćwiczeń laboratoryjnych,
Zaangażowanie w pracę zespołu
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 oraz klasy metod algorytmicznych. Potrafi korzystać z podanych źródeł literatury oraz poszukiwać własnych + + + - - - - - - - -
M_W002 Zna i rozumie podstawowe algorytmy rozwiązań dla zagadnień modelowych. Zna pojęcie złożoność obliczeniowej algorytmu + + + - - - - - - - -
Umiejętności
M_U001 Potrafi zastosować poznane struktury danych i algorytmy do rozwiązywania zadań algorytmicznych oraz oszacować złożoność obliczeniową przyjętego rozwiązania - + - - - - - - - - -
M_U002 Potrafi zaimplementować podstawowe struktury danych i algorytmy w wybranym języku programowania - - + - - - - - - - -
M_U003 Wykazuje gotowość do pracy zespołowej nad tworzeniem rozwiązania dla rozpatrywanego problemu algorytmicznego - + + - - - - - - - -
Treść modułu zajęć (program wykładów i pozostałych zajęć)
Wykład:
Algorytmy i struktury danych

Struktury danych, operacje z nimi związane, ich zastosowania. Klasy metod algorytmicznych. Algorytmy rozwiązań dla zagadnień modelowych. Złożoność obliczeniowa algorytmów.
Program wykładów:
1. Wykład wprowadzający. Pojęcie algorytmu, analiza algorytmów, projektowanie algorytmów.
2. Złożoność obliczeniowa. Rzędy wielkości funkcji. Sumy. Rekurencje. Pojęcia: zbiór, relacja, funkcja, graf, drzewo. Podstawowe pojęcia z kombinatoryki i rachunku prawdopodobieństwa.
3. Sortowania: metody proste, metody szybkie.
4. Sortowania w czasie liniowym. Mediany i statystyki pozycyjne.
5. Struktury danych: stosy, kolejki, listy, tablice z haszowaniem, drzewa poszukiwań binarnych, drzewa AVL, drzewa czerwono-czarne.
6. Programowanie dynamiczne, algorytmy zachłanne.
7. Algorytmy grafowe: reprezentacja grafów, przeszukiwanie wszerz, w głąb, sortowanie topologiczne, minimalne drzewa rozpinające, najkrótsze ścieżki, maksymalny przepływ.
8. Wyszukiwanie wzorca.
9. Geometria obliczeniowa.
10. NP-zupełność.
11. Algorytmy aproksymacyjne.

Ćwiczenia laboratoryjne:
Implementacja algorytmów i struktur danych

Implementacja wybranych struktur danych i algorytmów omawianych w czasie wykładu i ćwiczeń audytoryjnych

Ćwiczenia audytoryjne:
Projektowanie algorytmów i struktur danych

1. Ćwiczenia z zakresu szacowania złożoności obliczeniowej dla zadanych algorytmów.
2. Projektowanie algorytmów rozwiązań i struktur danych dla zagadnień modelowych na podstawie algorytmów prezentowanych w trakcie wykładu. Analiza złożoności opracowanych rozwiązań.

Nakład pracy studenta (bilans punktów ECTS)
Forma aktywności studenta Obciążenie studenta
Sumaryczne obciążenie pracą studenta 166 godz
Punkty ECTS za moduł 6 ECTS
Egzamin lub kolokwium zaliczeniowe 2 godz
Samodzielne studiowanie tematyki zajęć 40 godz
Przygotowanie do zajęć 40 godz
Udział w ćwiczeniach laboratoryjnych 14 godz
Udział w wykładach 28 godz
Udział w ćwiczeniach audytoryjnych 28 godz
Dodatkowe godziny kontaktowe z nauczycielem 14 godz
Pozostałe informacje
Sposób obliczania oceny końcowej:

Średnia ważona: 0.5*ocena z egzaminu + 0.3*ocena z ćwiczeń + 0.2*ocena z laboratoriów, przy czym oceny niedostateczne bądź nieusprawiedliwione nieobecności są wliczane do oceny końcowej odpowiednio z wagami 0.15 i 0.05.

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:

1. Cormen T. Leiserson C. Rivest R., Wprowadzenie do algorytmów, WNT 2000.
2. Knuth D., Sztuka Programowania, WNT 2002.
3. N. Wirth, Algorytmy + struktury danych = programy, WNT, 1999.
4. Aho A.V., Hopcroft J.E., Ulman J.D., Projektowanie i analiza algorytmów komputerowych, PWN, 1983.

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

1) Conventional multiscale modeling of microstructure evolution during laminar cooling of DP steel strips / Maciej PIETRZYK, Jan KUSIAK, Roman Kuziak, Łukasz MADEJ, Danuta SZELIGA, Rafał GOŁĄB // Metallurgical and Materials Transactions. A, Physical Metallurgy and Materials ; ISSN 1073-5623. — 2014 vol. 45 iss. 13, s. 5835–5851. — Bibliogr. s. 5850–5851. — Mini-symposiuym on multi-scale modeling of microstructure deformation in material processing. — tekst: http://vls1.icm.edu.pl/cgi-bin/sciserv.pl?collection=springer&journal=10735623&issue=v45i0013&article=5835_cammomlcodss&form=pdf&file=file.pdf

2) Application of sensitivity analysis to grid-based procedure dedicated to creation of SSRVE / Łukasz RAUCH, Danuta SZELIGA, Daniel BACHNIAK, Krzysztof BZOWSKI, Maciej PIETRZYK // W: eScience on distributed computing infrastructure : achievements of PLGrid Plus domain-specific services and tools / eds. Marian Bubak, Jacek Kitowski, Kazimierz Wiatr. — Switzerland : Springer International Publishing, cop. 2014 + CD. — (Lecture Notes in Computer Science ; ISSN 0302-9743 ; 8500). — ISBN: 978-3-319-10893-3 ; e-ISBN: 978-3-319-10894-0. — S. 364–377. — Bibliogr. s. 376–377, Abstr.

3) Sensitivity analysis as a support for optimization of industrial processes — Analiza wrażliwości jako narzędzie wspomagające optymalizację procesów przemysłowych / Danuta SZELIGA, Jan KUSIAK // Computer Methods in Materials Science : quarterly / Akademia Górniczo-Hutnicza ; ISSN 1641-8581. — Tytuł poprz.: Informatyka w Technologii Materiałów. — 2014 vol. 14 no. 1, s. 94–98. — Bibliogr. s. 98, Abstr., Streszcz.

4) Selection of parameters of the heat treatment thermal cycle for rails with respect to the wear resistance / Danuta SZELIGA, Roman Kuziak, Tadeusz Zygmunt, Jan KUSIAK, Maciej PIETRZYK // Steel Research International ; ISSN 1611-3683. — Tytuł poprz.: Steel Research. — 2014 vol. 85 no. 6 spec. iss.: Multiscale modeling, s. 1070–1082. — Bibliogr. s. 1082

5) Data exploration approach versus sensitivity analysis for optimization of metal forming processes / Krzysztof REGULSKI, Danuta SZELIGA, Jan KUSIAK // Key Engineering Materials ; ISSN 1013-9826. — 2014 vols. 611–612, s. 1390–1395. — Bibliogr. s. 1395, Abstr.. — ESAFORM 2014 : 17th conference of the European Scientific Association on Material Forming : May 7–9 2014, Espoo, Finland. — tekst: http://www.scientific.net/KEM.611-612.1390.pdf

Pozostałe:
http://www.bpp.agh.edu.pl/autor/szeliga-danuta-04360

Informacje dodatkowe:

Brak