Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:asd:2011:pewex [2011/05/30 14:49] esimon |
pl:dydaktyka:asd:2011:pewex [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| ====== Treningi dla pracowników naukowych [15 000 000 pkt] ====== | ====== Treningi dla pracowników naukowych [15 000 000 pkt] ====== | ||
| - | {{ :pl:dydaktyka:asd:2011:park-jordana.png|}}Komitet Główny Uczelnianej Partii Inteligencji Pracującej zlecił badania nad treningiem polepszajacym kodycję fizycną pracowników uczleni wyższych. Na teren treningów, którym każdy pracownik dydaktyczno-naukowy winien od przyszłego tygodnia poświecać się przynajmniej raz dziennie, wybrano Park Jordana. W związku z tym, że ilość pracowników uczleni jest bardzo duża, konieczne jest zaprogramowanie treningu, tak aby tłok na alejkach parkowych był jak najmniejszy, ale jednocześnie, aby trening był optymalny. Każdy Inteligent otrzyma na starcie najnowsze wydanie książki "W prowadzenie do Algorytmów" Cormena i z tą ksiażką (oczywiscie czytając ją podczas biegu, aby nie marnowac cennego czasu) będzie musiał biegać alejkami tak, aby pokonać jak najdłuższy dystans, ale jednocześnie nie przechodzić dwa razy tą samą ścieżka, co utrudniałoby trening innym i zwiekszało ruch na niektóych wąskich alejakch. Napisz program, który rozwiąże ten problem. Dobrze by było żeby trasa treningu przecinała się w minimalnie niewielu punktach, żeby roztargnieni naukowcy nie wpadali na siebie... | + | {{ :pl:dydaktyka:asd:2011:park-jordana.png|}}Komitet Główny Uczelnianej Partii Inteligencji Pracującej zlecił badania nad treningiem polepszającym kondycję fizyczną pracowników uczelni wyższych. Na teren treningów, którym każdy pracownik dydaktyczno-naukowy winien od przyszłego tygodnia poświęcać się przynajmniej raz dziennie, wybrano Park Jordana. W związku z tym, że ilość pracowników uczelni jest bardzo duża, konieczne jest zaprogramowanie treningu, tak aby tłok na alejkach parkowych był jak najmniejszy, ale jednocześnie, aby trening był optymalny. Każdy Inteligent otrzyma na starcie najnowsze wydanie książki "W prowadzenie do Algorytmów" Cormena i z tą książka (oczywiście czytając ją podczas biegu, aby nie marnować cennego czasu) będzie musiał biegać alejkami tak, aby pokonać jak najdłuższy dystans, ale jednocześnie nie przechodzić dwa razy tą samą ścieżka, co utrudniałoby trening innym i zwiększało ruch na niektórych wąskich alejkach. Napisz program, który rozwiąże ten problem. Dobrze by było żeby trasa treningu przecinała się w minimalnie niewielu punktach, żeby roztargnieni naukowcy nie wpadali na siebie... |
| **Uwaga** - Do wyznaczenia odległości w parku można użyć na przykład http://www.openrouteservice.org/, iść na rower i zmierzyć odległości licznikiem rowerowym, ewentualnie wybrać się na rolki/spacer/jogging z dziewczyną/chłopakiem/psem lub w skrajnym przypadku - samemu- i z użyciem GPS-a zmierzyć odpowiednie odległości. | **Uwaga** - Do wyznaczenia odległości w parku można użyć na przykład http://www.openrouteservice.org/, iść na rower i zmierzyć odległości licznikiem rowerowym, ewentualnie wybrać się na rolki/spacer/jogging z dziewczyną/chłopakiem/psem lub w skrajnym przypadku - samemu- i z użyciem GPS-a zmierzyć odpowiednie odległości. | ||
| + | |||
| + | **Uwaga II** - Do rozwiązania zadania wykorzystaj algorytmy grafowe. Wraz z zadaniem dostarcz plik PDF z opisem pracy zawierającym analizę algorytmu: Do jakiego problemu jaki algorytm został wykorzystany. | ||
| ====== Tele-gra [5 000 000] ====== | ====== Tele-gra [5 000 000] ====== | ||
| - | {{:pl:dydaktyka:asd:2011:scrabble.jpg |}}Popularną stała się ostatnio gra telewizyjna w której gracz dostaje kilka-kilkanaście liter, porozrzucanych w losowej kolejności i musi ułożyć z nich wyraz. Napisz program, który umożliwi Partii Inteligencji Pracującej wygrywanie teleturnieju. Program powinien na podstawie podanego zbioru liter wyświetlić wszystkie wyrazy jakie można z niego ułożyć w czasie O(n). Do rozwiązania w postaci programu komputerowego załącz analizę złożoności. | + | {{:pl:dydaktyka:asd:2011:scrabble.jpg?300x276 |}}Popularną stała się ostatnio gra telewizyjna w której gracz dostaje kilka-kilkanaście liter, porozrzucanych w losowej kolejności i musi ułożyć z nich wyraz. Napisz program, który umożliwi Partii Inteligencji Pracującej wygrywanie teleturnieju. Program powinien na podstawie podanego zbioru liter wyświetlić wszystkie wyrazy jakie można z niego ułożyć w czasie O(n). |
| + | |||
| + | ** Uwaga** - Do rozwiązania w postaci programu komputerowego załącz analizę złożoności. | ||
| + | ====== Bustin Jieber [10 000 000] ====== | ||
| + | {{ :pl:dydaktyka:asd:2011:ass-music.jpg|}}Nasz Towarzysz Bustin Jieber planuje trasę koncertowa. Maksymalnie jednego dnia może zagrać 4 koncerty, ale po każdym koncercie musi wrócić do hotelu żeby zadenuncjować fanów którzy nie dość ekspresyjnie wyrażali swoją radość podczas gdy śpiewał o sukcesach Partii Inteligencji Pracującej. Oczywiście aby zminimalizować koszty przejazdu konieczne jest zaplanowanie każdej trasy w następujący sposób: | ||
| + | - dla otrzymanej mapy reprezentującej połączenia pomiędzy miastami wyznaczyć takie zbiory miast między którymi komunikacja będzie optymalna - będzie można dostać się do każdego z nich i jednocześnie wrócić zawsze do hotelu (także umieszczonym w którymś z miast). | ||
| + | - wewnątrz zbiorów określić trasę koncertową i miasto w których Jieber będzie stacjonował | ||
| + | - w obrębie zbiorów miast wyznaczyć trasę pomiędzy nimi tak, aby była optymalna. | ||
| + | **Uwaga** - Do rozwiązania zadania wykorzystaj algorytmy grafowe. Wraz z zadaniem dostarcz plik PDF z opisem pracy zawierającym analizę algorytmu: Do jakiego problemu jaki algorytm został wykorzystany. | ||
