Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu: 1000-213bASD Kod Erasmus / ISCED: 11.302 / (0612) Database and network design and administration
Nazwa przedmiotu: Algorytmy i struktury danych
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty obowiązkowe dla II roku informatyki
Przedmioty obowiązkowe dla III roku JSIM - wariant 3I+4M
Przedmioty obowiązkowe dla III roku JSIM - wariant 3M+4I
Punkty ECTS i inne: 7.50
zobacz reguły punktacji
Język prowadzenia: polski
Rodzaj przedmiotu:

obowiązkowe

Wymagania (lista przedmiotów):

Matematyka dyskretna 1000-212bMD
Wstęp do programowania (podejście funkcyjne) 1000-211bWPF
Wstęp do programowania (podejście imperatywne) 1000-211bWPI

Skrócony opis:

Projektowanie i analiza algorytmów. Przegląd podstawowych algorytmów i struktur danych. Doskonalenie praktycznych umiejętnosci w projektowaniu i programowaniu poprawnych i wydajnych algorytmow oraz w posługiwaniu się gotowymi bibliotekami algorytmów i struktur danych.

Pełny opis:

Podstawowe zasady analizy algorytmów

Metody projektowania wydajnych algorytmów

Sortowanie

Selekcja

Kolejki priorytetowe

Wyszukiwanie i słowniki

Problem "Find-Union" i jego zastosowania

Algorytmy grafowe

Wyszukiwanie wzorca w tekstach

Tekstowe struktury danych

Literatura:

L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, Wydawnictwa Naukowo - Techniczne, 2006.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Wprowadzenie do algorytmów, PWN, 2012.

Efekty uczenia się:

Wiedza

1. Ma uporządkowaną, podbudowaną matematycznie wiedzę z zakresu metod projektowania wydajnych algorytmów i struktur danych oraz ich analizowania pod katem poprawności i złożoności obliczeniowej. (K_W01, K_W02, K_W04)

2. Zna i charakteryzuje pod kątem złożoności i zastosowań najważniejsze algorytmy sortowania, selekcji, wyszukiwania, tekstowe i grafowe. (K_W02, K_W04)

3. Ma wiedzę na temat podstawowych abstrakcyjnych struktur danych (listy, stosy, kolejki, słowniki, kolejki priorytetowe, zbiory, zbiory rozłączne, teksty, grafy) i ich wydajnych implementacji. (K_W02, K_W04, K_W05)

4. Zna biblioteki algorytmów i struktur danych. (K_W09)

5. Ma podstawową wiedzę dotyczącą własności intelektualnej związanej z wykorzystywaniem i modyfikowaniem dostępnych algorytmów i struktur danych. (K_W12)

Umiejętności

1. Potrafi projektować wydajne algorytmy i analizować je pod kątem złożoności obliczeniowej. (K_U01, K_U07)

2. Rozróżnia pojęcia złożoności obliczeniowej problemu od złożoności obliczeniowej algorytmu oraz potrafi oceniać trudności obliczeniowe problemów algorytmicznych i algorytmów. Rozumie znaczenie modelu obliczeń. (K_U01,K_U07)

3. Potrafi właściwie dobrać i zastosować metody projektowania algorytmów oraz znane algorytmy i struktury danych w projektowanych przez siebie rozwiązaniach problemów algorytmicznych. (K_U02, K_U06, K_U07)

4. Potrafi praktycznie implementować zaprojektowane przez siebie algorytmy z wykorzystaniem bibliotek algorytmicznych. (K_U05, K_U09, K_U22, K_U23, K_U25, K_U28)

5. Potrafi testować swoje programy pod kątem złożoności obliczeniowej (K_U25)

6. Potrafi samodzielnie pozyskiwać i wykorzystywać zgodnie z prawem informację na temat algorytmów i struktur danych i ich implementacji. (K_U02, K_U04, K_U30).

7. Potrafi zaprezentować zaprojektowane przez siebie algorytmy i struktury danych w sposób zrozumiały przez innych. (K_U04, K_U29)

Kompetencje

1. Zna ograniczenia własnej wiedzy algorytmicznej i rozumie potrzebę ciągłego dokształcania. (K_K01)

2. Rozumie potrzebę systematycznej pracy i dotrzymywania terminów wykonywanych zadań. (K_K02, K_K05)

3. Rozumie i docenia znaczenie uczciwości intelektualnej w zakresie korzystania z cudzego oprogramowania. Zachowuje się etycznie podczas realizacji projektów algorytmicznych. (K_K03)

4. Samodzielnie potrafić odnaleźć i wykorzystać różnego rodzaju informacje dotyczące algorytmiki, także w językach obcych. (K_K04)

Metody i kryteria oceniania:

Na końcową ocenę składają się oceny cząstkowe za pracę podczas laboratoriów i ćwiczeń oraz za egzamin. Laboratorium polega na zrealizowaniu szeregu projektów programistycznych, których celem jest zaprojektowanie i zaimplementowanie wydajnych algorytmów dla wybranych problemów algorytmicznych. Na ćwiczeniach projektuje się i analizuje teoretycznie algorytmy i struktury danych pod kątem ich złożoności obliczeniowej. Wiedza i umiejętności zdobywane na ćwiczeniach są weryfikowane podczas dwóch klasówek. Osoby z zaliczonym laboratorium i ćwiczeniami przystępują do egzaminu, który składa się z trzech części: praktycznej - weryfikującej praktyczne umiejętności projektowania i implementowania wydajnych algorytmów, testowej - sprawdzającej encyklopedyczną wiedzę podaną na wykładzie oraz zadaniowej - weryfikującą umiejętności zastosowania wiedzy podanej na wykładzie i ćwiczeniach.

Szczegółowe zasady oceniania są podawane studentom z każdą edycją przedmiotu.

Zajęcia w cyklu "Semestr zimowy 2020/21" (w trakcie)

Okres: 2020-10-01 - 2021-01-31
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Ćwiczenia, 30 godzin więcej informacji
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Krzysztof Diks
Prowadzący grup: Krzysztof Diks, Krzysztof Fleszar, Łukasz Kowalik, Mirosław Kowaluk, Jan Ludziejewski, Konrad Majewski, Adam Malinowski, Jana Novotná, Wojciech Plandowski, Juliusz Straszyński, Łukasz Sznuk, Tomasz Waleń, Wiktor Zuba, Anna Zych-Pawlewicz
Lista studentów: (nie masz dostępu)
Zaliczenie: Egzamin
Uwagi:

Algorytmy i Struktury Danych w roku akademickim 2020/2021

Wykład

Koordynator: Krzysztof Diks

Czas: poniedziałki, 10.15 – 11.45

Miejsce: platform https://zoom.us, zaproszenia do uczestnictwa w wykładzie zostaną rozesłane

Plan wykładu

(01) 19.10.2020: algorytm - poprawność i złożoność obliczeniowa algorytmu, model obliczeń i złożoność problemu algorytmicznego, wybrane metody projektowania wydajnych algorytmów

(02) 26.10.2020: sortowanie przez porównania: Insertion Sort, Shell Sort, Merge Sort, Heapsort

(03) 02.11.2020: sortowanie przez porównania, dolna granica w modelu drzew decyzyjnych, sortowanie w czasie “liniowym” i jego zastosowania

(04) 09.11.2020: statystyki pozycyjne i algorytm piątek; Algorytm Dijkstry i jego implementacje

(05) 16.11.2020: koszt zamortyzowany, kolejki priorytetowe: kopce zupełne, kopce dwumianowe, kopce Fibonacciego

(06) 23.11.2020: kopce Fibonacciego - analiza, wyszukiwanie i słowniki, drzew wyszukiwań binarnych, zrównoważone drzewa wyszukiwań binarnych - AVL-drzewa

(07) 30.11.2020: zrównoważone drzewa wyszukiwań binarnych - drzewa typu “splay”, B-drzewa, drzewa czerwono-czarne

(08) 07.12.2020: haszowanie

(09) 15.12.2020: algorytmy grafowe, przeszukiwanie wszerz i w głąb

(10) 22.12.2020: zastosowania przeszukiwania w głąb - dwuspójne i silnie spójne składowe

(11) 11.01.2021: minimalne drzewa rozpinające i problem Find-Union

(12) 18.01.2021: algorytmy tekstowe - wyszukiwanie wzorca w tekście

(13) 25.01.2021: tekstowe struktury danych: drzewa i tablice sufiksowe

Podstawowa literatura

Lech Banachowski, Krzysztof Diks, Wojciech Rytter, Algorytmy i struktury danych, PWN 2018

Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein, Wprowadzenie do algorytmów, PWN 2012

http://smurf.mimuw.edu.pl/?q=algorytmy_i_struktury_danych

Kilka dni przed każdym wykładem zostaną rozesłane materiały prezentowane na tym wykładzie.

Ćwiczenia

Koordynator: Krzysztof Diks

Czas: zgodnie z harmonogramem

Miejsce: platform https://zoom.us, zaproszenia do uczestnictwa w ćwiczeniach zostaną rozesłane przez prowadzących

Organizacja ćwiczeń

- tydzień przed każdymi ćwiczeniami zostaną rozesłane zadania do przerobienia na ćwiczeniach

- studenci są zobowiązani do przygotowania się do ćwiczeń w domu

- studenci zostaną podzieleni na grupy po co najwyżej 3 osoby

- każda grupa jest zobowiązana do (próby) rozwiązania 1-2 zadań z zestawu na ćwiczenia

- na końcu rozwiązania powinny być zapisane w czytelnym pliku pdf, który może być przedstawiony na dzielonej tablicy podczas ćwiczeń

- wskazany członek grupy przeprowadza dyskusję rozwiązania zadania na ćwiczeniach i po ćwiczeniach jest zobowiązany do przygotowania pełnego opisu rozwiązania, które zostanie udostępnione wszystkim członkom grupy

- wszyscy członkowie grupy powinni brać aktywny udział w dyskusji nad rozwiązaniami

- nieprzygotowanie się do ćwiczeń może skutkować ich niezaliczeniem, bez względu na wyniki klasówek (patrz niżej)

Zaliczenie ćwiczeń

Dwie klasówki dla wszystkich: 03.12.2020, 14.01.2021, godz. 16 - 19.

Laboratoria

Koordynator: Tomasz Waleń

Czas: zgodnie z harmonogramem

Miejsce: platforma https://zoom.us (zaproszenia do uczestnictwa w ćwiczeniach zostaną rozesłane przez prowadzących), szkopul.edu.pl

● W trakcie laboratorium będą:

o 2 zadania rozgrzewkowe na pierwszym laboratorium

o 9 zadań zwykłych

o 2 zadania zaliczeniowe

Reguły zaliczania ASD w roku 2020/2021

1. Żeby być dopuszczonym do egzaminu konieczne jest:

● zaliczenie laboratorium

● zaliczenie ćwiczeń (tylko w przypadku I terminu)

2. Egzamin składa się z części praktycznej i pisemnej

egzamin praktyczny:

- każdy student pracuje na swoim koncie i może korzystać z zasobów elektronicznych dostępnych na dysku lokalnym, manuali online do C++, STL oraz z własnych notatek i książek

- kontaktowanie się z innymi osobami będzie karane oceną niedostateczną z egzaminu

- do rozwiązania będą co najmniej dwa zadania w czasie 3 godzin

- żeby zaliczyć egzamin wystarczy rozwiązać w pełni jedno zadanie (zaliczane

automatycznie); za każde następne rozwiązane zadanie uzyskuje się pół oceny więcej

od tej wynikającej z wyników egzaminu pisemnego

- osoby, które nie zaliczą części praktycznej, nie będą dopuszczone do części pisemnej

- osoby, które nie zaliczą części praktycznej w I terminie (jednak zaliczą laboratorium),

mogą warunkowo przystąpić do egzaminu pisemnego w I terminie - wynik tego

egzaminu będzie liczył się pod warunkiem zaliczenia części praktycznej w II terminie

egzamin pisemny

Część 1 (max 20 punktów): test z wykładu i ćwiczeń, zabronione korzystanie z

jakichkolwiek pomocniczych materiałów

Część 2 (max 40 punktów): zadania pisemne; można korzystać z książek i notatek

Łącznie do uzyskania max 100 punktów (klasówki + egzamin). Do zdania egzaminu na pewno wystarczy >= 40 punktów.

Uwaga: wyniki z klasówek !!!!będą!!! liczyły się podczas egzaminu w drugim terminie.

3. Zaliczenie laboratorium

1. Żeby podejść do egzaminu w I terminie, trzeba zaliczyć laboratorium w I terminie. Żeby podejść do egzaminu w II terminie, trzeba zaliczyć laboratorium w I lub II terminie.

2. W trakcie laboratorium będą: 2 zadania rozgrzewkowe na pierwszym laboratorium, 9 zadań zwykłych i 2 zadania zaliczeniowe.

3. Rozwiązania każdego z zadań będzie można nadsyłać online przy użyciu systemu Szkopuł.

Link do rejestracji do zajęć w systemie szkopuł to: zostanie podany w oddzielnym mailu

4. Każde zadanie będzie miało termin zgłaszania rozwiązań. Zadania tegoroczne i archiwalne z laboratorium będą dostępne także w portalu Smurf (http://smurf.mimuw.edu.pl/node/27).

5. Student uzyskuje zaliczenie zadania zwykłego lub rozgrzewkowego przez zaakceptowanie rozwiązania przez system sprawdzający. Rozwiązania zadań zwykłych i rozgrzewkowych są omawiane na kolejnych laboratoriach wyraźnie przed upływem terminu zgłaszania rozwiązań przez Szkopuł.

6. Student uzyskuje zaliczenie zadania zaliczeniowego, jeśli jego rozwiązanie zostanie zaakceptowane przez system sprawdzający ORAZ zostanie zaakceptowane przez laboranta (osobiście).

7. Żeby zaliczyć laboratorium w I terminie, należy rozwiązać w terminie: 1/2 zadanie rozgrzewkowe, 7/9 zadań zwykłych i 2/2 zadania zaliczeniowe.

8. Żeby zaliczyć laboratorium w II terminie, należy rozwiązać najpóźniej na tydzień przed rozpoczęciem egzaminu poprawkowego: 1/2 zadanie rozgrzewkowe, 8/9 zadań zwykłych i 2/2 zadania zaliczeniowe.

9. WSZYSTKIE zadania należy rozwiązywać samodzielnie (dopuszczalne jest dodatkowe konsultowanie się z laborantem w kwestii zadań zwykłych i rozgrzewkowych). Korzystanie z cudzych kodów programów, w tym znalezionych w Internecie, jest niedopuszczalne. Programy powinny działać dla wszystkich możliwych testów spełniających kryteria podane w treści zadania.

4. Zwolnienia

1. Wszyscy studenci, którzy uzyskają odpowiednio dobry wynik w konkursie o zwolnienie z ASD-lab ale muszą przystąpić do egzaminu praktycznego. Konkurs odbędzie się w czwartek 22 października w godz. zostaną podane w oddzielnym mailu . Prosimy o jak najszybsze zgłaszanie chęci udziału w eliminacjach poprzez formularz LINK. Konkurs odbędzie się na zasadach ACM ICPC. Treści zadań są w języku angielskim. Nie należy kopiować kodów powstałych przed rozpoczęciem zawodów (w tym szablonów itp.) i nie należy korzystać z Internetu przy rozwiązywaniu zadań. Konkurs może mieć jedynie implikacje pozytywne (gorszy wynik nie będzie miał żadnego wpływu na zaliczanie przedmiotu).

2. Wszyscy studenci, którzy rozwiązali co najmniej dwa zadania w zeszłorocznym konkursie o zwolnienie z ASD-lab (lub studenci spełniający odpowiedni warunek z jeszcze wcześniejszych lat), są zwolnieni na takich samych zasadach jak w konkursie w tym roku.

3. Osoby, które zaliczyły laboratorium w ubiegłych latach, nie muszą zaliczać go ponownie. Osoby, które zdały egzamin praktyczny w ubiegłych latach, nie muszą zaliczać labu i przystępować do egzaminu praktycznego w tym roku.

5. Zaliczenie ćwiczeń

Trzeba uzyskać co najmniej 10 punktów na 40 z dwóch klasówek. Nie będzie klasówki poprawkowej!

Uwaga: osoby, które powtarzają rok mogą przepisać wyniki z klasówek z lat poprzednich. Proszę o maila w tej sprawie ze wskazaniem roku uczestnictwa w zajęciach i wyników z klasówek, które mają być zaliczone.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.