Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowania
Strona główna

Algorytmy II

Informacje ogólne

Kod przedmiotu: 0800-ALGOR2
Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Algorytmy II
Jednostka: Wydział Fizyki, Astronomii i Informatyki Stosowanej
Grupy:
Punkty ECTS i inne: 7.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.
Język prowadzenia: polski
Wymagania wstępne:

Algorytmy i struktury danych, Języki programowania. Programowanie obiektowe.

Całkowity nakład pracy studenta:

Wykład: 30H

ćwiczenia: 15H

Laboratoria: 45H

Praca indywidualna: 100H

Efekty uczenia się - wiedza:

Zaawansowana znajomość i umiejętność wykorzystania ważnych algorytmów.

Pogłębiona analiza złożoności algorytmów.

Umiejętność wybory algorytmu do problemu i struktur danych.

Elementy pracy zespołowej.

Wiedza o zaawansowanych struktura danych i algorytmach.

Posługiwanie się językami programistycznymi.


W 1, 2, 5



Efekty uczenia się - umiejętności:

Umiejętność zaawansowanej analizy algorytmu.

Umiejętność wykorzystania algorytmów.

Umiejętność oceny złożoności algorytmów.

Umiejętność podziału problemu na podproblemy.

Umiejętność implementacji zaawansowanych algorytmów i struktur danych.

Umiejętność posługiwania się złożonymi strukturami danych


U 5, 7


Efekty uczenia się - kompetencje społeczne:

ma świadomość skutków wadliwie działających systemów informatycznych, które mogą doprowadzić do strat moralnych i finansowych, a nawet utraty zdrowia czy zagrożenia życia


K 2

Metody dydaktyczne:

Wykład: prezentacja materiału i problemów, dyskusja

Ćwiczenia: omawianie zagadnień i ich analiza, wspólne i indywidualne rozwiązywanie zadań. Analiza przypadków. Częściowo praca grupowa.

Laboratoria: Nacisk na indywidualne rozwiązywanie problemów + pomoc eksperta. Dyskusja nad przykładami rozwiązań.

Metody dydaktyczne eksponujące:

- pokaz

Metody dydaktyczne podające:

- wykład informacyjny (konwencjonalny)
- wykład problemowy

Metody dydaktyczne poszukujące:

- ćwiczeniowa
- doświadczeń
- giełda pomysłów
- klasyczna metoda problemowa
- obserwacji
- projektu
- punktowana
- studium przypadku
- sytuacyjna

Metody dydaktyczne w kształceniu online:

- metody integracyjne
- metody odnoszące się do autentycznych lub fikcyjnych sytuacji
- metody oparte na współpracy
- metody rozwijające refleksyjne myślenie
- metody wymiany i dyskusji

Skrócony opis:

Jest to cykl zajęć (wykład, ćwiczenia i laboratorium) poświęcone bardziej zaawansowanej części algorytmów ale także struktur danych.

Poruszane są też ważne aspekty związane ze złożonością obliczeniową.

Pełny opis:

Na zagadnienia wykładu, ćwiczeń i laboratoriów składają się:

1. Algorytmy z powrotami

a. Problem skoczka szachowego

b. Problem ośmiu hetmanów

c. Ogólny algorytm z powrotami

d. Wieże Hanoi, permutacje, kombinacje (z/bez powtórzeń)

2. Problemy plecakowe (ciągłe i dyskretne)

3. Algorytmy i struktury danych dla operacji zbiorowych

a. Algorytmy i struktury naiwne

b. Haszowanie (zbiory i słowniki)

c. Drzewa zrównoważone

d. Listy z dowiązaniami

e. Problem Unio-Find

4. Silnie spójne składowe grafu

5. Cykle Eulera i Hamiltona

6. Problem maksymalnego przepływu

7. Klasy złożoności

8. Kopce Fibonacciego

9. Automaty i wyrażenia regularne

10. Wyszukiwanie wzorców

a. Algorytm naiwny

b. Algorytmy szybkie, automaty

c. Drzewa sufiksowe

11. Problem spełnialności reguł logicznych

12. Geometria obliczeniowa - podstawy

Literatura:

A. V. Aho, J. E. Hopcroft, J. D. Ullman.

Projektowanie i analiza algorytmów.

Helion, Warszawa, 2003.

A. V. Aho, J. E. Hopcroft, J. D. Ullman.

Projektowanie i analiza algorytmów.

Państwowe Wydawnictwa Naukowe, Warszawa, 1983.

Niklaus Wirth.

Algorytmy + Struktury Danych = Programy.

Wydawnictwa Naukowo–Techniczne, Warszawa, wydanie 2, 1989.

T. H. Cormen, C. E. Leiserson, R. L Rivest.

Wprowadzenie do algorytmów.

Wydawnictwa Naukowo–Techniczne, Warszawa, 1997.

A. V. Aho, J. D. Ullman.

Wykłady z informatyki z przykładami w języku C.

Helion, Warszawa, 2003.

L. Banachowski, K. Diks, W. Rytter.

Algorytmy i struktury danych.

Wydawnictwa Naukowo–Techniczne, Warszawa, 1996.

M. M. Sysło, N. Deo, J. Kowalik.

Algorytmy optymalizacji dyskretnej.

Państwowe Wydawnictwa Naukowe, Warszawa, 1993.

D. Harel.

Rzecz o istocie informatyki. Algorytmika.

Wydawnictwa Naukowo–Techniczne, Warszawa, 1992.

L. Banachowski, A. Kreczmar, W. Rytter.

Analiza algorytmów i struktur danych.

Wydawnictwa Naukowo–Techniczne, Warszawa, 1989.

L. Banachowski, A. Kreczmar.

Elementy analizy algorytmów.

Wydawnictwa Naukowo–Techniczne, Warszawa, 1982.

D. E. Knuth.

Sztuka Programowania, wolumen I–III.

Wydawnictwa Naukowo–Techniczne, 2002.

Metody i kryteria oceniania:

1. Bieżąca praca. W 1, 2, 5, U 5, 7, K 2

2. Kolokwia pisemne. W 1, 2, 5, U 5, 7, K 2

3. Zadania bieżące (listy zadań i programów). W 1, 2, 5, U 5, 7, K 2

4. Wejściówki (w zależności od potrzeb). W 1, 2, 5, U 5, 7, K 2

5. Egzamin pisemny lub zadania koncepcyjne. W 1, 2, 5, U 5, 7, K 2

Powyższe metody oceny weryfikują zakres programu jak i efekty kształcenia opisane powyżej.

Ocena kolokwium i egzaminu pisemnego: minimum 50%, poniżej 2.0, od 50% (3.0) ocena skalowana liniowo do 5.0

Ocena ćwiczeń jest składową oceny kolokwium (podstawa oceny), pracy bieżącej, i innych dodatkowych zadań.

W przypadku egzaminu poprzez zadania koncepcyjne ocena jest średnią oceny wykonanych zadań egzaminacyjnych (które muszą być zrobione), oceny z ćwiczeń i laboratorium.

Ocena laboratorium: minimalnie trzeba wykonać około 80% zadań (zależne od bieżącej listy zadań), zadania są oceniane na podstawie jakości realizacji poszczególnych zadań. Ocena jest średnią ocen poszczególnych zadań. W przypadku braku rozwiązania wszystkich zadań ocena jest pomniejszana: 1% wszystkich zadań = 0.1 oceny (np. brak 10% zadań = ocena o 1.0 w dół).

W pracy bieżącej, na kolokwiach, na laboratoriach i egzaminie weryfikuje się wszystkie efekty uczenia się: wiedzy, umiejętności i kompetencje społeczne.

Zajęcia w cyklu "Semestr zimowy 2021/22" (zakończony)

Okres: 2021-10-01 - 2022-02-20
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 15 godzin więcej informacji
Laboratorium, 45 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Norbert Jankowski
Prowadzący grup: Norbert Jankowski, Miłosz Michalski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2022/23" (zakończony)

Okres: 2022-10-01 - 2023-02-19
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 15 godzin więcej informacji
Laboratorium, 45 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Norbert Jankowski
Prowadzący grup: Norbert Jankowski, Miłosz Michalski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin

Zajęcia w cyklu "Semestr zimowy 2023/24" (zakończony)

Okres: 2023-10-01 - 2024-02-19
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Ćwiczenia, 15 godzin więcej informacji
Laboratorium, 45 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Norbert Jankowski
Prowadzący grup: Norbert Jankowski, Miłosz Michalski
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Ćwiczenia - Zaliczenie na ocenę
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.
ul. Jurija Gagarina 11, 87-100 Toruń tel: +48 56 611-40-10 https://usosweb.umk.pl/ kontakt deklaracja dostępności USOSweb 7.0.2.0-1 (2024-03-12)