Przygotowanie XVIII Olimpiady Informatycznej


Dodałem treści zadań z wszystkich dni warsztatów. Są dostępne po kliknięciu małego przycisku Pliki u dołu tej strony. Zadania można wysyłać nadal na systemie Solve System [www.solve.edu.pl]

Prowadzący

Karol Pokorski
Jestem uczniem III Liceum im. Marynarki Wojennej RP w Gdyni. Od paru lat startuję w Olimpiadzie Informatycznej z paroma sukcesami. Rok temu prowadziłem (wydaje mi się, że udane) warsztaty z teorii gier oraz miniwykład o haszowaniu. Kontakt ze mną: moc.liamg|iksrokop.lorak#moc.liamg|iksrokop.lorak lub lp.ude.evlos|iksrokop#lp.ude.evlos|iksrokop.

Opis

Warsztaty potrwają 9 dni i będą stanowiły solidną dawkę wiedzy przydatnej do rozwiązywania zadań informatycznych. Każdego dnia skupimy się na jednym aspekcie (więcej w poddziale Program zajęć). Podczas każdego z dni prowadzony będzie wykład wprowadzający do danych algorytmów/struktur danych, podanych będzie kilka zastosowań do problemów, potem nastąpi chwila przerwy na kanapkę i regenerację sił, następnie praca rozwidla się w zależności od wyboru grupy, do której chce się przynależeć:
konkursowa - praca polega na samodzielnym rozwiązywaniu kilku zadań natury algorytmicznej, powiązanych bezpośrednio lub pośrednio z tematem wykładów. Czas pracy będzie ograniczony, a warunki będą symulowały warunki na Olimpiadzie. Dostępny będzie serwer wydruków, a zadania będą sprawdzane automatycznie (w specjalnym systemie zgłoszeniowym) na zestawie testów przykładowych.
warsztatowa - tak jak w grupie konkursowej rozdaję zadania (te same, co w grupie konkursowej) i wspólnie myślimy nad ich rozwiązaniem, konsultujemy pomysły, ja daję wskazówki. Jeśli starczy czasu, lub ktoś wie jak rozwiązać jakieś zadanie - rozwiązuje je na komputerze - w takiej sytuacji w przypadku problemów z kompilacją/poprawnością ja podchodzę i pomagam.
Po upływie czasu przeznaczonego na rozwiązywanie zadań - przechodzimy do omówienia zadań, na które zaproszone są obie grupy. Na omówieniu przedstawiam symulację wyników (progres najlepszych zawodników w grupie konkursowej w trakcie trwania zawodów). Zawodnicy, którzy poprawnie rozwiązali dane zadanie mogą zostać wytypowani (jeśli chcą) do omówienia zadania, w przeciwnym wypadku ja omawiam dane zadanie. Publikuję najlepsze wyniki z grupy konkursowej oraz wyróżniam pracowitych w grupie warsztatowej. Po warsztatach w czasie wolnym można poprawiać zadania, których się nie zrobiło/zrobiło błędnie. System oceni zgłoszenia automatycznie i poda pełne wyniki oceny natychmiast. Pracowici pod koniec warsztatów zostaną wyróżnieni.
Dwa dni będą wyglądać inaczej. Będzie luźniejszy i krótszy wykład, a zawody będą drużynowe. Będziecie rozwiązywać zadania w trzyosobowych drużynach. Wyniki będą pojawiać się na bieżąco a zawody będą dynamiczne według formuły z ACM ICPC. Wszelkie zasady będą dokładnie wyjaśnione jeszcze przed zawodami. Nie będzie wtedy podziału na grupę warsztatową i konkursową - będzie można tworzyć drużyny według własnego uznania (także mieszając grupy). W szczególnych przypadkach zasugeruję inny skład - nie będę jednak niczego narzucał na siłę.

Program zajęć

Zamierzam poruszyć następujące tematy:

  • algorytmy wykładnicze (wykorzystanie rekurencji, problem ośmiu hetmanów, maski bitowe, funkcja "widełkowa", zasada włączania i wyłączania, metoda meet-in-the-middle)
  • teoria liczb (NWD i NWD, sito Eratostenesa, rozkład na czynniki pierwsze, liczba dzielników liczby, rozszerzony algorytm Euklidesa, odwrotność modularna, małe twierdzenie Fermata, funkcja "fi" Eulera, logarytm dyskretny)
  • przeszukiwanie w głąb (algorytm DFS, sortowanie topologiczne, silnie spójne składowe, numeracja pre- i post-order, dwukolorowanie grafu, cykl Eulera, punkty artykulacji i mosty, dwuspójne składowe, 2-SAT)
  • algorytmy grafowe (alborytm BFS, algorytm Dijkstry, algorytm Bellmana-Forda, algorytm Floyda-Warshalla, najniższy wspólny przodek, drzewa, metoda odcinania liści, Find&Union, minimalne drzewo rozpinające)
  • teoria gier (twierdzenie Sprague-Grundy'ego, definicja pozycji wygrywających i przegrywających, nim-liczby, gra Nim oraz Staircase-Nim)
  • algorytmy tekstowe (funkcja prefiksowa, algorytm Knutha-Morrisa-Pratta, okresy, pierwiastki i szablony słów, lemat o okresowości, algorytm Manachera, drzewo TRIE, słownik podsłów bazowych)
  • programowanie dynamiczne (własność optymalnej podstruktury, problem wydawania reszty, problem plecakowy, najdłuższy wspólny podciąg, najdłuższy podciąg rosnący, odległość Levensteina)
  • przepływy i skojarzenia (definicja przepływu, metoda Forda-Fulkersona, algorytm Edmondsa-Karpa, algorytm Dinica, twierdzenie o maksymalnym przepływie i minimalnym przekroju, sposoby rozwiązywania zadań na przepływy, skojarzenia w grafach dwudzielnych, algorytm Hopcrofta-Karpa, turbo-matching)
  • struktury danych (drzewo potęgowe, drzewo przedziałowe, drzewo licznikowe, kopiec i stos)
  • technikalia (preprocessing, haszowanie, algorytmy i struktury danych działające w czasie pierwiastkowym, wykorzystanie biblioteki STL, wyszukiwanie binarne)

Spodziewam się, że nie wszystko nam się uda - przed warsztatami zostanie zrobiona ankieta, w której będziecie mogli wybrać co ma priorytet. Przeanalizuję to wszystko i te tematy będą analizowane w pierwszej kolejności. Poziom warsztatów będzie dostosowany do waszych wyników i opinii.

Wymagania

  • znajomość pojęcia złożoności obliczeniowej i pamięciowej,
  • biegła umiejętność programowania w co najmniej jednym języku programowania z podanych: C, C++, Pascal (z małym wskazaniem na C++, ale dowolny z tych języków jest akceptowalny),
  • chęci do zdobycia wiedzy i umiejętności przez pracę i zadawanie pytań,
  • umiejętność przyznania się do niewiedzy,
  • znajomość zasad panujących na Olimpiadzie Informatycznej, sposobu oceniania rozwiązań i typu zadań (to zostanie jeszcze powtórzone na pierwszych zajęciach, ale proszę się zaznajomić).

Zadania kwalifikacyjne

Kwalifikacja odbywać się będzie przez automatyczny system zgłoszeniowy (znajduje się on na stronie: [http://www.solve.edu.pl]). Należy się zarejestrować używając swoich prawdziwych danych. Po zalogowaniu należy wybrać konkurs o identyfikatorze WWW-Qual. Do rozwiązania są cztery dość łatwe zadania (na warsztatach spodziewajcie się nieco trudniejszych). Oceniana jest poprawność i efektywność metody użytej do rozwiązania zadania. Każde zadanie oceniane jest w skali 0-100 tak jak na Olimpiadzie Informatycznej. Wybór języka programowania jest częścią rozwiązania zadania. Wyniki dostępne są natychmiast po wysłaniu (w przypadku ich braku proszę o kontakt). Minimum kwalifikacyjne ustalam na 150 punktów (na 400 możliwych). Zadania pojawią się w systemie o północy 1. maja, system zamknie możliwość wysyłania zgłoszeń o północy 16. lipca.

Dodatkowe informacje

Dobrze byłoby mieć własny komputer. Ostatnio były dostępne komputery, ale jednak zawsze wygodniej pracuje się na własnych…

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License