Środowisko

• Python 3
• PyCharm

Przydatne linki

• Skrypt do wykładu (tylko HTML)
• Programowanie 1 (Python) 2023/2024: wykład, laboratoria
• Złożoność operacji podstawowych kolekcji Pythona
• Definicje i konwencje z wykładów
• UMLet - proste narzędzie do tworzenia diagramów UML
• app.diagrams.net - inne narzędzie rysowania diagramów (w tym UML), online
• Generowanie dokumentacji programów w Pythonie
• Doxygen - jedno z narzędzi generowania dokumentacji

Literatura do wykładu

1. Bradley N. Miller — Problem Solving with Algorithms and Data Structures Using Python, link.
2. Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein — Wprowadzenie do algorytmów.
3. Dusty Phillips — Python 3 Object Oriented Programming, link.
4. Luciano Ramalho — Fluent Python: Clear, Concise, and Effective Programming.

Omówiony materiał

1. Wstęp do analizy złożoności czasowej algorytmów. Notacja asymptotyczna: zbiory O(·), Ω(·) i Θ(·) ich podstawowe własności. Porządek na klasach Θ(·). Rozmiar danych. Przypadek pesymistyczny, optymistyczny i średni. Slajdy. Skrypt.
2. Analiza czasu działania algorytmów, złożoność operacji na kolekcjach Pythona. Stos i jego zastosowania: weryfikacja poprawności nawiasowania, wypisywanie liczby w zadanej podstawie liczbowej. Slajdy. Przykłady: implementacja stosu, sprawdzanie nawiasowania (źródło), animacje weryfikacji nawiasowania. Skrypt (Jupyter notebook + HTML). Bonus: wypisywanie liczby w zadanej podstawie
3. Notacja postfiksowa (odwrotna notacja polska). Konwersja wyrażeń arytmetycznych do ONP i wyliczanie ich wartości. Kolejka i przykłady zastosowań. Materiały + skrypt.
4. Iteratory i generatory. Implementacja iteratora dla stosu przez klasę i przez funkcję generującą. Lista łączona i jej zastosowania: stos i kolejka. Materiały. Bonus (poza wykładem): iteratory ze zwykłych funkcji.
5. Algorytmy sortujące: przez wybieranie, przez wstawianie, przez scalanie, szybkie. Stabilność sortowania. Niezmiennik pętli i złożoność pamięciowa. Materiały.
6. Drzewa i drzewa binarne. Parsowanie wyrażeń arytmetycznych do drzew. Drzewa wyszukiwań binarnych. Materiały.
7. Grafy: skierowane, nieskierowane i ważone. Elementarne sposoby reprezentacji grafów (ważonych): listy (słowniki) sąsiedztwa i macierze sąsiedztwa. Algorytm BFS i znajdowanie najkrótszej drogi w grafie skierowanym. Materiały.
8. Dziedziczenie jednokrotne: specjalizacja do podklas i kolejność wyszukiwania metod. Podstawy języka UML: diagram klas. Opis klas oraz podstawowe relacje. Materiały.
9. Kopce binarne: reprezentacja jako drzewa i implementacja listowa. Zastosowania: sortowanie przez kopcowanie i kolejka priorytetowa. Algorytm Dijkstry szukania najkrótszej ścieżki w skierowanym grafie dodatnio ważonym. Materiały.