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

Programowanie i algorytmika

Informacje ogólne

Kod przedmiotu: 1000-MS1-ProgAlg Kod Erasmus / ISCED: (brak danych) / (0541) Matematyka
Nazwa przedmiotu: Programowanie i algorytmika
Jednostka: Wydział Matematyki i Informatyki
Grupy: Matematyka stosowana, 1 rok, studia I stopnia
Przedmioty z polskim językiem wykładowym
Punkty ECTS i inne: 9.00
Język prowadzenia: polski
Wymagania wstępne:

Praca z komputerem w zakresie podstawowym: umiejętność pracy z prostym edytorem tekstowym, uruchamianie aplikacji, korzystanie z serwisów www.

Znajomość matematyki szkolnej na poziomie podstawowym.


Rodzaj przedmiotu:

przedmiot obowiązkowy

Całkowity nakład pracy studenta:

godziny kontaktowe: 30 godz. wykładu + 60 godz. ćwiczeń;

zadania domowe i bieżące przygotowanie się do ćwiczeń: 90 godz.

przygotowanie się do kolokwiów 30 godzin, do egzaminu: 30 godz.

egzamin:2 godziny część pisemna, 2 godziny część praktyczna przy komputerach.


Efekty uczenia się - wiedza:

W1: zna podstawowe pojęcia teorii algorytmów: dane wejściowe i wyjściowe (ich typy), struktury sterujące, mechanizmy iteracji i rekurencji, itp. - K_W02

W2: ma uporządkowaną wiedzę ogólną w zakresie algorytmów, ich złożoności i zastosowań; zna podstawowe metody projektowania algorytmów i przykłady algorytmów wykorzystujących te metody, zna podstawowe struktury danych i wykonywane na nich operacje (tablice, zbiory, struktury dynamiczne) – K_W03

W3: zna przynajmniej jeden język programowania wyższego rzędu w zakresie podstawowym; zna zasady programowania strukturalnego i proceduralnego; zna zasady programowania obiektowego, pojęcie klasy i obiektu, zalety programowania obiektowego i metody oraz przypadki użycia, zasady pracy z obiektami i problemy programistyczne z nimi związane, pojęcie referencji i obiektu; zna zasady dziedziczenia i hierarchicznej budowy programu, obsługę i tworzenie wyjątków, zna przynajmniej dwa narzędzia pracy z kodem źródłowym - K_W04


Efekty uczenia się - umiejętności:

U1: samodzielnie projektuje algorytmy rozwiązujące typowe zadania (obliczeniowe, wyszukujące, porządkujące); potrafi podać specyfikacje algorytmów i zapisać algorytmy w postaci pseudokodu; implementuje algorytmy i dobiera odpowiednie struktury danych; analizuje wpływ struktur danych na złożoność programów - K_U17

U2: potrafi pisać, uruchamiać i testować programy w wybranym środowisku programistycznym; umie czytać ze zrozumieniem programy zapisane w wybranym języku programowania; potrafi pracować z obiektami i projektować programy zorientowane obiektowo; potrafi wykorzystać bibliotekę standardową i złożone struktury danych; potrafi budować hierarchiczną strukturę programu - K_U14

U3: potrafi zaprojektować algorytmy rozwiązujące konkretne problemy matematyczne; potrafi pisać kod odporny na błędy z wykorzystaniem mechanizmu przechwytywania wyjątków - K_U05

U4: potrafi samodzielnie wyszukiwać informacje w literaturze, także w językach obcych - K_U21, KU23


Efekty uczenia się - kompetencje społeczne:

K1: zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia - K_K04

K2: sumienność i dokładność: jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegół; jest systematyczny - K_K02


Metody dydaktyczne:

Wykład ma charakter informacyjno-problemowy. Ważnym elementem wykładu jest wizualizacja działania algorytmów oraz ich implementacji w języku Python z uwzględnieniem optymalnego doboru struktur danych.

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.


Metody dydaktyczne eksponujące:

- drama
- pokaz
- symulacyjna (gier symulacyjnych)

Metody dydaktyczne podające:

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

Metody dydaktyczne poszukujące:

- doświadczeń
- klasyczna metoda problemowa
- projektu
- seminaryjna

Metody dydaktyczne w kształceniu online:

- gry i symulacje
- metody oparte na współpracy
- metody służące prezentacji treści
- metody wymiany i dyskusji

Skrócony opis:

Wprowadzenia w świat algorytmiki i programowania, kształci przy tym myślenie algorytmiczne, doskonali logiczne wnioskowanie. Głównym celem jest przygotowanie do rozwiązywania i programowania rozwiązań zagadnień z matematyki stosowanej przez zapoznanie z podstawowymi algorytmami, strukturami danych i językiem programowania Python

Podczas wykładu są omawiane podstawowe pojęcia teorii algorytmów, klasyczne algorytmy i struktury danych oraz zasady programowania w języku Python. Przy omawianiu kolejnych algorytmów wprowadzane są potrzebne do ich implementacji elementy języka programowania z uwzględnieniem różnorodnych technik i metod.

Podczas zajęć laboratoryjnych kształcone są umiejętności: samodzielnego projektowania algorytmów przez rozwiązywanie typowych zadań (obliczeniowe, wyszukujące, porządkujące), implementacji algorytmów w języku programowania Python z wykorzystaniem standardowych bibliotek i złożonych struktur danych.

Pełny opis:

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].

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.

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 w semestrze.

Oceny końcowe:

90-100 - bdb

80-89 +db

70-79 db

60-69 +dst

50-59 dst

Zajęcia w cyklu "Semestr zimowy 2017/18" (zakończony)

Okres: 2017-10-01 - 2018-02-25
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 60 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 100 miejsc więcej informacji
Koordynatorzy: Anna Kwiatkowska, Łukasz Mikulski
Prowadzący grup: Marcin Gąsiorek, Anna Kwiatkowska, Katarzyna Zając
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Skrócony opis:

Przedmiot wprowadza studenta w świat algorytmiki i programowania, kształci przy tym myślenie algorytmiczne, doskonali logiczne wnioskowanie. Jego głównym celem jest przygotowanie do rozwiązywania i programowania rozwiązań zagadnień z matematyki stosowanej przez zapoznanie z podstawowymi algorytmami, strukturami danych i językiem programowania Python

Podczas wykładu są omawiane podstawowe pojęcia teorii algorytmów, klasyczne algorytmy i struktury danych oraz zasady programowania w języku Python. Przy omawianiu kolejnych algorytmów wprowadzane są potrzebne do ich implementacji elementy języka programowania z uwzględnieniem różnorodnych technik i metod, ze szczególnym uwzględnieniem projektowania iteracyjnego, obiektowego i funkcyjnego.

Podczas zajęć laboratoryjnych kształcone są umiejętności: samodzielnego projektowania algorytmów przez rozwiązywanie typowych zadań (obliczeniowe, wyszukujące, porządkujące), implementacji algorytmów w języku programowania Python z wykorzystaniem standardowych bibliotek i złożonych struktur danych.

Pełny opis:

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].

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.

Zajęcia w cyklu "Semestr zimowy 2018/19" (zakończony)

Okres: 2018-10-01 - 2019-02-24
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 60 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 100 miejsc więcej informacji
Koordynatorzy: Anna Kwiatkowska
Prowadzący grup: Anna Kwiatkowska, Katarzyna Zając
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Skrócony opis:

Przedmiot wprowadza studenta w świat algorytmiki i programowania, kształci przy tym myślenie algorytmiczne, doskonali logiczne wnioskowanie. Jego głównym celem jest przygotowanie do rozwiązywania i programowania rozwiązań zagadnień z matematyki stosowanej przez zapoznanie z podstawowymi algorytmami, strukturami danych i językiem programowania Python

Podczas wykładu są omawiane podstawowe pojęcia teorii algorytmów, klasyczne algorytmy i struktury danych oraz zasady programowania w języku Python. Przy omawianiu kolejnych algorytmów wprowadzane są potrzebne do ich implementacji elementy języka programowania z uwzględnieniem różnorodnych technik i metod, ze szczególnym uwzględnieniem projektowania iteracyjnego, obiektowego i funkcyjnego.

Podczas zajęć laboratoryjnych kształcone są umiejętności: samodzielnego projektowania algorytmów przez rozwiązywanie typowych zadań (obliczeniowe, wyszukujące, porządkujące), implementacji algorytmów w języku programowania Python z wykorzystaniem standardowych bibliotek i złożonych struktur danych.

Pełny opis:

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].

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.

Zajęcia w cyklu "Semestr zimowy 2019/20" (zakończony)

Okres: 2019-10-01 - 2020-02-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 60 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: Anna Kwiatkowska
Prowadzący grup: Anna Kwiatkowska, Katarzyna Zając
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Skrócony opis:

Przedmiot wprowadza studenta w świat algorytmiki i programowania, kształci przy tym myślenie algorytmiczne, doskonali logiczne wnioskowanie. Jego głównym celem jest przygotowanie do rozwiązywania i programowania rozwiązań zagadnień z matematyki stosowanej przez zapoznanie z podstawowymi algorytmami, strukturami danych i językiem programowania Python

Podczas wykładu są omawiane podstawowe pojęcia teorii algorytmów, klasyczne algorytmy i struktury danych oraz zasady programowania w języku Python. Przy omawianiu kolejnych algorytmów wprowadzane są potrzebne do ich implementacji elementy języka programowania z uwzględnieniem różnorodnych technik i metod, ze szczególnym uwzględnieniem projektowania iteracyjnego, obiektowego i funkcyjnego.

Podczas zajęć laboratoryjnych kształcone są umiejętności: samodzielnego projektowania algorytmów przez rozwiązywanie typowych zadań (obliczeniowe, wyszukujące, porządkujące), implementacji algorytmów w języku programowania Python z wykorzystaniem standardowych bibliotek i złożonych struktur danych.

Pełny opis:

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].

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.

Zajęcia w cyklu "Semestr zimowy 2020/21" (jeszcze nie rozpoczęty)

Okres: 2020-10-01 - 2021-02-28
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 60 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 60 miejsc więcej informacji
Koordynatorzy: (brak danych)
Prowadzący grup: (brak danych)
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Skrócony opis:

Przedmiot wprowadza studenta w świat algorytmiki i programowania, kształci przy tym myślenie algorytmiczne, doskonali logiczne wnioskowanie. Jego głównym celem jest przygotowanie do rozwiązywania i programowania rozwiązań zagadnień z matematyki stosowanej przez zapoznanie z podstawowymi algorytmami, strukturami danych i językiem programowania Python

Podczas wykładu są omawiane podstawowe pojęcia teorii algorytmów, klasyczne algorytmy i struktury danych oraz zasady programowania w języku Python. Przy omawianiu kolejnych algorytmów wprowadzane są potrzebne do ich implementacji elementy języka programowania z uwzględnieniem różnorodnych technik i metod, ze szczególnym uwzględnieniem projektowania iteracyjnego, obiektowego i funkcyjnego.

Podczas zajęć laboratoryjnych kształcone są umiejętności: samodzielnego projektowania algorytmów przez rozwiązywanie typowych zadań (obliczeniowe, wyszukujące, porządkujące), implementacji algorytmów w języku programowania Python z wykorzystaniem standardowych bibliotek i złożonych struktur danych.

Pełny opis:

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].

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.

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