Prowadzący: Jędrzej Jabłoński
Zajawka
Druga edycja warsztatów o Sieciach Petriego będzie o czymś zupełnie innym niż pierwsza ;)
Blok ten będzie w rzeczywistości wielką zabawą programistyczną o charakterze konkursowym. Jeśli masz ochotę na sympatyczne klepanie kodu w inteligentnym towarzystwie, albo chcesz się zmierzyć z kolegami w pasjonującej rozgrywce to są to warsztaty właśnie dla Ciebie!
Sieci Petriego? O czym to w ogóle jest?
Podstawową rolą Sieci Petriego jest modelowanie pewnych procesów oraz ich analiza. Przykładowo możliwe jest zbudowanie Sieci Petriego modelującej następujące zachowanie studenta:
Student mieszka w mieszkaniu, w którym ma lodówkę. Student generalnie (jak sama nazwa wskazuje) zajmuje się piciem piwa z lodówki. Jeżeli jednak piwo się skończy to student może wybrać się do sklepu, aby zakupić piwo z tamtejszej lodówki.
oraz analiza problemów typu:
Czy jest możliwe, aby student znajdował się w sklepie, a piwo znikało z jego lodówki?
Czy jest możliwe, aby student doprowadził do takiej sytuacji, w której na pewno nie będzie potrzebował iść do sklepu?
Czy może nastąpić przepełnienie lodówki studenta?
W przypadku studenta i jego piwa tego rodzaju analiza wydaje się śmieszna, jednak istnieją procesy (np. w firmach farmaceutycznych), które potrafią trwać kilkanaście lat i których nikt w całości nie ogarnia. W takich przypadkach analiza typu "czy jeszcze kiedykolwiek użyjemy tych trzystu magazynów", albo "czy nie wyprodukujemy przypadkiem tylu śmieci, że nie będzie gdzie ich zmieścić" wydaje się całkiem rozsądna.
Takie są podstawy zastosowania, ale nauka dotycząca Sieci Petriego zahacza o wiele dziedzin z informatyki i matematyki (takich jak teoria liczb, algebra, teoria złożoności, gal, algorytmy grafowe, rachunek prawdopodobieństwa, logika, teoria języków). Podczas pierwszej edycji warsztatów skupiliśmy się na matematycznych aspekatach Sieci Petriego, oswajaniu z patologicznymi sytuacjami i udowodniliśmy ważne twierdzenie o nieistnieniu algorytmu stwierdzającego osiągalność danego stanu w klasie sieci z "łukami wykluczającymi".
Opis
Tegoroczna edycja warsztatów jest zupełnie inna od poprzedniej, więc warto przyjść ponownie :) W tym roku nie będziemy dowodzić twierdzeń, będziemy pisać algorytmy! Po krótkim wprowadzeniu (przypomnieniu) podstawowych pojęć sformułowane zostanie konkursowe zadanie laboratoryjne. Rozwiązania wraz ze złośliwymi testami dla innych uczestników będzie można składać do ostatniego bloku zajęciowego. W trakcie wszystkich bloków (poza ostatnim) dyskutować będziemy wybrane, znane mi próby podejścia do rozwiązywania problemu.
Wymagania
Wymagana jest umiejętność programowania w języku, który będę umiał skompilować/zinterpretować pod Linuxem. Do takich z pewnością należą:
- C/C++ (GCC)
- Ocaml
- Pascal (FPC)
- Python
- PHP
- Asembler (NASM, GAS)
Jeśli ktoś będzie chciał podczas warsztatów pisać w innym języku i nauczy mnie odpalać programy w nim napisane, to nie będę miał nic przeciwko.
Zadania kwalifikacyjne
Treści zadań dostępne są TUTAJ.
W skład rozwiązania musi wchodzić program rozwiązujący problem (najlepiej w jednym z wymienionych języków), oraz może wchodzić do pięciu zestawów danych wejściowych (przy pomocy których będę testować rozwiązania).
Każde zadanie testowane będzie na dziesięciu moich zestawach danych wejściowych, oraz na wszystkich przesłanych mi wraz z zadaniami. Do zakwalifikowania się z pewnością wystarczy całkowicie poprawne rozwiązanie jednego zadania. Być może próg ten zostanie obniżony.
Wszelkie pytania dotyczące zadań oraz rozwiązania należy wysyłać na adres: ten.epocsodnim|6www-nirolo#ten.epocsodnim|6www-nirolo.
Termin ostateczny jest najprawdopodobniej ustalony z góry, więc nie będę go ani przedłużać, ani skracać.