Programowanie i algorytmika 1000-MS1-ProgAlg
Laboratorium (LAB) Semestr zimowy 2018/19

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

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