Programowanie i algorytmika

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 i obiektowego.

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

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 i obiektowego.

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

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 i obiektowego.

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

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 i obiektowego.

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) Procedury i funkcje, przekazywanie parametrów - zastosowanie algorytmu Euklidesa (działania na ułamkach) [1], systemy liczbowe [1], generowanie liczb o zdanych własnościach [1][2][11].

4) Dokładność obliczeń - 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].

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