Termin i miejsce zajęć

Egzamin

Wyniki egzaminu pojawią się prawdopodobnie we wtorek.

Narzędzia

Przydatne linki

Literatura

  1. Bradley N. Miller — Problem Solving with Algorithms and Data Structures Using Python, link.
  2. Dusty Phillips — Python 3 Object Oriented Programming, link.
  3. Luciano Ramalho — Fluent Python: Clear, Concise, and Effective Programming.

Omówiony materiał

  1. Złożoność algorytmów: notacja asymptotyczna (O(·), Ω(·) i Θ(·)) oraz eksperymentalne wyznaczanie czasu działania programu (zob. [A, rozdz. 2]), przykłady.
  2. Korzystanie z modułu timeit (zob. [A, rozdz. 2]). Stos i jego zastosowania (odwracanie kolejności, sprawdzanie dobrego nawiasowania oraz zamiana systemów liczbowych) (zob. [A, rozdz. 3]), przykłady.
  3. Odwrotna notacja polska. Kolejka i jej zastosowania (zob. [A, rozdz. 3.9-3.14]), przykłady.
  4. Kolejka dwustronna oraz listy łączone (zob. [A, rozdz. 3.15-3.23]), przykłady.
  5. Wyszukiwanie: sekwencyjne oraz binarne (zob. [A, 5.3-5.4]). Algorytmy sortowania: bąbelkowe, przez wybieranie, przez wstawianie, przez scalanie oraz sortowanie szybkie (zob. [A, rozdz. 5.6-5.12]) , przykłady.
  6. Drzewa, obiektowa implementacja drzew binarnych, parsowanie w pełni nawiasowanych wyrażeń arytmetycznych do drzewa, sposoby przechodzenia drzewa: preorder, inorder oraz postorder (zob. [A, rozdz. 6.2-6.3 oraz 6.5-6.7]), przykłady.
  7. Grafy: sposoby reprezentacji, algorytm przejścia wszerz (BFS) (zob. [A, rozdz. 7.1-7.10]), przykłady.
  8. Analiza obiektowa. Podstawowe pojęcia: asocjacja, kompozycja, dziedziczenie. Diagramy UML: klas i obiektów (zob. [B, rozdz. 1]).
  9. Podstawy dziedziczenia, dziedziczenie wielokrotne, ,,diamond problem" (zob. [B, rozdz. 3]).
  10. Sposoby rozwiązania ,,diamond problem". Monkey patching. Abstrakcyjne klasy bazowe (abc) jako formalna definicja protokołów. Przegląd abc z biblioteki standardowej (zob. [B, rozdz. 3] oraz [C, rozdz. 11]).
  11. Wyjątki (zob. [B. rozdz. 4]).
  12. Wzorce projektowe: dekorator (zob. [B, rozdz. 10]), strategia (zob. [C, rozdz. 6]), obserwator (zob. [B, rozdz. 10]).
  13. Wzorce projektowe: szablon (zob. [B, rozdz. 10]), adapter (zob. [B, rozdz. 11]), polecenie (zob. [B. rozdz. 11]).
  14. Wzorce projektowe: stan (zob. [B, rozdz. 10]), singleton (zob. [B, rozdz. 10]), kompozyt (zob. [B, rozdz. 11]).