Algorytmy i programowanie 1000-SD-AlgProg
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.
Całkowity nakład pracy studenta
Efekty uczenia się - wiedza
Efekty uczenia się - umiejętności
Efekty uczenia się - kompetencje społeczne
Metody dydaktyczne
Metody dydaktyczne eksponujące
- symulacyjna (gier symulacyjnych)
- pokaz
Metody dydaktyczne podające
- pogadanka
- wykład problemowy
Metody dydaktyczne poszukujące
- laboratoryjna
- giełda pomysłów
- stolików eksperckich
- ćwiczeniowa
- projektu
Metody dydaktyczne w kształceniu online
- metody rozwijające refleksyjne myślenie
- metody oparte na współpracy
Rodzaj przedmiotu
Wymagania wstępne
Koordynatorzy przedmiotu
Kryteria oceniania
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
Praktyki zawodowe
Nie dotyczy
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.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: