Category: teaching

1. Dana jest tablica kwadratowa A rozmiaru n x n wypełniona liczbami całkowitymi. Napisz funkcje sum_iter(A) i sum_rec(A) zwracające tablicę B, która na pozycji (i, j) ma sumę wszystkich pozycji (k, l) z tablicy A, dla których 0 ≤ k ≤ i i 0 ≤ l ≤ j.
2. Niech S(f, n) oznacza sumę wartości funkcji f dla wszystkich liczb naturalnych od 0 do n. Funkcja g zdefiniowana jest tak:
   • g(0) = 1
   • g(n) = S(g, n-1) + 6, dla n > 0.

   Funkcja h natomiast zdefiniowana jest tak:

   • h(0) = 2
   • h(n) = S(h, n-1) – S(g, n-1) + 6, dla n > 0.

   Napisz rekurencyjne i iteracyjne wersje funkcji g i h. Która z nich działa szybciej? Spróbuj policzyć h(25) dla każdej z nich.

3. Napis s został zakodowany w taki sposób, że wszystkie jego spółgłoski i samogłoski zostały ułożone w odwrotnej kolejności, tzn. pierwsza samogłoska została zamieniona kolejnością z ostatnią, następnie druga z przedostatnią, itd. Analogicznie postępowano ze spółgłoskami. Napisz procedurę decode(s), która zdekoduje napis s zakodowany opisanym szyfrem.

Prezentacje:
http://www.mimuw.edu.pl/~gorecki/wdi/Wdi1u.pdf
http://www.mimuw.edu.pl/~gorecki/wdi/Wdi2u.pdf
http://www.mimuw.edu.pl/~gorecki/wdi/Wdi3u.pdf
http://www.mimuw.edu.pl/~gorecki/wdi/Wdi4u.pdf

Zadania:

1. W pliku avgs.txt dana jest lista miejscowości wraz ze średnią temperaturą w grudniu. Posortuj ją używając potoków w kolejności rosnącej średniej temperatury.
2. Wypisz nazwę i rozmiar 5 największych plików z katalogu domowego.
3. Przeszukaj swój katalog domowy rekurencyjnie i znajdź wszystkie wystąpienia plików o tej samej nazwie (mogą się różnić co najwyżej wielkością liter). Na wyjściu chcemy dostać takie nazwy poprzedzone liczbą wystąpień.
4. Policz liczbę takich nieunikalnych nazw plików z poprzedniego zadania.
5. Wypisz do pliku bests.txt początek, koniec i score z pliku dmel.gff posortowane po score do pliku best_scores.txt.
6. Wypisz wartości score z wygenerowanego pliku best_scores.txt na pozycjach od 1000 do 2000.

Nie łatwo być Mikołajem. Każdego roku trzeba przeczytać miliony listów i wywnioskować z nich, o jakich prezentach marzą dzieci. Później życzenia przekazuje się elfom, które skrzętnie wyszukują w magazynach odpowiednie przedmioty i pakują je do paczek. Następnie zamiast w Wigilię spokojnie zajadać się barszczem wsiada się na sanie i gimnastykuje w kominach, żeby każda paczka trafiła do odpowiedniego adresata. Ponieważ jednak mamy XXI wiek, możemy wspomóc Mikołaja w jego corocznych wysiłkach. W tym celu napiszemy pakiet mikolaj_2_0, który usprawni system roznoszenia prezentów w przyszłym roku.

Pakiet będzie składał się z trzech modułów: listy, magazyn i dostawa.

Zadaniem modułu listy będzie obsługa przychodzącej korespondencji i przekazywanie do magazynu życzeń w postaci list opatrzonych adresami dzieci. Zakładamy, że listy, które przychodzą są już przepisane komputerowo i w postaci plików zapisane na twardym dysku. Przykładowe pliki z listami to list1.txt i list2.txt. W module listy powinny się znaleźć dwie funkcje.
Pierwsza o nazwie adres(plik) zwróci napis reprezentujący adres dziecka dla listu zapisanego w pliku. Adres to ciąg znaków następujący po napisie Adres: (na końcu jest spacja), aż do ostatniej napotkanej kropki w linijce adresu (kropka nie jest częścią adresu).
Druga funkcja, prezenty(plik), znajduje w pliku wszystkie wystąpienia nazw prezentów wraz z poprzedzającą ją liczbą sztuk. Zakładamy, że nazwą prezentu jest każde słowo następujące po wystąpieniu liczby w tekście listu. Zakładamy, że interesują nas tylko prezenty występujące w tekście po adresie. Nie przejmujemy się odmianą wyrazów – można bezpiecznie założyć, że kolejka i kolejki to dwa różne prezenty. Jako wynik funkcja prezenty zwraca słownik, którego kluczami są nazwy prezentów, a wartościami jest łączna liczba sztuk prezentu wymieniona w liście. W jednym liście dany prezent może występować kilka razy (wtedy interesuje nas suma ilości sztuk tego prezentu). Można założyć, że w każdym liście jest mowa przynajmniej o jednym prezencie.
Dla przykładu:

adres(“list1.txt”) == “ul. Basniowa 5/10, 25-231 Otwock”

prezenty(“list1.txt”) == {“samochodziki”: 2, “klocki”: 1}

W module magazyn dostępne będą dwie funkcje.

Pierwsza z nich – uzupelnij(plik) wczytuje dane z pliku i zwraca słownik, którego kluczami są nazwy produktów, a wartościami – ich ilości, z pliku w formacie:
produkt1 ilość1
produkt2 ilość2
…
Przykładowy plik w tym formacie to magazyn.txt.

Druga natomiast (rozdziel(magazyn, zyczenia)) służy do podejmowania decyzji, jakie prezenty dzieci dostaną w tym roku. Wynikiem funkcji jest słownik, gdzie kluczami jest adres dziecka, a wartością para: (nazwa prezentu, ilość). Prezenty przydzielane są według następujących zasad. Każde dziecko dostaje ze swojej listy tylko jeden prezent (przy czym zawsze w ilości, którą sobie zażyczyło). Spośród dzieci, którym prezent nie został jeszcze przydzielony, realizowane jest największe pod względem ilości zamówienie, dla którego w magazynie jest odpowiednia liczba przedmiotów. W przypadku kilkorga dzieci z tym samym, maksymalnym możliwym do realizacji życzeniem, pierwsze w kolejności dostaje prezent dziecko, którego adres jest mniejszy leksykograficznie. W przypadku remisów w ramach życzeń jednego dziecka, dziecko dostaje prezent, którego nazwa jest mniejsza leksykograficznie. Procedura powtarzana jest do momentu, kiedy żadne życzenie nie może już być zrealizowane. Wszystkie dzieci, którym w wyniku tej procedury nie przydzielono jeszcze prezentu dostają w wynikowym słowniku rózgę (a dokładniej parę (“rozga”, 1)). magazyn jest słownikiem postaci takiej, jak zwracana z funkcji uzupelnij. zyczenia natomiast to słownik, w którym kluczami są adresy dzieci, a wartościami słowniki w formacie jak zwracany przez funkcję prezenty.

Dla przykładu:

uzupelnij(“magazyn.txt”) == {“klocki”: 5, “samochodziki”: 3, “rowery”: 2}

rozdziel({“klocki”: 5, “samochodziki”: 2, “wrotki”: 4}, {“ul. Krucza 2/3, Krakow”: {“klocki”: 4, “wrotki”: 4}, “ul. Wolominska 17/27, Warszawa”: {“klocki”: 4, “samochodziki”: 5}, “ul. Gdynska 5/2, Gdansk”: {“wrotki”: 3, “klocki”: 1}, “ul. Czysta 24/7, Czestochowa”: {“samochodziki”: 2, “rowery”: 6}}) == {“ul. Krucza 2/3, Krakow”: (“klocki”, 4), “ul. Wolominska 17/27, Warszawa”: (“rozga”, 1), “ul. Gdynska 5/2, Gdansk”: (“wrotki”: 3), “ul. Czysta 24/7, Czestochowa”: (“samochodziki”: 2)}

W module dostawa należy zaimplementować dwie funkcje.

Pierwsza – zapotrzebowanie(magazyn, zyczenia) – pomoże Mikołajowi odpowiednio uzupełnić magazyn przed przyszłymi świętami. Parametry przekazywane są w tym samym formacie, co w przypadku funkcji rozdziel. Wynikiem jest słownik zawierający jako klucze nazwy prezentów występujące w zyczeniach, a jako wartości liczbę sztuk prezentu, której zabrakło, aby móc obdarować wszystkie dzieci prezentem o tej nazwie w ilości przez nie zgłaszanej w listach (tzn. jeśli troje dzieci życzyło sobie dostać po 3 paczki klocków, a w magazynie było ich tylko 5, to w wynikowym słowniku powinna się znaleźć liczba 4). Jeśli danego prezentu jest w magazynie odpowiednia ilość, nie należy zawierać jego nazwy w wynikowym słowniku.

Ostatnią funkcją jest funkcja kiedy_prezent(adres, prezenty), która będzie zupełnie nową usługą zaproponowaną dzieciom przez Mikołaja. Dzięki niej każde dziecko, podając swój adres, będzie mogło się dowiedzieć, jako które w kolejności dostanie swój prezent. Mikołaj roznosi prezenty w kolejności alfabetycznej, tzn. rózga zawsze będzie dostarczona później niż klocki. Na swoje sanie Mikołaj zabiera tylko prezenty jednego typu i wędruje od adresu do adresu w kolejności alfabetycznej, po czym wraca do Laponii po kolejny typ prezentu. adres to napis – adres dziecka, a prezenty to słownik w formacie takim, jak wynik funkcji rozdziel. Opisana wcześniej procedura wyznacza jednoznacznie kolejność, w jakiej Mikołaj będzie odwiedzał kolejne dzieci. W szczególności w którymś momencie odwiedzi dziecko o podanym adresie. Jako wynik funkcja kiedy_prezent powinna zwracać właśnie numer przypadający temu dziecku na trasie Mikołaja. Zakładamy, że adres występuje jako klucz słownika prezenty. Przyjmujemy pythonową numerację kolejności – pierwsze dziecko ma numer 0.

Dla przykładu:
zapotrzebowanie({“klocki”: 5, “samochodziki”: 2, “wrotki”: 4}, {“ul. Krucza 2/3, Krakow”: {“klocki”: 4, “wrotki”: 4}, “ul. Wolominska 17/27, Warszawa”: {“klocki”: 4, “samochodziki”: 5}, “ul. Gdynska 5/2, Gdansk”: {“wrotki”: 3, “klocki”: 1}, “ul. Czysta 24/7, Czestochowa”: {“samochodziki”: 2, “rowery”: 6}}) == {“klocki”: 4, “wrotki”: 3, “samochodziki”: 5, “rowery”: 6}.
kiedy_prezent(“ul. Wolominska 17/27, Warszawa”, {“ul. Wolominska 17/27, Warszawa”: (“wrotki”, 3), “ul. Krucza 2/3, Krakow”: (“wrotki”, 4) , “ul. Czysta 24/7, Czestochowa”: (“wrotki”, 2), “ul. Gdynska 5/2, Gdansk”: (“klocki”, 1)}) == 3

Punktacja za poszczególne funkcje:

• adres – 2pkt
• prezenty – 3pkt
• uzupelnij – 2pkt
• rozdziel – 6pkt
• zapotrzebowanie – 2pkt
• kiedy_prezent – 5pkt

Należy trzymać się wytycznych dotyczących struktury modułów w pakiecie. Za rozbieżności w stosunku do treści zadania, mogą być odjęte punkty. Zadania w postaci pakietu (sam kod źródłowy rozmieszczony w odpowiednich katalogach) spakowanego w formacie zip lub tgz należy przesłać do wykładowcy (bartek@mimuw.edu.pl) oraz prowadzącego odpowiednią grupę ćwiczeniową (pawel.bednarz@mimuw.edu.pl lub mist@mimuw.edu.pl lub pwl@mimuw.edu.pl). Termin przesyłania zadania: 27.01.2014, godzina 12:00. W tytule e-maila należy umieścić dopisek [WDI-2]. Ocenianie, jak poprzednio osobiście z prowadzącymi ćwiczenia. Zadania należy rozwiązywać samodzielnie. Powodzenia!

PS. Zbiór dodatkowych testów dostępny tutaj. Instrukcja obsługi: rozpakowujemy dane testowe do jakiegoś katalogu. Następnie w tym katalogu umieszczamy swój pakiet mikolaj_2_0 i robimy: python test.py. Jeśli wszystkie funkcje działają jak należy, program nie powinien zwrócić żadnego wyjścia.

1. Napisz funkcję zip_code(s), która sprawdzi, czy napis s jest poprawnym polskim kodem pocztowym.
2. Napisz funkcję remove_numbers(s), która usunie z napisu s wszystkie cyfry.
3. Napisz funkcję sum_all(s), która dla zadanego napisu s zsumuje wszystkie liczby całkowite występujące w napisie s.
4. Napisz funkcję trim_all(s), która zamieni wszystkie ciągi białych znaków w napisie s na pojedynczą spację, czyli np.

   trim_all("Ala     ma kota   .")=="Ala ma kota ."

5. Załóżmy, że mamy napisać fragment strony internetowej w języku przypominającym html. Do dyspozycji mamy trzy rodzaje znaczników: em, b i br. Znaczniki em i b otaczają fragment tekstu powodując zmianę wyglądu jego czcionki. Z tego powodu występują dwie odmiany tych znaczników: odmiana otwierająca (<em>, <b>) i zamykająca (</em>, </b>). Znacznik br natomiast występuje tylko w jednej wersji (<br/>) powodującej złamanie wiersza w miejscu jego wystąpienia. Dodatkowo chcemy, aby były to jedyne znaczniki występujące w tekście (nie chcemy innych wystąpień znaków < i > w tekście) oraz nie chcemy, aby wewnątrz znaczników em i b znajdowały się inne znaczniki oraz chcemy, aby znaczniki były poprawnie domknięte. Napisz funkcję test_markups(s), która sprawdzi, czy napisany przez nas tekst s spełnia te wymogi.
6. Napisz funkcję pretty_printer(s), która znajdzie wszystkie wystąpienia liczb całkowitych w tekście s i wypisze je w oddzielnych liniach w formacie:

   start end number number_pow
   

   gdzie start i end to początkowa i końcowa pozycja liczby number w tekście s, a number_pow to liczba 2 podniesiona do potęgi number.

7. Napisz za pomocą pojedynczego wyrażenia regularnego funkcję, która dla pliku dmel stworzy nowy plik, składający się ze wszystkich wpisów o funkcji OrthoDB i roli orthologous_to, które zawierają dwa wystąpienia tego samego znaku (+ lub -). Dodatkowo chcemy, aby w nowym pliku kolumny zawierające początkową i końcową pozycję wpisu były ze sobą zamienione miejscami.

Wyrażenia regularne:
Howto

Nieznacznie zmienione w stosunku do wersji zeszłorocznych Wykłady szósty (o zmiennych) i siódmy o modułach.

Dodatkowo moduł wdi (do wykładu 7.)

Skrypt  simple z użyciem sys.argv

i Skrypt z użyciem modułu Argparse

Dzisiejszym zadaniem jest stworzenie pakietu testującego szybkość napisanych przez nas funkcji sortujących. Do zadań pakietu należeć będzie wczytywanie list – instancji problemów zapisanych w kilku różnych formatach, a następnie opracowanie porównania szybkości działania różnych funkcji sortujących na wczytanych listach. Dodatkowo chcemy mieć funkcję generate_list(file_name, swaps_no, length), która zapisze do pliku o ścieżce file_name listę liczb naturalnych od 1 do length wg algorytmu o następującym pseudokodzie:

    a ← range(length)
    for i from swaps_no to 1
    do
        di ← random element of { 0, ..., (length - swaps_no + i - 2) }
        swap a[di] and a[length - swaps_no + i - 1]
    return a

Szczegóły implementacji:
Pakiet ma się składać z trzech modułów. Pierwszy z nich będzie zawierał funkcje sortujące (ważne, żeby były to funkcje o takim samym interfejsie, czyli przyjmujące jako jedyny parametr listę, a zwracające listę posortowaną). Drugi moduł będzie zawierał funkcje wczytujące listy z plików w następujących formatach:
li1:
[4, 3, 1, 2, 4, 5]
li2:
4
3
1
2
4
5
li3:
4 3 1 2 4 5
W drugim module powinny się znaleźć trzy funkcje, które przyjmują jako parametr nazwę pliku, a zwracają wczytaną z tego pliku listę.

Trzeci moduł ma przeszukiwać bieżący katalog w poszukiwaniu instancji problemów (plików o rozszerzeniach li1, li2 lub li3) i dla każdego z takich plików ma wywoływać wszystkie dostępne w pierwszym module funkcje testujące wraz z informacją na temat czasu działania każdego z nich na poszczególnych instancjach problemu. Dodatkowo ma zawierać funkcję generate_list.

Trzeci moduł powinien dawać się wywoływać z linii poleceń za pomocą polecenia: python compare_sorts.py [opcje]. Powinien udostępniać przynajmniej opcje:
-h – pomoc na temat sposobu wywołania skryptu
-g len – generowanie zestawu 9 plików testowych, zawierających listy o długości len, po trzy w każdym formacie. Dla każdego formatu pliki powinny zostać wygenerowane funkcją generate_list z parametrami swaps_no równymi odpowiednio 10, (len / 3) i len – 1.

1. Przepisz poniższy program tak, aby uniknąć użycia zmiennych globalnych (zachowaj sposób wyliczania wyniku w funkcji f).

   a = 2
   b = 5
   c = 0
   def f():
       global c
       for i in range(b):
           c += i ** a
   f()
   print c
   

2. Napisz funkcję knight(a), która dla zadanej pozycji a(dwuelementowa krotka) na szachownicy zwróci listę pozycji odległych o jeden ruch skoczka szachowego. Zakładamy, że szachownica jest kwadratową tablicą o wymiarach 8×8, indeksowaną dwuelementowymi krotkami (a, b), gdzie a i b są z przedziału [0,7].
3. Napisz funkcję perfect(n), która dla zadanej liczby naturalnej n sprawdzi, czy liczba ta jest liczbą doskonałą.
4. Napisz funkcję all_perfects(n), która znajdzie wszystkie liczby doskonałe mniejsze lub równe od n w następujący sposób. Najpierw konstruujemy słownik, w którym pod kluczami, będącymi liczbami całkowitymi, znajdzie się lista liczb, których suma dzielników (różnych od tej liczby) jest równa kluczowi. Następnie funkcja all_perfects w pętli znajdzie w tym słowniku liczby doskonałe.
5. W pewnym banku kody do systemu składają się z ciągów cyfr długości 10. Podczas każdego logowania zostajemy poproszeni o podanie pewnych 3 cyfr naszego hasła. Okazało się, że na komputerze, z którego zwykle logujemy się do systemu naszego banku ktoś zainstalował oprogramowanie zbierające dane na temat historii naszych logowań. Zakładamy przy tym, że są w nim odnotowywane jedynie poprawne próby logowania. Dane są zbierane w formie słownika pythonowego. Kluczami są trzyelementowe krotki oznaczające indeksy cyfr hasła, o które zostaliśmy poproszeni, np. klucz (0, 3, 7) oznacza, że w pewnej próbie logowania system poprosił nas o zerową, trzecią i siódmą cyfrę z hasła. Wartościami w słowniku będą natomiast cyfry hasła występujące na pozycjach z klucza. Napisz funkcję attempts(d), która dla zadanego słownika – historii logowań zwróci liczbę prób potrzebną do złamania naszego hasła (chodzi tutaj o przypadek pesymistyczny, w którym dla każdej nieznanej cyfry z hasła włamujący “trafia” dopiero podczas ostatniej próby). Przykład:

   attempts({(0,1,2):(7,3,5), (3,4,5):(7,2,0), (6,7,8):(9,4,1)})==10
   attempts({(0,1,2):(7,3,5), (3,4,5):(7,2,0), (6,7,8):(9,4,1), (0,8,9):(7,1,1)})==1
   

6. Napisz funkcję BST(l), która dla zadanej listy liczb całkowitych l zwróci drzewo binarnych poszukiwań powstałe poprzez dodawanie do drzewa liczb w kolejności ich występowania na liście l. Każdy węzeł drzewa ma być trzyelementową krotką, a brakujące puste poddrzewo reprezentowane jest przez obiekt None. Przykład:

   BST([4,1,6,2,5,6,8])=((None, 1, (None, 2, None)), 4, ((None, 5, None), 6, (None, 8, None)))
   

Słowniki:

1. Stwórz pusty słownik. Zapoznaj się z funkcjami, jakie są dla niego dostępne. Dodaj do niego następujące elementy: pod kluczem 1 wartość 3, 5->2, “a”->4. Usuń jeden z elementów używając metody del, a drugi używając metody pop. Przypisz na pozostały element wartość 10.
2. Sprawdź, jak działają metody iterkeys, itervalues, iteritems. Której z nich odpowiada zwykła iteracja pętlą for?
3. Stwórz słownik dla tekstu z zadania 4 (lab4), w którym kluczem będzie numer słowa w tekście, a wartością to słowo. Użyj funkcji enumerate.
4. Stwórz funkcję zwracającą dla zadanego napisu słownik, który pod indeksem odpowiadającym danemu słowu zawiera jego długość.
5. Rozwiąż poprzednie zadanie używając funkcji map i zip.
6. Używając klasy defaultdict (moduł collections) stwórz funkcję zwracającą dla danego słowa słownik, który pod indeksem odpowiadającym danej literze będzie zawierał liczbę jej wystąpień.
7. Używając klasy defaultdict stwórz dla zadanego napisu słownik, zawierający dla słów z napisu ilość ich wystąpień.
8. Rozwiąż zadanie 2 z labu 4 korzystając ze słowników.

Zbiory:

1. Stwórz zbiór liter z napisów “alabama” i “alaska”. Jak wygląda różnica pomiędzy jednym zbiorem a drugim (użyj operatora “-“)?
2. Zobacz jakie inne funkcje na zbiorach są dostępne w pythonie.
3. Stwórz zbiór słów z pliku the_emperors_new_clothes.txt (usuń najpierw znaki interpunkcyjne zastępując je spacjami).
4. Stwórz również zbiór słów z pliku the_bell.txt i wypisz słowa występujące w pierwszym, ale nie występujące w drugim.
5. Znajdź słowa, które występują dokładnie w jednym z powyższych plików oraz słowa wspólne dla obu plików.
6. Dla danego zbioru wygeneruj jego zbiór potęgowy (zbiór wszystkich podzbiorów tego zbioru).

Slajdy z ostatniego wykładu są tutaj.