Algorytmy i programowanie

Znajomość zagadnień z podstaw algorytmiki i języka programowania C++ realizowanych na przedmiocie Podstawy programowania. 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.

przedmiot obowiązkowy

Godziny realizowane z udziałem nauczycieli – 30 godzin laboratorium;

Czas potrzebny na pracę indywidualną studenta - 60 godzin, w tym

- 30 godzin - czytanie literatury, zapoznanie się z materiałami dydaktycznymi umieszczonymi na platformie e-learningowej,

- 15 godzin – przygotowanie do laboratorium

- 15 godzin – powtórzenie materiału z laboratorium

RAZEM: 90 godzin (3 punkty ECTS)

W1: ma uporządkowaną wiedzę ogólną w zakresie podstawowych 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 – K_W03, K_W06

W2: zna przynajmniej jeden język programowania wyższego rzędu w zakresie podstawowym; zna zasady programowania strukturalnego i proceduralnego; zna podstawowe zasady programowania obiektowego, zna przynajmniej dwa narzędzia pracy z kodem źródłowym - K_W04

U1: samodzielnie projektuje/modyfikuje algorytmy w celu rozwiązania problemu; potrafi podać specyfikacje algorytmu i zademonstrować jego działanie; 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, K_U17

U3: potrafi zaprojektować algorytm rozwiązujący konkretny problem z danej dziedziny; potrafi pisać kod odporny na błędy - K_U05

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

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_K04, K_K03

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

Laboratoria są połączeniem metody informacyjno-problemowej z praktyczną realizacją algorytmów w postaci programów w języku Python. Takie podejście ma na celu poznanie języka programowania w wyniku rozwiązywania problemów teoretycznych i pozwala na rozwijanie myślenia komputacyjnego.

- drama
- pokaz
- symulacyjna (gier symulacyjnych)

- opis
- pogadanka
- wykład problemowy

- ćwiczeniowa
- giełda pomysłów
- klasyczna metoda problemowa
- laboratoryjna
- projektu
- stolików eksperckich

- metody oparte na współpracy
- metody rozwijające refleksyjne myślenie
- metody służące prezentacji treści

Przedmiot kontynuuje wprowadzenie w świat algorytmiki i programowania rozpoczęte na przedmiocie Podstawy programowania, doskonali myślenie algorytmiczne i logiczne wnioskowanie. Głównym celem jest przygotowanie do rozwiązywania problemów i programowania podstawowych algorytmów, struktur danych w języku programowania Python.

W trakcie omawianiu kolejnych algorytmów wprowadzane są potrzebne do ich implementacji elementy języka programowania Python z uwzględnieniem różnorodnych technik i metod.

Podczas laboratoriów omawiane są i implementowane algorytmy będące uzupełnieniem zagadnień poruszanych na przedmiocie Podstawy programowania, analizowane są również problemy, w których mają one zastosowanie. Przy rozwiązywaniu problemów wprowadzane są potrzebne do implementacji elementy języka Python z uwzględnieniem złożoności obliczeniowej i efektywności. W opisie poniżej podano kolejne tematy zajęć wraz z rozważanymi podczas nich algorytmami i problemami. Kolokwium I powinno obejmować tematy 1)-7), kolokwium II – tematu 8)-12).

Tematy:

1) Oprogramowanie dla języka Python, tryb interaktywny, edycja, uruchamianie i testowanie programów. Reprezentacja liczb i tekstów w języku Python, konwersja typów.

2) Wprowadzenie do języka programowania Python, syntaktyka i semantyka instrukcji, struktura programu, zmienne, instrukcje (podstawienia, warunkowa i iteracji), korzystanie z funkcji dodatkowych bibliotek programistycznych – algorytmy dotyczące badania różnorodnych własności liczb i tekstów (podzielność, pierwszość, sito Eratostenesa, palindromy). 

3) Funkcje, przekazywanie parametrów, biblioteka funkcji użytkownika (zastosowanie algorytmu Euklidesa, działania na ułamkach, przelewanie wody, punkty kratowe, systemy liczbowe, generowanie liczb o zdanych własnościach). 

4) Listy, krotki - właściwości oraz operacje, jakie można przeprowadzać na tego typu strukturach (zastosowanie algorytmów wyszukiwania i porządkowania, dwa pakowania, problem sumy w ciągach uporządkowanych, przykłady algorytmów z preprocessingiem, np. liczba par AB, szukanie idola, zadanie kajaki i przedziały z OI i ich testowanie).

5) Pobieranie danych i przechowywanie wyników algorytmów w plikach (dane i wyniki liczbowe oraz tekstowe, scalanie plików, występowanie wzorca w tekście).

6) Rekurencja w języku Python (szybkie podnoszenie do potęgi, jednoczesne szukanie elementu najmniejszego i największego, wieże Hanoi, przeszukiwanie z nawrotami, wychodzenie z labiryntu).

7) Słowniki, zbiory – właściwości oraz operacje, jakie można przeprowadzać na tego typu strukturach (reprezentacja rzymska liczb, reprezentacje: macierz sąsiedztwa i lista sąsiadów dla grafów i digrafów).

8) Optymalizacja algorytmów w praktyce (sumy prefiksowe, zapytania o przedziały na sumach prefiksowych, metoda gąsienicy, maksymalny segment, najbliższy mniejszy sąsiad w ciągu, najdalszy mniejszy sąsiad w permutacji, generowanie permutacji, najdłuższy malejący podciąg, równoważność cykliczna ciągów, liczba inwersji permutacji). 

9) Struktury dynamiczne w języku Python: stos, kolejka, lista ich zastosowanie w rozwiązywanych problemach (ONP, sortowanie leksykograficzne, problem Flawiusza, sortowanie topologiczne z wykorzystaniem stopni wierzchołków).

10) Obiektowość języka Python - obiekty, klasy, dziedziczenie, polimorfizm, przeciążanie operatorów (biblioteki dla kopca, grafów, drzew poszukiwań binarnych).

11) Grafika. Ilustracja algorytmów geometrycznych, fraktale, moduł matplotlib (zbiór Cantora, drzewo binarne, płatek Kocha, smok Heighway’a, trójkąt i dywan Sierpińskiego, krzywa Hilberta, kostka Mengera, zbiory Julii, Mandelbrota, i wizualizacja metody Monte Carlo, ruchy Browna). 

12) Podstawy uczenie maszynowego, pakiet pandas i scikit-learn - przykładowy projekt dla uczenia maszynowego: import i wyczyszczenie danych, zbiór treningowy i testowy, wybór modelu uczącego (prognozowanie wyniku, ewaluacja i mierzenie dokładności prognozy, korzystanie z wyuczonych modeli.

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.

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. aktywność podczas zajęć

Weryfikacja efektów W1, W2, 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 nieobecności nieusprawiedliwione w semestrze.

Oceny końcowe:

90-100 - bdb

80-89 +db

70-79 db

60-69 +dst

50-59 dst

Nie dotyczy