NOMAD (VI)

Data ostatniej modyfikacji:
2016-04-20
Autor: 
Joanna Polechońska
nauczycielka w GIM 1 we Wrocławiu
Organizator: 

Koło Naukowe Statystyki Matematycznej GAUSS
Instytut Matematyki i Informatyki PWr
ul. Janiszewskiego 14a,
50-372 Wrocław
mail: gauss@pwr.wroc.pl
http://nomad.im.pwr.wroc.pl

 

Terminy: 

eliminacje internetowe - 21 V 2016, godz. 10-15
finał na PWr - 4 VI 2016, godz. 10-15

 

Niezależne Ogólnopolskie Mistrzostwa w Analizie Danych (NOMAD) organizowane są przez Koło Naukowe Statystyki Matematycznej "Gauss" działające przy Instytucie Matematyki i Informatyki Politechniki Wrocławskiej. Startują w nich uczniowie szkół średnich i studenci. Podczas zawodów za pomocą samodzielnie napisanych programów rozwiązują problemy praktyczne, często znane im z codziennego życia. Szkoda, że wbrew nazwie, zawody są zwykłym konkursem programistycznym i nie mają związku z ciekawą dziedziną zastosowań matematyki – statystyką i analizą danych.

Do konkursu mogą zgłaszać się trzyosobowe drużyny, które startują w jednej z dwóch kategorii wiekowych: uczniowie szkól ponadgimnazjalnych oraz studenci. Zawody są dwuetapowe. Zgłoszenia i eliminacje odbywają się przez internet, a finał - w siedzibie organizatora we Wrocławiu. W obu etapach należy rozwiązać w ciągu 5 godzin 5 zadań, które wymagają zastosowania metod informatycznych do problemów analizy danych. Przed przystąpieniem do konkursu warto zapoznać się na jego stronie domowej z przykładami zadań, ich rozwiązaniami oraz sposobem ich oceniania.

Współorganizatorem konkursu jest Fundacja Rozwoju Politechniki Wrocławskiej. Konkurs ma wielu sponsorów, którzy zapewniają atrakcyjne nagrody: kursy szkoleniowe, książki, czasopisma oraz sprzęt multimedialny.

 

Historia: 

Pierwsza edycja Mistrzostw odbyła się w roku 2011.

 

Skrót regulaminu: 
  • Zgłoszenie do konkursu następuje przez wypełnienie formularza na stronie organizatora.
  • Do zawodów mogą zgłaszać sie zespoły składające się maksymalnie z trzech osób.
  • Konkurs odbywa się w dwóch kategoriach wiekowych: uczniów szkół ponadgimnazjalnych oraz studentów.
  • Zawody składają się z dwóch etapów.
  • Eliminacje odbywają się przez internet i polegają na rozwiązaniu 5 zadań w ciągu 5 godzin. W eliminacjach uczestnicy zobowiązani są sami zapewnić sobie odpowiednie oprogramowania pozwalające na start w zawodach.
  • Finał odbywa się we Wrocławiu w laboratoriach Politechniki Wrocławskiej.
  • Do finału przechodzi po 10 najlepszych drużyn z każdej kategorii.
  • W finale uczestnicy rozwiązują 5 zadań w ciągu 5 godzin. Za każde rozwiązane zadanie drużyna otrzymuje jeden punkt. Dodatkowo rejestrowany jest czas uzyskania poprawnego rozwiązania. Za zgłoszenie błędnego rozwiązania drużyna otrzymuje karę w wysokości 20 minut.
  • Zwycięzcy wyłaniani są na podstawie sumy uzyskanych punktów. W przypadku remisu o kolejności decyduje łączny czas rozwiązywania zadań.
  • Skład sędziowski wyznacza Zarząd Koła Naukowego Statystyki Matematycznej „Gauss” w porozumieniu z jego opiekunami naukowymi.
  • Rozstrzygnięcie konkursu i wręczenie nagród następuje w dniu zawodów.

    

Przykładowe zadania: 

ELIMINACJE

szkoły ponadgimnazjalne

Deszcz meteorytów. Podczas podróży kosmicznej jeden z nomadów podróżujący statkiem Dromader 13 wpadł w deszcz meteorytów. Aby zwiększyć swoje szanse przeżycia, musi poinformować pozostałych o swoim problemie — być może będą potrafili mu pomóc. Może to zrobić, przesyłając wiadomość za pomocą alfabetu Morse’a. Wiadomość taka składa się z 3 sygnałów. Nomad może nadać 4 rodzaje informacji:
kropka-kropka-kropka — koniec paliwa,
kreska-kreska-kreska — atak obcych,
kreska-kropka-kreska — deszcz meteorytów,
kropka-kreska-kropka —czarna dziura.
Wiadomości te wysyła się odpowiednio za pomocą przycisków I, II, III lub IV. Z powodu turbulencji nomad naciśnie guzik I z prawdopodobieństwem p1, II z p2, III z p3 lub IV z p4. Sygnały podlegają jednak losowym zakłóceniom przez pył kosmiczny. W rezultacie sygnał 'kropka' może być odebrany jako 'kreska' z prawdopodobieństwem k, zaś sygnał 'kreska' może być odebrany jako 'kropka' z prawdopodobieństwem l. Nomadowie zbadali, że sygnały 'kropka' i 'kreska' są poddawane zniekształceniom niezależnie. W nomadzkiej bazie odebrano sygnał kreska-kropka-kreska. Jakie jest prawdopodobieństwo, że została nadana informacja o rzeczywistych kłopotach nomada? Wejście składa się z jednej linii, w której podane są prawdopodobieństwa p1, p2, p3, p4, k, l.

Przykładowe wejścia:
0.2370 0.1880 0.3280 0.2470 0.1100 0.0709
0.2750 0.0790 0.3420 0.3040 0.1920 0.3260
Przykładowe wyjścia:
0.9460071
0.8496416

szkoły wyższe

Droga mleczna. Gospodarka kosmicznych nomadów, podobnie jak ich ziemskich braci, opiera się głównie na hodowli wielbłądów. Międzygalaktyczni koczownicy traktują te zwierzęta jak członków rodziny, czemu trudno się dziwić — z mleka kosmicznych wielbłądów można wyprodukować nomadinę — wysokoenergetyczne paliwo dla statków, które postacią przypomina najzwyklejszą we wszechświecie bryndzę. Niestety, kosmiczne wielbłądzice nie należą do najbardziej ugodowych, więc bardzo trudno jest o to, by dostawy ich mleka zawsze osiągały oczekiwany poziom. Okazuje się, że skłonność wielbłądzic do współpracy można w pewnym stopniu przewidzieć. Raszyd Selim Al-Malouf, nomadzki businessman, który zbił majątek na handlu wielbłądzim mlekiem, twierdzi, że ilość mleka wyprodukowanego danego dnia zależy w sposób liniowy od kilku ostatnich wartości tego wskaźnika, a zależność ta jest niezmienna w czasie. Jakby tego było mało, Raszydowi wystarcza tylko chwila przypatrywania się danym dotyczącym produkcji, aby stwierdzić, jaki jest jej rząd wspomnianej zależności. Wiedzę tę można wykorzystać, by na podstawie zaobserwowanych danych przewidzieć, ile mleka można będzie wyprodukować w przyszłości. Pojedyncze wejście programu składa się z dwóch linii. Pierwsza informacja to wskazówka Raszyda — liczba ostatnich obserwacji mających wpływ na wskaźnik produkcji mleka. Druga linia to dane dotyczące produkcji z k kolejnych dni. Zadaniem jest zaprognozowanie ilości wyprodukowanego mleka w dniu k + 1.

Przykładowe wejścia:
2
67.830 67.699 65.745 67.544 63.300 63.287 63.227 67.012 69.281 71.892 70.993 71.086 70.557
3
130.9174 120.2749 126.2859 123.4186 124.3474 123.8648 123.2041 123.7942 124.9461
Przykładowe wyjścia:

70.895
124.181

FINAŁ

szkoły ponadgimnazjalne

Flota wojenna. NASA (Nomad Aeronautics and Space Administration) na zlecenie dowódcy Damona przygotowuje flotę wojenną na wypadek ataku ze strony obcych cywilizacji. NASA rozważa rozmieszczenie k uzbrojonych statków kosmicznych w n oddziałach. Jednostki wysyłane będą do walki oddział po oddziale, możliwe jest również wzięcie wroga na przeczekanie, co aby nie komplikować instrukcji dla pilotów, NASA również nazywa zero-osobowym oddziałem. W zależności od rodzaju uzbrojenia statków obecny plan przewiduje, że możliwa jest jedna z trzech następujących strategii:
1. Dell Nomadell to strategia, w której statki różnią się między sobą pod względem uzbrojenia. Przesunięcie jednostki między oddziałami daje zatem nową formację. Liczba statków w jednym oddziale jest dowolna.
2. Osa Nomadosa to strategia, w której statki mają identyczne uzbrojenie. Zamiana dwóch jednostek miejscami nie zmienia formacji.
3. Dino Nomadino to strategia, w której statki nie różnią się miedzy sobą, a w każdym oddziale może znaleźć się co najwyżej jeden statek.
NASA zastanawia się, czy rozsądne jest, aby piloci sami wybierali sobie formację w jakiej lecą. Wiadomo, że wielu z nich to indywidualiści i możliwe jest, że będą tworzyć oddziały jednoosobowe, czyli będą tak zwanymi wolnymi strzelcami. O ile wolni strzelcy są potrzebni w każdej formacji, ważne są też większe, współpracujące ze sobą oddziały. Najbardziej niekorzystne rozstawienie statków to tak zwany Rząd Straceńców czyli formacja, w której wszystkie jednostki pełnią rolę wolnych strzelców i znajdują się jeden po drugim na początku formacji. Oczywiście, Damon tego nie chce, zatem zlecił Ci obliczenie prawdopodobieństwa, że gdy pilotom pozostawić wolny wybór, ustawią się w Rząd Straceńców.
Ponieważ od dawna nie dostałeś podwyżki, chcesz wykonać nieco dodatkowej pracy, by mieć jakieś podstawy do negocjacji nowej stawki. NASA nagradza aktywnych! Zauważyłeś, że w przypadku formacji Osa Nomadosa korzystne jest pojawienie się tak zwanej tarczy, czyli pewnej liczby jednostek lecących w ostatnim oddziale. Zatem do każdej analizy strategii Osa Nomadosa, postanowiłeś dodatkowo obliczać, jakie jest prawdopodobieństwo, że w ostatnim oddziale znajdzie się dokładnie m statków, nie biorąc pod uwagę, jak rozmieszczą się pozostałe jednostki. Wejście składa się z wielu przypadków, po jednym w linii. W każdej linii podana jest odpowiednio: liczba oddziałów, liczba statków i skrócona do pierwszego członu nazwa strategii. W przypadku wybrania strategii Osa Nomadosa podana jest dodatkowo liczba m statków w tarczy.

Przykładowe wejścia:
3 2 Dell
5 4 Osa 3
Przykładowe wyjścia:
0.222222222222
0.0142857142857 0.0571428571429

szkoły wyższe
Odyseja kosmiczna. Pilot statku kosmicznego to zawód cieszący się ogromnym poważaniem w społeczności nomadów, trudno się więc dziwić, że tak wielu młodych śmiałków pragnie zostać adeptami sztuki pilotażu. Niestety, nie każdy posiada zdolności do wykonywania tego zawodu, a co gorsza, ostatnimi czasy nie wszystkie niedorajdy udaje się wykluczyć podczas wyboru kandydatów na pilotów. Nomadzcy naukowcy postanowili znaleźć sposób, by skuteczność selekcji zdecydowanie poprawić. Naukowcy zaprojektowali więc wirtualną Nomadię. W tym nierzeczywistym świecie można poruszać się tylko po dwuwymiarowej kracie całkowitej, która w każdym punkcie wygląda tak samo. Kandydat na starcie w punkcie (0, 0) dowiaduje się, w którym kierunku powinien podążać. Następnie w chwilach i = 1, ... , n porusza się o jeden na wschód bądź zachód (Xi) oraz o jeden na północ bądź południe (Yi). Już po kilku krokach można wywnioskować, czy testowany nadaje się na pilota — jeśli badany jest zdolny zostać asem międzygalaktycznych przestworzy, to ciągle pamięta o celu podróży, dlatego jego wertykalne i horyzontalne decyzje są zależne.
Każde dwie linie wejścia programu to kolejno x-owe i y-owe współrzędne położenia danego kandydata w wirtualnej Nomadii. Na wyjściu zwróć 1, jeśli decyzje kandydata były zależne. W przeciwnym wypadku zwróć 0.

Przykładowe wejścia:
1 0 1 0 1 0 1 2 1 2 1 2 3 4 3 2 1 0
-1 -2 -3 -4 -3 -4 -3 -2 -3 -4 -5 -6 -5 -6 -5 -4 -3 -2
-1 0 -1 0 1 2 3 2 1 2 3 2 3 4 5 4
1 2 3 4 3 2 3 4 5 4 3 4 5 4 3 4

Przykładowe wyjścia:
0
1

 

Co z maturzystami?

Czy tegoroczni maturzyści mogą startować w tym konkursie w swojej szkole, którą ukończyli, tj. jeszcze w kategorii "szkoły ponadgimnazjalne"?

Pytanie do organizatorów

To pytanie należałoby skierować bezpośrednio do organizatorów, ale zapewne odpowiedź brzmi tak. Wszak uczniem szkoły abiturient pozostaje do końca roku szkolnego, czyli formalnie do końca września (wtedy traci ważność jego legitymacja szkolna).

Powrót na górę strony