Informatyka - liceum klasa 3, zakres rozszerzony
Materiały do wszystkich lekcji informatyki rozszerzonej w klasie 3 liceum (podział rozszerzenia 1-2-2-1, dwie godziny tygodniowo), w kolejności rozkładu materiału zgodnego z podstawą programową: podciągi, stos, kolejka i odwrotna notacja polska, metoda zachłanna, programowanie dynamiczne, grafy i drzewa, bazy danych i SQL, kompresja, sieci komputerowe i kryptografia z szyfrem RSA oraz zespołowy projekt programistyczny. Każda lekcja to przykłady i zadania sprawdzane automatycznie. Bez logowania widać wybrane lekcje, całość nauczyciel przypisuje klasie.
Dla kogo: Klasa 3 liceum, zakres rozszerzony (podział 1-2-2-1, 2 godziny tygodniowo): cały rok informatyki, lekcja po lekcji według rozkładu materiału. Więcej o kursie
Bez logowania widać tylko wybrane przykłady i ćwiczenia. Pozostałe lekcje (na liście z kłódką) nauczyciel udostępnia klasie po przypisaniu kursu, a uczeń otwiera je po zalogowaniu.
Najdłuższy spójny podciąg niemalejący
Najdłuższy fragment niemalejący jednym przebiegiem, granice serii i inne warunki serii.
Spójny podciąg o największej sumie: algorytm Kadane
Największa suma fragmentu: metoda naiwna, algorytm Kadane, granice i największy iloczyn.
Najdłuższy podciąg rosnący i inne własności podciągów
Podciąg a fragment, najdłuższy podciąg rosnący z odtwarzaniem i podciągi naprzemienne.
Struktury danych: tablica, lista, stos i kolejka
Tablica i lista, stos (LIFO), kolejka (FIFO) i dobór struktury do zadania.
Stos w praktyce: poprawność nawiasów
Poprawność nawiasów licznikiem i stosem, miejsce błędu i pary nawiasów.
Kolejka i lista jednokierunkowa
Kolejka cykliczna w tablicy, lista jednokierunkowa i kolejka na węzłach.
Odwrotna notacja polska: obliczanie wartości wyrażenia
Obliczanie wyrażeń w ONP stosem, kolejność argumentów i poprawność zapisu.
Zamiana wyrażenia na odwrotną notację polską
Symbole wyrażenia, algorytm stacji rozrządowej, potęgowanie i zamiana z ONP z powrotem.
Projekt: kalkulator wyrażeń w ONP
Kalkulator z funkcji: symbole, ONP, obliczanie, obsługa błędów i zmienne.
Metoda zachłanna: wydawanie reszty
Reszta największymi nominałami, kwoty w groszach, ograniczona kasa i plecak ciągły.
Kiedy metoda zachłanna zawodzi: kontrprzykład
Kontrprzykłady dla reszty i plecaka, porównanie z przeglądem wszystkich możliwości.
Zachłanne planowanie zajęć i tankowanie na trasie
Planowanie zajęć, liczba sal, tankowanie jak najpóźniej i pokrycie odcinka.
Programowanie dynamiczne: zapamiętywanie wyników podproblemów
Liczba wywołań rekurencji, spamiętywanie w słowniku, drogi w kratce i liczba sposobów.
Metoda wstępująca: tablica wyników podproblemów
Tablica wypełniana od przypadków bazowych: schody, kratka, plecak i sumy z liczb.
Najdłuższy wspólny podciąg
Tablica LCS, odtwarzanie podciągu, najdłuższy wspólny fragment i odległość edycyjna.
Wydawanie reszty dynamicznie i porównanie z metodą zachłanną
Najmniej monet tablicą, odtwarzanie monet, liczba sposobów i porównanie z zachłanną.
Grafy: wierzchołki, krawędzie i modele sytuacji problemowych
Stopnie wierzchołków, grafy skierowane, wagi krawędzi i modele: mapa, znajomi, zależności.
Reprezentacje grafu: macierz i lista sąsiedztwa
Macierz i lista sąsiedztwa, zamiana zapisów, pamięć obu zapisów i macierz wag.
Przeszukiwanie grafu wszerz
BFS kolejką, odległości w krawędziach, odtwarzanie drogi i warstwy grafu.
Przeszukiwanie grafu w głąb i składowe spójności
DFS rekurencyjnie i stosem, składowe spójności, cykle i kolejność zadań.
Najkrótsza droga w grafie z wagami: algorytm Dijkstry
Dijkstra z przeglądem i z kolejką priorytetową, odtwarzanie trasy i wagi ujemne.
Drzewa: drzewo binarne i drzewo poszukiwań
Węzły i wysokość, przejścia drzewa, wyrażenia, drzewo poszukiwań i sortowanie drzewem.
Grafy w zadaniach: labirynt i plansza
Plansza jako graf, najkrótsze wyjście z labiryntu, wyspy, zalewanie i ruchy skoczka.
Porównanie metod algorytmicznych dla jednego problemu
Przegląd, dziel i zwyciężaj, zachłannie i dynamicznie: liczba operacji i poprawność.
Zadania maturalne: struktury danych i grafy
Zestawy na plikach danych: nawiasy, sieć dróg, mapa i drzewo.
Sprawdzian: metody algorytmiczne i struktury danych
Stos i kolejka, metoda zachłanna, programowanie dynamiczne i przeszukiwanie grafów.
Relacyjna baza danych: tabele, klucze i relacje
Baza sklepu: klucz główny i klucze obce, relacje jeden do wielu i wiele do wielu, więzy.
Kwerendy wybierające: SELECT, WHERE i ORDER BY
Kolumny i aliasy, BETWEEN, IN i LIKE, DISTINCT, sortowanie po kilku kolumnach i LIMIT.
Warunki złożone i funkcje w zapytaniach
AND przed OR, funkcje tekstowe, daty (strftime, julianday) i wyrażenie CASE.
Funkcje agregujące, GROUP BY i HAVING
count, sum, avg, min i max, GROUP BY, WHERE a HAVING, grupowanie po miesiącu.
Złączenia wielu tabel: JOIN
Złączenia po kluczu obcym, łańcuch złączeń (wartość zamówień) i LEFT JOIN.
Podzapytania
Podzapytanie jako wartość, IN i NOT IN, podzapytanie skorelowane, EXISTS i w FROM.
Modyfikacja danych: INSERT, UPDATE i DELETE
UPDATE z warunkiem, DELETE z podzapytaniem i INSERT ... SELECT, sprawdzane zapytaniem kontrolnym.
Projekt bazy: normalizacja i diagram związków encji
Anomalie tabeli nieznormalizowanej, rozkład na tabele i diagram związków encji.
Tworzenie tabel i więzy integralności w SQL
Typy i klucz główny, klucz obcy z usuwaniem kaskadowym, UNIQUE i CHECK na kilku polach.
Import danych z plików tekstowych do bazy
Plik z separatorem, polskie daty i liczby, polecenia INSERT i odrzucanie błędnych wierszy.
Baza danych w programie: zapytania SQL z Pythona
Moduł sqlite3, wynik jako lista krotek, parametry zamiast sklejania, WHERE i GROUP BY w Pythonie.
Zadania maturalne z baz danych, część 1
Baza konkursu: uczestnicy z miast, najlepsi, statystyka zadań i ranking szkół.
Zadania maturalne z baz danych, część 2
Brakujące rekordy, klasyfikacja CASE, najlepszy w grupie i zmiany po odwołaniach.
Sprawdzian: bazy danych i SQL
Grupowanie, złączenia i podzapytania, zmiany danych i więzy na bazie sklepu.
Kompresja bezstratna: kodowanie długości serii
Kodowanie długości serii: kodowanie i dekodowanie napisów, zysk z kompresji, wiersze obrazu.
Kod Huffmana: częstsze znaki krótszym kodem
Kod prefiksowy, drzewo Huffmana z kolejką priorytetową, kody z drzewa, kodowanie i dekodowanie bitów.
Kompresja stratna obrazów, dźwięku i filmu
Formaty plików, rozmiar surowych danych, przepływność, kwantyzacja, uśrednianie bloków i różnice klatek filmu.
Sieć komputerowa: urządzenia i ich funkcje
Adres MAC, koncentrator, przełącznik z tablicą adresów i router z bramą domyślną: symulacje w Pythonie.
Model warstwowy i protokoły: TCP/IP, HTTP i DNS
Kapsułkowanie nagłówków, żądanie i odpowiedź HTTP, hierarchia i pamięć podręczna DNS, segmenty TCP.
Adresy IP, maska podsieci i routing
Adres IP jako liczba, maska, adres sieci i rozgłoszeniowy, podział na podsieci, trasa z najdłuższym prefiksem.
Zarządzanie siecią: DHCP, NAT i polecenia diagnostyczne
Pula i dzierżawy DHCP, tablica NAT, odczyt wyników ping i tracert programem.
Uwierzytelnianie: hasła, funkcje skrótu i drugi składnik
Skrót SHA-256 zamiast hasła, atak słownikowy, sól, siła hasła i kod jednorazowy z HMAC.
Kryptografia symetryczna i asymetryczna
Szyfr XOR i Vigenère'a, wymiana klucza Diffiego-Hellmana, liczba kluczy i przegląd wszystkich kluczy.
Szyfrowanie RSA: klucz publiczny i prywatny
Szyfrowanie i odszyfrowanie potęgowaniem modulo, tekst i bloki znaków, złamanie małego klucza.
Odwrotność modulo i generowanie kluczy RSA
Liczby pierwsze p i q, wykładnik e, rozszerzony algorytm Euklidesa, odwrotność modulo i komplet kluczy.
Podpis elektroniczny i certyfikaty
Skrót jako odcisk dokumentu, podpis i weryfikacja kluczami RSA, który klucz do czego, łańcuch certyfikatów.
Bezpieczne połączenia: HTTPS i ochrona danych w sieci
Ważność certyfikatu, nazwy z gwiazdką, mieszana zawartość, co widzi podsłuchujący i lista HSTS.
Otwarte zasoby: licencje i publikowanie własnych materiałów
Prawo autorskie i licencje programów, licencje Creative Commons i otwarte zasoby w projektach.
Projekt: specyfikacja i wybór algorytmów
Specyfikacja danych i wyniku, przypadki testowe i brzegowe, wybór algorytmu i struktury danych według rozmiaru danych.
Projekt: wspólne repozytorium kodu i podział zadań
Historia zmian, różnice między wersjami, łączenie zmian z konfliktem, kolejność zadań według zależności i przydział pracy.
Projekt: implementacja i testy
Testy jako asserty, własny program do testów, poprawianie błędów, wyjątki przy złych danych i testy regresji.
Projekt: dokumentacja i prezentacja rozwiązania
README i instrukcja użytkownika, opracowanie wyników, wystąpienie z prezentacją i ocena rozwiązań zespołów.
Publikacja projektu jako otwartego zasobu
Numery wersji, licencje i ich warunki, README i dziennik zmian, publikacja w Internecie.
Podsumowanie roku: struktury danych, bazy i sieci
Stos i kolejka, przeszukiwanie grafu wszerz, tabele jak w SQL, adresy IP i RSA: przypomnienia i zadania łączące.