Programowanie i algorytmika

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.

godziny kontaktowe:

30 godz. wykładu

60 godz. ćwiczeń,

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

przygotowanie się do kolokwiów 20 godz.

przygotowanie się do egzaminu: 20 godz.

Egzamin: 3

Razem 210 godzin

7 pkt. ECTS

W1: ma uporządkowaną wiedzę ogólną w zakresie algorytmów, ich złożoności i zastosowań K_W02, K_W07

W2: zna podstawowe techniki i metody projektowania algorytmów oraz przykłady algorytmów je wykorzystujących, zna podstawowe struktury danych i wykonywane na nich operacje K_W03, K_W07

W3: zna przynajmniej jeden język programowania wyższego rzędu w zakresie podstawowym; zna zasady programowania strukturalnego, zna zasady programowania obiektowego, zna przynajmniej dwa narzędzia pracy z kodem źródłowym, zna ograniczenia w zakresie reprezentacji liczb komputerze. K_W07

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

U2: pisze, uruchamia i testuje programy w wybranym środowisku programistycznym; czyta ze zrozumieniem programy zapisane w wybranym języku programowania; pracuje z obiektami, wykorzystuje biblioteki funkcji i złożone struktury danych, buduje hierarchiczną strukturę programu, K_U13

U3: projektuje algorytm rozwiązujący konkretny problem matematyczny; pisze kod kontrolując niedokładność obliczeń wynikającą z ograniczeń w reprezentacji liczb. K_U13, K_U22

U4: wyszukuje samodzielnie informacje w literaturze, także w językach obcych, K_U26

K1: zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia z wykorzystaniem różnych źródeł informacji, krytycznie ocenia informacje dostępne w Internecie, K_K03

K2: wykonuje zadania sumiennie i dokładnie, jest nastawiony na jak najlepsze wykonanie zadania; dba o szczegół; jest systematyczny. K_K04

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

- drama
- pokaz
- symulacyjna (gier symulacyjnych)

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

- giełda pomysłów
- klasyczna metoda problemowa
- laboratoryjna
- obserwacji
- projektu

- gry i symulacje
- metody oparte na współpracy
- metody rozwijające refleksyjne myślenie

Przedmiot wprowadza 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 przez zapoznanie z podstawowymi algorytmami, struktura 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.

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

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

Weryfikacja efektów W1, W2, W3

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 2*5 punktów

Weryfikacja efektów U1, U2, U3, U4, K1, K2

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

nie dotyczy

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.

Jak w podstawowej informacji o przedmiocie.