Na tej stronie znajdą Państwo informacje dotyczące ćwiczeń z przedmiotu Wstęp do Informatyki, adresowane do powierzonej mi grupy.
Tradycją jest, aby z ćwiczeniami zaczekać, aż odbędzie się pierwszy wykład. Tradycję tę należy uszanować, zatem pierwsze ćwiczenia odbędą się dopiero w drugim tygodniu semestru. Teoretycznie zajęcia te należałoby kiedyś odrobić, podejrzewam jednak, że pierwsze listy zadań będą na tyle proste i krótkie, iż uda nam się przerobić cały materiał w ciągu N-1 zajęć. Nie chciałbym tego jednak robić kosztem jakości, toteż, gdy zajdzie wyrażona przez Państwa potrzeba zwolnienia tempa, ustalimy termin zastępczego spotkania.
Pierwsze zajęcia poprowadzi w moim zastępstwie Łukasz Jeż, którego upoważniam w szczególności do sprawdzenia obecności, zebrania wypełnionych deklaracji (które można zakupić/odbić w punkcie ksero) i ocenienia prezentowanych rozwiązań. Z ustaleniem sposobu zaliczania ćwiczeń, wyliczania końcowej oceny itd, proponuję się jednak wstrzymać do czasu mojego powrotu.
Proszę nie deklarować, że potrafią Państwo zrobić zadanie jeśli nie potrafią rozwiązać jednego z podpunktów, lub nie rozumieją w pełni treści zadania. Czasem w treści jest błąd i to dlatego nie da się jej zrozumieć, ale w takich sytuacjach proszę kierować się zdrowym rozsądkiem. Nie przydzielam częściowych punktów za częściowe rozwiązania, gdyż w matematyce i informatyce, trudność leży z reguły w ostatniej linijce dowodu, bądź w jednym z podpunktów właśnie.
Z praktycznego punktu widzenia, wole mieć Państwa deklaracje na jednej kartce, dlatego nie ma potrzeby zaopatrywania się w wydrukowane formularzyki - będę puszczał liste obecności. Proszę jednak nauczyć się własnego nazwiska na pamięć, aby wędrowanie listy po sali nie trwało dłużej niż początkowe 5 minut, które mam zamiar przeznaczać na niemerytoryczne dygresje.
Z "grzybami" nie żartowałem. Dzisiejsze nieudane występy oceniłem łagodnie, przyznając 0 punktów tylko za zweryfikowane przy tablicy zadania. Jednak od przyszłych zajęć mam zamiar konsekwentnie oceniać wg następującej reguły: Jeśli X osób zadeklaruje, że potrafi rozwiązać zadanie warte Y punktów, to osoba wezwana do odpowiedzi, która nie będzie potrafiła go rozwiązać wbrew wczesniejszej deklaracji, otrzyma -X*Y punktów. Za niezadeklarowanie zadania otrzymuje się 0 punktów. W pozostałych przypadkach, otrzymuję się Y punktów.
Progi punktowe nie są jeszcze ustalone, bo nie jest jeszcze jasne jak będą wyglądały kolokwia. Będą one jednak zbliżone poziomem trudności do tych sugerowanych na listach zadań (zarówno progi jak i kolokwia).
Ćwiczenia dnia 7 XI 2007 nie odbędą się. Na ćwiczenia dnia 14 XI 2007 proszę przygotować się ze wszystkich list o numerach większych niż 4.
Dnia 21 XI 2007 przewidziane jest kolokwium, a zatem zostały nam już tylko jedne zajęcia, aby przećwiczyć materiał..
Zapraszam na konsultacje, które prowadzę we czwartki od 14 do 16 w pokoju 323.
Musimy poświęcić trochę czasu na powtórzenie sobie co to jest notacja O, bo ponad połowa osób miała mylne intuicje. Przyda się też powtórzyć jak działają kwantyfikatory i implikacja, bo odnoszę wrażenie, że część z Pańtwa używa tych znaczków "fonetycznie", tj. tam gdzie pojawiłyby się w zdaniu języka polskiego, a to nie koniecznie prowadzi do dobrej formuły. Moim zdaniem trzeba koniecznie zrobić jakieś repetytorium i dać Państwu szansę zrozumienia co jest grane, bo o ile WDI większość powinna zaliczyć, to marwię się Logiką i Analizą.
Na wykładzie pojawiły się elementy programowania funkcjonalnego, w szczególności mowa była o jednym z podstawowych typów danych jakim jest lista. Lista może być albo pusta, albo zawierać jakąś informacje w pierwszym jej elemencie, zwanym głową i wskaźnik na dalszą jej część, również będącą listą, zwaną ogonem. W zależności od języka programowania, wymaga się bądź nie, aby wszystkie elementy listy były tego samego typu. Aby móc specyfikować typy funkcji oraz mieć pewność, że wykonywane przez program operacje mają sens, wygodniej jest zajmować się jezykami, w których wszystkie twory mają konkretne typy. Zdefiniowane na wykładzie funkcje zd oraz lista, jakkolwiek użyteczne, wprowadzają dużo bałaganu w świecie typów. Dlatego na ćwiczeniach wprowadziliśmy sobie bardziej popularne w językach funkcjonalnych takich jak Nemerle, sml, ocaml, czy haskel pojęcia.
Pierwszym pojęciem jest konstruktor listy, który jako argumenty przyjmuje element x oraz listę L, a zwraca listę, której ogonem jest L, mającą w głowie x. Konstruktor listy reprezuntejmy jako czterokropek ::, który podobnie jak znane Państwu działania matematyczne jest operatorem infiksowym, czyli piszemy go pomiędzy głową a ogonem, które chcemy połączyć. Zachodzi, więc:
x::[x1,x2,...,xn]=[x,x1,x2,...,xn] 1::[]=[1] 1::[2,3]=[1,2,3] [1]::[[2],[3]]=[[1],[2],[3]]
Drugim popularnym pojęciem jest operator konkatenacji, czyli sklejania dwóch list jedna za drugą. W zależności od języka nazywa się taką funkcję append, concat,lub po prostu @. Ta ostatnia forma jest o tyle wygodna, że jest infiksowym operatorem, co pozwala zaoszczędzić kredę oraz jest bardziej sugestywne dla wyobraźni.
[x1,x2,...,xn]@[y1,y2,...,ym]=[x1,x2,...,xn,y1,y2,...,ym] [1,2]@[]=[1,2] [1,2]@[3]=[1,2,3] [1,2]@[3,4]=[1,2,3,4] []@[]=[] []@[1,2]=[1,2]
Tak zdefiniowane pojęcia dbają o to, aby wszystkie elementy listy posiadały ten sam typ. Ten sam w obrębie jednej listy, bowiem różne listy mogą mieć w sobie elementy innych typów. Aby nie było bałaganu nie chcielibyśmy nigdy ze sobą mieszać takich list ze sobą. W tym celu wymyślono pewien kompromis. Mówimy, że lista ma typ polimorficzny, konkretnie nazywa się on list<T> jeśli zawiera tylko elemnty typu T. Mamy zatem nie jeden typ "lista", ale nieskończenie wiele różnych typów, po jednym dla każdego możliwego typu zawartości. Ten formalizm, pozwala nam podać typ konstruktora listy, czy operacji konkatenacji:
@ : list<T> x list<T> -> list<T> , dla każdego T :: : T x list<T> -> list<T> , dla każdego T
Podobnie jak nie istnieje jeden konkretny typ "lista", nie istnieje też jeden konkretny operator konkatenacji, ale raczej nieskończenie wiele takich operatorów, po jednym dla każdego typu listy. Wszystkie one są reprezentowane przy pomocy tego samego znaczka @. Podobnie używamy jedenego znaczka [] mimo, że istnieje nieskończenie wiele typów list pustych. Właśnie to zjawisko nazywamy polimorfizmem - jeden napis ma nieskończenie wiele znaczeń, wszystkie podobne i zdefiniowane w ten sam sposób.
Zauważmy, że operator @, chociaż w większości języków jest wbudowany, możemy zdefiniować sobie sami. W językach funkcjonalnych programuje się o tyle przyjemnie, że wystarczy się dobrze zastanowić czego oczekujemy od funkcji, napisać sobie post-condition, a potem wprowadzić kosmetyczne poprawki tak, aby dopasować składnie do naszego ulubionego języka.
X@Y = if(X==[]) then Y else pierw(X)::(bp(X)@Y)
Powyższa metoda zaimplementowania z pewnych względów nie jest zbyt efektywna, zainteresowanych odsyłam do googlowania takich pojęć, jak rekurencja ogonowa, odśmiecanie itd. To co chciałbym podkreślić, to to, że ten jednolinijkowy program definiuje nieskończenie wiele operatorów @ po jednym dla każdego typu listy, wszystkie zachowujące się w ten sam sposób. Tak się bowiem składa, że wszystkie elementy układanki są tu polimorficzne : operator porównania ==, stała reprezentująca listę pustą [], operator wyłuskiwania głowy pierw, konstruktor listy ::, operator dekapitacji bp, oraz wywoływany rekurencyjnie @.
Typy, polimorfizm itd. zgłębiać będą Państwo na przedmiocie Programowanie. Jeśli to kogo teraz przeraża, to niech chociaż zrozumie z tego tyle, że miłą cechą jest gdy napotykając w programie X, wiemy czy wolno nam go pomnożyć przez 7, albo pozbawić głowy. Bo jeśli tego nie wiemy za wczasu, pisząc program, to przekonamy się o tym dopiero w trakcie wykonywania programu przez naszego klienta i to z reguły w nieprzyjemny sposób.
Dzisiaj na przerwie skłamałem, że algorytm zachłanny, jeśli wypełni cały plecak, to zwróci optymalny wynik. Jest to bzdura -- aby się przekonać, wystarczy do danych wejściowych dodać przedmiot o wadze 1kg i wartości 0pln.
Decyzyjny problem plecakowy, jest NP-trudny. Aby się o tym przekonać, wystarczy rozważać dane wejściowe, w których waga jest proporcjonalna do ceny. Ogólny problem plecakowy, też jest NP-trudny, choć pokazanie tego wymaga nieco finezji i zabawy na bitach. Badany na ćwiczeniach algorytm dynamiczny jest pseudowielomianowy, bo działa w czasie wielomianowym od wielkości plecaka. Jeśli więc na wejściu pojawi się np. W=2^k, które śmiało można zapisać używając k bitów, to czas działania będzie wykładniczo długi względem długości danych wejściowych. Oczywiście można się oszukiwać, że rozmiarem zadania jest W a nie jego długość w bitach, ale to niesportowe zachowanie.
Ciekawą wersją problemu plecakowego była rozwiązywana przez Pana Babija, w której dla każdego typu przedmiotu na wejściu podana jest także liczba dostępnych w magazynie sztuk. Tę wersję można rozwiązać równie szybko co decyzyjną. Inspiracje czerpać można z zadania Banknoty, XII OI
Problem plecakowy jest o tyle ciekawym zagadnieniem, że jest jest to najprostsza forma układu nierówności -- mamy tylko jedną nierówność -- a i tak dostarcza nam nie lada problemów. Głównym źródłem trudności, jest to, że wymagamy by rozwiązania były liczbami naturalnymi (wersja ogólna) czy wręcz 0 lub 1 (decyzyjna). Jeśli przedmioty są płynne i można brać ile się chce, to zadanie sprowadza się do znalezienia przedmiotu o najlepszym stosunku cena/waga. Jeśli są płynne, ale mamy ograniczoną ilość surowca, problem nadal jest trywialny.
Okazuje się, że dla dowolnego ustalonego m, istnieje algorytm pseudowielomianowy, który sprawdza czy istnieje rozwiązanie w liczbach naturalnych m równań. Nie jest to łatwy i przyjemny algorytm, ale jest.
Rozwiązywanie układu dowolnej liczby równań, ale w liczbach całkowitych, da się wykonać w czasie wielomianowym. Jest to potwornie trudne, ale już chyba rozumiem.
Rozwiązywanie układu nierówności w liczbach wymiernych, da się przeprowadzić w czasie wielomianowym (choć nie rozumiem tego algorytmu Karmarkara).
Rozwiązywanie układu równań w liczbach wymiernych, da się przeprowadzić Gaussem w czasie wielomianowym, choć nie jest to takie oczywiste, jeśli się pamięta o dużych liczbach.
Jeśli ktoś się nie boi, to polecam przedmiot Równania i Nierówności Liniowe prowadzony ongiś przez Antoniego Kościelskiego. Mi bardzo poszerzył horyzonty.
Jako, że część z Państwa musi 16.01.2008 pisać kolokwium z Analizy, proponuję przenieść kolokwium o tydzień, to jest na 23.01.2008. Pomysł ów poddam pod dyskusję na najbliższych zajęciach.
Wyniki kolokwium i proponowane oceny są już w necie. Zapraszam we czwartek 31.01.2008 od 14.00 do 16.00 do gabinetu 323. Jako, że wtorek (29.01.2008), też jest czwartkiem, zapraszam także we wtorek w tych samych godzinach w to samo miejsce. Indexy można zostawiać na mojej półeczce w hallu.