Informatyka
Tematy zajęć olimpijskich
Wprowadzenie do informatyki i narzędzi matematycznych
- Czym jest informatyka i algorytm? – wstęp teoretyczny: czym zajmuje się informatyka, pojęcie algorytmu, przykłady prostych procedur krok po kroku.
- Informacja i reprezentacja danych – bity i bajty, systemy liczbowe, reprezentacja znaków (ASCII, Unicode), podstawy przechowywania i przesyłania informacji.
- Złożoność obliczeniowa – intuicja, jak mierzyć czas działania algorytmów, notacja dużego O, podstawowe klasy złożoności, przykłady z praktyki.
- Logika i rozumowanie algorytmiczne – operatory logiczne, implikacja i równoważność, proste zagadki logiczne, wprowadzenie do inwariantów i dowodzenia poprawności algorytmów.
- Arytmetyka modulo, NWD i NWW – działanie w arytmetyce modularnej, algorytm Euklidesa.
- Kombinatoryka – permutacje, wariacje, kombinacje, współczynnik dwumienny, wzór dwumienny Newtona, podstawowe techniki liczenia możliwości.
- Maszyna Turinga / Model obliczeń – idea abstrakcyjnej maszyny obliczeniowej, granice tego, co da się obliczyć, przykłady problemów obliczalnych i nieobliczalnych.
Programowanie w C++ – podstawy i narzędzia
- Wprowadzenie do systemu linux.
- Wprowadzenie do języka C++ – historia i charakterystyka języka, kompilacja i uruchamianie programów, podstawy środowiska programistycznego.
- Pierwszy program, typy danych i zmienne, instrukcje wejścia/wyjścia, komentarze, struktura prostego programu, typy podstawowe, konwersje typów.
- Operatory i instrukcje sterujące – operatory arytmetyczne, logiczne i porównania; instrukcje warunkowe if, else, switch.
- Pętle – for, while, do…while; przykłady zastosowań (sumy, silnie, tablice).
- Wskaźniki i referencje – podstawy wskaźników, różnice między wskaźnikiem a referencją, proste zastosowania.
- Tablice i napisy – tablice jednowymiarowe, podstawy pracy z napisami (string), operacje na elementach.
- Funkcje – deklaracja i definicja funkcji, parametry i wartości zwracane, zasięg zmiennych, rekurencja (podstawy).
- Struktury i typy złożone – struct, proste rekordy danych, metody w strukturach, wprowadzenie do programowania zorganizowanego.
- Wprowadzenie do STL i para (pair) – idea szablonów, pair, operacje porównania i praktyczne zastosowania.
- Kontenery sekwencyjne I – vector – tworzenie, dodawanie/usuwanie elementów, indeksowanie, iteratory, typowe błędy i zastosowania.
- Kontenery sekwencyjne II – deque, stack, queue – kolejka i stos jako adaptery kontenerów, różnice między deque a vector, przykłady użycia.
- Kontenery asocjacyjne I – set, multiset, bitset – operacje podstawowe, unikalność elementów, iteratory, użycie bitset do problemów algorytmicznych.
- Kontenery asocjacyjne II – map, multimap – pary klucz-wartość, iteratory, operacje wstawiania i wyszukiwania.
- Hashowane wersje – unordered_map, unordered_set – różnice względem klasycznych map i setów, złożoność operacji, typowe zastosowania.
- Algorytmy STL – sortowanie (sort), wyszukiwanie binarne (binary_search, lower_bound, upper_bound), generowanie permutacji (next_permutation), przykłady problemów.
- Dobre praktyki i styl pisania kodu – czytelność kodu, komentarze, unikanie błędów początkujących, debugowanie, podstawy profilowania.
Podstawowe algorytmy i techniki
- Sumy prefiksowe – idea sum prefiksowych i tablic różnicowych; zastosowania do szybkiego liczenia sum podprzedziałów; przykłady praktyczne.
- Technika dwóch wskaźników – przesuwane wskaźniki (two pointers); znajdowanie przedziałów spełniających warunki; zastosowania w zadaniach optymalizacyjnych.
- Sortowania proste – sortowanie przez wstawianie, bąbelkowe i wybieranie; analiza złożoności; sytuacje, w których mimo wszystko mogą być przydatne.
- Sortowania szybkie – mergesort i quicksort; idea „dziel i zwyciężaj”; praktyczne użycie std::sort i jego złożoność.
- Sortowania specjalne – sortowanie przez zliczanie, sortowanie kubełkowe, radix sort; ograniczenia i zastosowania przy danych liczbowych.
- Algorytmy zachłanne – konstrukcja rozwiązania krok po kroku; przykłady: wybór aktywności, budowanie największej liczby z cyfr; dowodzenie poprawności algorytmów zachłannych.
- Wyszukiwanie binarne – idea binarnego przeszukiwania; implementacja klasyczna; warianty (lower_bound, upper_bound); typowe błędy implementacyjne.
- Kopiec binarny i kolejka priorytetowa – zasada działania kopca; operacje push/pop; implementacja kolejki priorytetowej (priority_queue w C++); zastosowania.
- Kolejka maksimów i minimum – algorytm liniowy do znajdowania maksimum/minimum w oknie przesuwanym; zastosowania w zadaniach na przedziałach.
- Divide & Conquer – inne zastosowania – znajdowanie maksimum i minimum w tablicy; problem najbliższej pary punktów; rekurencyjne liczenie inwersji.
Teoria złożoności i granice obliczalności
- Notacja asymptotyczna – przypomnienie i pogłębienie – notacje O,Ω,Θ; porównywanie funkcji wzrostu; przykłady algorytmów o różnych złożonościach.
- Klasy P i NP – intuicja pojęć: problemy rozwiązywalne w czasie wielomianowym, problemy sprawdzalne w czasie wielomianowym; przykłady typowych problemów z obu klas.
- NP-zupełność – idea redukcji problemów; klasyczne przykłady (SAT, klik, plecak, pokrycie wierzchołkowe); znaczenie NP-zupełności w praktyce.
- Problemy poza NP i nierozstrzygalność – klasy NP-trudne i PSPACE; problemy nierozstrzygalne (problem stopu, równoważność programów); związki z maszyną Turinga.
- Heurystyki i praktyka – co robić z problemami „zbyt trudnymi” (NP-trudnymi); algorytmy zachłanne, przybliżone, randomizowane jako obejście teoretycznych ograniczeń.
Matematyka w algorytmice
- Arytmetyka modularna – rozszerzenia – dzielenie modulo, elementy odwrotne, Małe Twierdzenie Fermata, szybkie potęgowanie modulo; praktyczne zastosowania w zadaniach.
- Chińskie Twierdzenie o Resztach (CRT) – idea kongruencji, rozwiązywanie układów równań modularnych, przykłady praktyczne.
- Liczby pierwsze i sita – sito Eratostenesa i jego warianty (np. liniowe); testy pierwszości (Miller–Rabin); rozkład na czynniki.
- Funkcje liczbowo-teoretyczne – funkcja Eulera φ, funkcja Möbiusa μ, podstawy liczenia funkcji multiplikatywnych.
- Kombinatoryka – rozszerzenia – zasada inkluzji–ekskluzji; liczenie podzbiorów i permutacji z powtórzeniami; generowanie struktur kombinatorycznych.
- Prawdopodobieństwo w algorytmice – podstawy rachunku prawdopodobieństwa; algorytmy randomizowane (Monte Carlo i Las Vegas) jako praktyczne zastosowania.
Algorytmy na grafach
- Reprezentacje grafów – macierz sąsiedztwa, listy sąsiedztwa, wybór reprezentacji pod kątem złożoności.
- DFS i BFS – przeszukiwanie w głąb i wszerz; kolejka i stos w implementacji; zastosowania w prostych zadaniach.
- Własności grafów nieskierowanych – komponenty spójności, cykle, drzewa i lasy.
- Grafy skierowane – silnie spójne składowe (SCC); algorytmy Kosaraju i Tarjana.
- Sortowanie topologiczne – definicja DAG, algorytmy (DFS + Kahn), zastosowania w zadaniach porządkowych.
- Algorytmy jednokrotnego źródła – Dijkstra (tablica + kopiec), Bellman–Ford.
- Algorytmy wieloźródłowe – Floyd–Warshall; zastosowania do pełnych macierzy odległości.
- Najkrótsze ścieżki w DAG – dynamiczne podejście na grafach acyklicznych.
- Drzewa rozpinające (MST) – Kruskal, Prim, porównanie algorytmów; zastosowania praktyczne.
- Wyszukiwanie centroidu i centroid decomposition – dzielenie drzewa na części; przykłady zastosowań.
- Binary Lifting i LCA – algorytmy do znajdowania najniższego wspólnego przodka; zastosowania w zapytaniach na drzewach.
- Euler Tour i Heavy-Light Decomposition (HLD) – techniki reprezentacji drzew do obsługi zapytań.
- Mosty i punkty artykulacji – definicja, algorytm Tarjana; dwuspójne składowe.
- Grafy planarne – twierdzenie Eulera, wykrywanie planarnych grafów, graf dualny, zastosowania w zadaniach optymalizacyjnych.
- Cykl Eulera i ścieżka Hamiltona – różnice między problemami, algorytm Hierholzera; trudność Hamiltona.
- Grafy dwudzielne – sprawdzanie dwudzielności; dopasowania w grafach dwudzielnych.
- Algorytmy przepływu – Ford–Fulkerson, Edmonds–Karp, Dinic; zastosowania w dopasowaniach i problemach sieciowych.
- Dopasowania ogólne – matching w grafach dwudzielnych (Hungarian, Hopcroft–Karp); wzmianka o Edmonds Blossom.
Programowanie dynamiczne
- Wprowadzenie do DP – idea pamiętania wyników, różnica między tablicowaniem a memoizacją; przykłady prostych rekurencji.
- Klasyczne ciągi i zadania 1D – Fibonacci, liczby Catalana, proste optymalizacje liniowe.
- Plecak (knapsack) – 0/1 knapsack, unbounded knapsack, różne warianty i ich zastosowania.
- Najdłuższy wspólny podciąg (LCS) – rekurencja, tablica 2D, odtwarzanie rozwiązania.
- Najdłuższy rosnący podciąg (LIS) – rozwiązanie O(nlogn), powiązania z grafami.
- Problemy rozdzielania i podziałów – triangulacja wielokąta, optymalne nawiasowanie (matrix chain multiplication).
- DP na drzewach – podproblemy na poddrzewach, klasyczne przykłady (maksymalne niezależne wierzchołki, średnica drzewa).
- DP na grafach acyklicznych (DAG) – liczenie ścieżek, najdłuższe/ najkrótsze ścieżki w DAG, zastosowania do porządków topologicznych.
- DP na planszach i siatkach – klasyczne zadania typu „ścieżki w siatce”, liczenie sposobów przejścia przez kratownicę z przeszkodami.
- Divide & Conquer DP – idea dzielenia przestrzeni decyzji, przykłady zastosowań.
- Convex Hull Trick – optymalizacja DP liniowych, struktury wspierające.
- Knuth i Yao Optimization – specjalne przypadki optymalizacji problemów sekwencyjnych.
Zaawansowane Struktury danych
- Tablice haszujące (hash tables) – idea funkcji mieszającej; kolizje i metody ich obsługi; unordered_map i unordered_set w C++; zastosowania praktyczne.
- Drzewo Fenwicka (BIT) – implementacja; zastosowania do sum prefiksowych i aktualizacji; złożoność i przewagi nad tablicami prefiksowymi.
- Sparse Table – struktura do RMQ i zapytań statycznych; koncepcja preprocesingu; porównanie z Fenwickiem i segment tree.
- Segment Tree – podstawy – implementacja drzewa przedziałowego; operacje update i query; zastosowania (suma, minimum, maksimum).
- Segment Tree z propagacją leniwą – „lazy propagation” do aktualizacji przedziałowych; przykłady zastosowań.
- Segment Tree 2D i warianty – obsługa zapytań na planszach; wady i zalety (złożoność pamięciowa).
- Struktury dynamiczne
- Union-Find (DSU) – znajdowanie reprezentantów, łączenie zbiorów; optymalizacje (path compression, union by rank); zastosowania w grafach.
- Drzewa BST – wprowadzenie – idea drzew poszukiwań binarnych; zrównoważone vs niezrównoważone BST.
- Treapy i Splay Trees – losowe równoważenie w treapach; splay trees i analiza amortyzowana.
- Struktury zaawansowane na drzewach
- Persistent Data Structures – idea niezmienniczości; persistent segment tree; zastosowania w zadaniach offline.
- Heavy-Light Decomposition (HLD) – rozbijanie drzewa na ścieżki; obsługa zapytań na ścieżkach w czasie logarytmicznym.
- Link-Cut Trees (opcjonalnie) – wprowadzenie do struktury do dynamicznych drzew; zastosowania w problemach konkursowych.
Algorytmy na ciągach i napisach
- Naiwne wyszukiwanie i idea prefikso-sufiksów – proste przeszukiwanie liniowe; analiza złożoności; intuicja prefiksów i sufiksów jako wprowadzenie do KMP.
- Algorytm Knutha–Morrisa–Pratta (KMP) – formalne wprowadzenie; budowa tablicy pi; implementacja; przykłady zastosowań.
- Funkcja Z – definicja, implementacja liniowa; zastosowania w wyszukiwaniu wzorców i analizie napisów.
- Rabin–Karp – klasyczny algorytm wyszukiwania wzorca przy użyciu hashy; złożoność i praktyczne użycie.
- Suffix Array – idea tablicy sufiksowej; algorytmy konstrukcji; tablica LCP.
- Drzewo sufiksowe (Suffix Tree) – idea drzewa sufiksowego; algorytm Ukkonena (wzmianka); porównanie z suffix array.
- Tries – budowa drzewa prefiksowego; operacje insert/search; zastosowania w problemach na słowniki.
- Aho–Corasick – automatyczne wyszukiwanie wielu wzorców naraz; implementacja z BFS; zastosowania w problemach konkursowych.
Geometria obliczeniowa
- Podstawy wektorów i układów współrzędnych – reprezentacja punktów, operacje na wektorach, iloczyn skalarny i wektorowy.
- Orientacja punktów i test CCW – sprawdzanie skrętu, położenie punktu względem odcinka, zastosowania w algorytmach.
- Pole wielokąta i własności geometryczne – wzór Shoelace, obliczanie pól, testy wypukłości, własności figur.
- Triangulacja wielokąta – podział wielokąta na trójkąty; zastosowania w dynamicznym programowaniu i grafice.
- Przecięcia odcinków – warunki przecięcia, implementacja, przypadki brzegowe.
- Otoczka wypukła (Convex Hull) – algorytm Grahama i Andrew; zastosowania w zadaniach optymalizacyjnych.
- Najbliższa para punktów – naiwny algorytm; rozwiązanie „divide & conquer” w O(nlogn).
- Algorytmy typu sweep-line – idea zdarzeń i aktywnych obiektów; przecięcia wielu odcinków; zastosowania praktyczne.
Gry i algorytmy kombinatoryczne
- Wprowadzenie i gra Nim – gry dwuosobowe z pełną informacją; brak losowości i remisów; klasyczny Nim i twierdzenie Boutona; interpretacja XOR jako strategii wygrywającej.
- Teoria Sprague–Grundy – definicja funkcji Grundy’ego; dowód redukcji gry do Nim; przykłady zastosowań.
- Gry na grafach – gry w usuwanie krawędzi/wierzchołków, Hackenbush, Kayles; strategie w oparciu o Sprague–Grundy.
- Minimax – klasyczny algorytm przeszukiwania drzewa gry; zastosowanie w prostych grach logicznych.
- Alpha–Beta Pruning – optymalizacja minimaxu; praktyczne znaczenie w ograniczaniu przestrzeni stanów.
Algorytmy zaawansowane i techniki specjalne
- Operacje bitowe w praktyce – manipulacje bitami, maski, szybkie sprawdzanie warunków, zastosowania w problemach kombinatorycznych.
- DP na maskach – klasyczne zadania (TSP, liczenie podzbiorów); implementacja i optymalizacje.
- Kolejność podzbiorów i subset convolution – iterowanie po wszystkich podzbiorach, triki implementacyjne; idea subset convolution i zastosowania.
- Szybkie potęgowanie macierzy – mnożenie macierzy w DP; zastosowania do ciągów i grafów (np. liczenie ścieżek długości k).
- FFT i NTT – szybka transformata Fouriera i numeryczna; mnożenie wielomianów i ciągów; zastosowania w zadaniach.
- Algorytm Mo – idea offline queries; porządkowanie zapytań, przykład z sumami; analiza złożoności.
- Sweep-line w zadaniach ogólnych – technika zdarzeń poza geometrią; zastosowania do przedziałów, zbiorów, zapytań offline.
- Dynamiczna spójność i zapytania offline – technika „rollback DSU”, divide & conquer on queries; przykłady problemów konkursowych.