Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Programowanie i algorytmika 1000-MS1-ProgAlg
Laboratorium (LAB) Semestr zimowy 2019/20

Informacje o zajęciach (wspólne dla wszystkich grup)

Liczba godzin: 60
Limit miejsc: 16
Zaliczenie: Zaliczenie na ocenę
Literatura:

Literatura podstawowa:

[1] M. Sysło, Algorytmy, WSiP, Warszawa

[2] M. Sysło, Piramidy, szyszki i inne konstrukcje algorytmiczne, Helion,

[3] L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych, WNT, Warszawa

[4] M. Dawson, Python dla każdego. Podstawy programowania, Helion

[5] M. Gągolewski, M. Bartoszuk, A. Cena, Przetwarzanie i analiza danych w języku Python

Literatura uzupełniająca:

[6] D. Harel, Rzecz o istocie informatyki: Algorytmika, WNT, Warszawa.

[7] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT, Warszawa.

[8] E. Matthes, Python - instrukcje dla programisty, Helion 2016

Materiały dostępne on-line:

[9] Oficjalna dokumentacja Pythona, http://docs.python.org

[10] Wykłady UW, http://wazniak.mimuw.edu.pl/

[11] Notatki i materiały wykładowcy dostępne na platformie elektronicznego wspomagania zajęć moodle.

Efekty uczenia się:

laboratorium - W1, W2, W3, U1, U2, U3, U4

Metody i kryteria oceniania:

Wykład:

egzamin pisemny składający się z dwóch części:

teoretycznej (wiedza) 50 punktów

praktycznej (umiejętności) 50 punktów

Laboratoria:

Na ocenę końcową składają się oceny za:

1. dwa kolokwia 2*30 punktów

2. sześć zadań domowych 6*5 punktów

3. znajomość zagadnień poruszanych na wykładzie (wejściówka) 1*10 punktów

Aby otrzymać zaliczenie za każdą ze składowych oceny trzeba zdobyć co najmniej 50% punktów. Dopuszczalne są tylko dwie nieobecności nieusprawiedliwione na laboratoriach w semestrze.

Oceny końcowe:

90-100 - bdb

80-89 +db

70-79 db

60-69 +dst

50-59 dst

Zakres tematów:

Tematyka kolejnych wykładów i ćwiczeń jest ściśle skorelowana. Na każdy dwugodzinny wykład przypadają cztery godziny ćwiczeń w laboratorium komputerowym, podczas których implementowane są algorytmy omówione na wykładzie oraz na ich bazie odkrywane są przez studentów algorytmy rozwiązujące problemy pokrewne. Ćwiczona jest przez to również umiejętność efektywnej implementacji rozwiązań w języku programowania Python.

Tematy wykładów i ćwiczeń:

1) Wprowadzenie do algorytmiki - definicja i własności algorytmu, baza algorytmiczna, sposoby zapisywania algorytmów: język naturalny, schematy blokowe dla prostych problemów warunkowych i iteracji, pseudokod, języki programowania [1] [11].

2) Wprowadzenie do języka programowania, syntaktyka i semantyka, struktura programu, zmienne, instrukcje (podstawienia, warunkowa i iteracji), komentarze, korzystanie z dodatkowych bibliotek programistycznych [4][5] - algorytmy dotyczące badania różnorodnych własności liczb i tekstów: podzielność[3], algorytm Euklidesa [1][2], palindromy[11].

3) Procedury i funkcje, przekazywanie parametrów - zastosowanie algorytmu Euklidesa (działania na ułamkach, przelewanie wody) [1][2], systemy liczbowe [1], generowanie liczb o zdanych własnościach [1][2][11].

4) Dokładność obliczeń - losowość danych, błąd względny, błąd bezwzględny obliczeń [11], wyznaczanie miejsc zerowych funkcji metodą połowienia [1], obliczania przybliżonej wartości pierwiastka kwadratowego [1], wielkości pola obszarów zamkniętych[11], liczby pi metodą Monte Carlo [11].

5) Listy, krotki i słowniki, właściwości oraz operacje, jakie można przeprowadzać na tego typu zmiennych [4] [5] - algorytmy wyszukiwania elementów i ciągów o różnorodnych własnościach i porządkowania metodami: bąbelkową, przez wybór, wstawianie, zliczanie [1][2][3].

6) Iteracja a rekurencja - obliczanie wartości elementów ciągu zadanego rekurencyjnie (np. liczb Fibonacciego) metodą rekurencyjną i iteracyjną[1][2]; rekurencyjny algorytm Euklidesa[1][2], obliczania wartości wielomianu za pomocą schematu Hornera[1], szybkie potęgowanie w wersji iteracyjnej i rekurencyjnej[1].

7) Operacje na plikach - podstawowe operacje odczytu i zapisu danych[4].

8) Podstawowe paradygmaty programowania: strukturalne, obiektowe, funkcyjne[4][5][10]. Maszyna Turinga[6]. Złożoność obliczeniowa[6][11].

9) Podstawowe algorytmy geometryczne - położenie punktu względem prostej[3][7], przecinanie się odcinków[3][7], wypukła otoczka[3][7].

10) Grafika: fraktale i wizualizacja metody Monte Carlo[9][11], ruchy Browna[11].

11) Algorytmy na tekstach: wyszukiwanie wzorca[3][7], szyfrowanie[3][7].

12) Algorytmy rekurencyjne: jednoczesne szukanie elementu najmniejszego i największego, sortowanie przez scalanie i szybkie, sortowanie na kopcu[1][3].

13) Podejście zachłanne: wydawanie reszty[11], planowanie zajęć[7], kompresja Huffmana [7].

14) Programowanie dynamiczne: zasada optymalności Bellmana, optymalne nawiasowanie[7], szukanie najdłuższego wspólnego podciągu[7], problem plecakowy[1].

15) Dynamiczne struktury danych: stos, kolejka, lista [4][5] - odwrotna notacja polska[11], sortowania leksykograficzne[1], problem Flawiusza[11].

Metody dydaktyczne:

Laboratoria są prowadzone w laboratorium komputerowym i dotyczą praktycznej realizacji algorytmów w postaci programów prowadzącej do poznania języka programowania oraz rozwiązywania teoretycznych ćwiczeń problemowych pozwalających pogłębić wiedzę przyswojoną w czasie wykładów.

Grupy zajęciowe

zobacz na planie zajęć

Grupa Termin(y) Prowadzący Miejsca Akcje
1 każda środa, 14:00 - 16:00, sala L11
każdy wtorek, 16:00 - 18:00, sala L11
Anna Kwiatkowska 15/16 szczegóły
2 każda środa, 8:00 - 10:00, sala L2
każdy poniedziałek, 12:00 - 14:00, sala L7
Katarzyna Zając 15/16 szczegóły
Wszystkie zajęcia odbywają się w budynku:
Wydział Matematyki i Informatyki
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.