Nasz Sylabus

Sylabus koła informatycznego w zakresie algorytmiki i programowania przygotowującego do startu w Olimpiadzie Informatycznej

Sylabus jest przeznaczony dla nauczycieli prowadzących koła zainteresowań przygotowujące uczniów do startu (po raz pierwszy) w Olimpiadzie Informatycznej. Od uczniów oczekuje się zainteresowania rozwiązywaniem problemów algorytmicznych z użyciem komputera, zapału w zdobywaniu nowej wiedzy i nabywaniu oraz pogłębianiu umiejętności w układaniu algorytmów i ich programowaniu. Uczniowie przystępujący do pracy w kole powinni wykazać się także zdolnościami matematycznymi. Przedstawiany sylabus jest podzielony na trzy części: Matematyka, Programowanie i Algorytmika. Dla każdej części jest przedstawiony zestaw zagadnień, z którymi uczeń powinien zapoznać się podczas pracy w kole, a które są istotne w rozwijaniu umiejętności algorytmiczno-programistycznych na poziomie szkoły średniej. Omawianie przedstawionych zagadnień powinno odbywać się wraz z rozwiązywaniem konkretnych problemów algorytmicznych, a nie teoretycznie i w oderwaniu od siebie. Część zagadnień oznaczono symbolem *. Zagadnienie nie oznaczone symbolem *, to zagadnienia, które powinny zostać poruszone w pierwszym roku pracy koła. Zagadnienia oznaczone symbolem * należy omówić i przećwiczyć, ale może to nastąpić w kolejnych latach kształcenia. Zakłada się, że po pierwszym roku pracy w kole uczeń powinien mieć szansę zmierzyć się z zadaniami z I etapu Olimpiady Informatycznej. W prezentowanym sylabusie przyjęto, że językiem programowania używanym do pracy w kole jest C++ ograniczony tylko do jego imperatywnej części. Uznano, że jest to w tej chwili najlepszy język programowania do zapisywania algorytmów, wyposażony na dodatek w bogatą biblioteką algorytmów i struktur danych.

MATEMATYKA

LOGIKA
rachunek zdań, kwantyfikatory (rozumienie), techniki dowodowe (wprost, nie wprost), indukcja (definiowanie i dowodzenie)

ELEMENTARNA TEORIA LICZB
Podzielność, NWD, algorytm Euklidesa (rozszerzony algorytm Euklidesa*), NWW, liczby pierwsze i złożone, rozkład liczby na czynniki pierwsze, testowanie pierwszości (algorytm „pierwiastkowy”), sito Eratostenesa, systemy liczbowe (reprezentacja liczb w komputerze), schemat Hornera, arytmetyka modulo

KOMBINATORYKA (kluczowa w projektowaniu algorytmów)
zbiory i operacje na zbiorach, iloczyn kartezjański, relacje (równoważności, porządek częściowy, porządek liniowy, porządek leksykograficzny), funkcje (różnowartościowa, na, wzajemnie jednoznaczna, składanie funkcji), ciągi (arytmetyczny, geometryczny, liczby Fibonacciego), permutacje, kombinacje (współczynniki dwumianowe), słowa skończone nad skończonym alfabetem, zliczanie obiektów kombinatorycznych, dowody kombinatoryczne, zasada szufladkowa, definicje i równania rekurencyjne, proste metody rozwiązywania równań rekurencyjnych (rozwijanie, argumenty kombinatoryczne)

DYSKRETNY RACHUNEK PRAWDOPODOBIEŃSTWA*
definicja klasyczna, dyskretne zmienne losowe, wartość oczekiwana

GRAFY (skończone)
grafy nieskierowane i skierowane, wierzchołki, stopień wierzchołka, krawędzie, ścieżki, cykle (w tym Eulera i Hamiltona), spójność, silna spójność*, podgrafy, drzewa i lasy, grafy ważone*, drzewa rozpinające, minimalne drzewa rozpinające*, klasy grafów (dwudzielne, planarne*), drzewa ukorzenione, drzewa binarne i ich własności, metody przechodzenia drzew w tym drzew ukorzenionych, metody przechodzenia grafów*, skojarzenia w grafach dwudzielnych*

GEOMETRIA*
geometria analityczna na płaszczyźnie: punkt, odcinek, prosta, wektor, okrąg i koło, wielokąt i jego własności, reprezentacja obiektów geometrycznych w komputerze, metryki Eucklidesowa i miejska, iloczyn skalarny i wektorowy wraz z zastosowaniami

MATERIAŁY ŹRÓDŁOWE

portal: smurf.mimuw.edu.pl/uczesie

Witold Lipski, Kombinatoryka dla programistów, WNT

PROGRAMOWANIE

Środowiska programistyczne (do wyboru)
On-line
ideone.com
repl.it
Desktop
Dev c++
Codeblocks
Wprowadzenie do programowania
Obsługa środowiska programistycznego
System sprawdzający rozwiązania uczniowskie
Zmienne i typy zmiennych (całkowity, rzeczywisty)
Tradycyjne wskaźniki (operatory new, delete i delete[])*
Typ struct*
Wejście i wyjście (strumieniowe), formatowanie wyjścia
Operatory arytmetyczne
Biblioteka matematyczna
Instrukcja warunkowa i operatory logiczne, typ logiczny
Instrukcje iteracyjne
Synchronizacja wejścia/wyjścia strumieniowego
Testowanie programu (przekierowanie strumienia w konsoli, wypisywanie pośrednich wyników)
Tablice statyczne jednowymiarowe
Biblioteka algorithm (sortowanie)
Łańcuchy znaków (typ char, string, rzutowanie typów)
Funkcje, parametry funkcji, zasięg zmiennych
Funkcje rekurencyjne
Struktury danych: stos, kolejka, vector, pair
Tablice dwuwymiarowe
Biblioteka STL*
MATERIAŁY ŹRÓDŁOWE

portal: main2.edu.pl

Wiki Rafała Nowaka: www.rafalnowak.pl>wiki

Karol Kuczmarski, Kurs C++ od zera do gier kodera

ALGORYTMIKA

Metody projektowania algorytmów i strategie algorytmiczne:
specyfikacja, projektowanie pętli – niezmienniki, metoda siłowa (brute force), algorytmy zachłanne, rekurencja, dziel i rządź, programowanie dynamiczne, przeszukiwanie z powrotami, zamiatanie*
Elementy złożoności obliczeniowej: operacja dominująca, złożoność pesymistyczna, notacja asymptotyczna O (wielkie O), podstawowe klasy funkcji złożoności (logarytmiczna, liniowa, nlog n, kwadratowa, sześcienna, wykładnicza)
Algorytmy
Podstawowe algorytmy dla liczb całkowitych: zamiana systemu liczbowego, algorytm Euklidesa (iteracyjny, rekurencyjny), rozszerzony algorytm Euklidesa*, pierwiastkowy test pierwszości, sito Eratostenesa, rozkład na czynniki pierwsze, szybkie potęgowanie
Proste przetwarzanie tablic jednowymiarowych: wypełnianie, przesuwanie (shifting), odwracanie (reversing), przeszukiwanie, przeszukiwanie cykliczne (rotating), znajdowanie minimum/maksimum, wyszukiwanie binarne, sumy prefiksowe, zliczanie, sortowanie przez zliczanie, arytmetyka wielkich liczb
Proste algorytmy dla tekstów, palindromy, wyszukiwanie wzorca w tekście algorytmem naiwnym, algorytm KMP*
Sortowanie: przez wstawianie, sortowanie przez scalanie, sortowanie szybkie*, sortowanie przez kopcowanie*
Proste przetwarzanie tablic dwuwymiarowych: problem 8 hetmanów, wyznaczanie najtańszej drogi z dolnego lewego rogu do górnego prawego rogu w tablicy liczbowej przy ruchach tylko w prawo i do góry, operacje macierzowe*
Przeszukiwanie drzew ukorzenionych (prefiksowe, infiksowe i postfiksowe)
Przeszukiwanie grafów (w głąb i wszerz), drzewo przeszukiwania
Spójność, sortowanie topologiczne, cykl Eulera, dwuspójność*, silna spójność*, domknięcie przechodnie*
Najkrótsze ścieżki (algorytm Dijkstry, Bellmana-Forda, Floyda-Warshall)*
Minimalne drzew rozpinające (algorytmy Prima i Kruskala)*
Skojarzenia w grafach dwudzielnych (algorytm w czasie O(VE))*
Gry kombinatoryczne – algorytm minmax*
Proste algorytm geometryczne na płaszczyźnie*: lokalizacja punktu w wielokącie, wypukła otoczka
Podstawowe abstrakcyjne struktury danych i ich implementacje
Wektor
Stos, kolejka, lista
Reprezentacja grafu (macierz sąsiedztwa, listy sąsiedztwa)
Kopiec binarny
Reprezentacja zbiorów rozłącznych (problem Find-Union)*
Zbiór
Statyczne, zrównoważone drzewa przeszukiwań binarnych (drzewa przedziałowe, drzewa licznikowe), dynamiczne, zrównoważone drzewa przeszukiwań binarnych*, wzbogacanie
Kolejka priorytetowa*
Biblioteka STL*
MATERIAŁY ŹRÓDŁOWE