Teaching

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.

1. Napisz rekurencyjną funkcję triangle(n), generującą dla zadanego n wzory postaci:

   ****
   ***
   **
   *
   

   o n liniach.

2. Weźmy funkcję f zdefiniowaną następująco:

   def f(n):
       if n % 2 == 0:
           return n / 2
       else:
           return 3*n + 1
   

   Napisz rekurencyjną funkcję collatz_steps(n), która zwróci dla zadanego n liczbę elementów ciągu n, f(n), f(f(n)), …, potrzebnych do osiągnięcia 1. Np.

   collatz_steps(1) == 0
   collatz_steps(4) == 2
   

3. Napisz rekurencyjną funkcję binary(n), która dla zadanej liczby n znajdzie jej zapis binarny.
   Wskazówka: ostatnią cyfrą w tym zapisie będzie n % 2.
4. Napisz rekurencyjną funkcję newton(n, k), która dla zadanych liczb n i k wylicza współczynnik dwumianowy (“n po k”, wzór rekurencyjny na stronie http://pl.wikipedia.org/wiki/Symbol_Newtona).
5. Załóżmy, że mamy daną funkcję rosnącą w przedziale <0;n>. Napisz rekurencyjną funkcję bisection(f), która znajdzie przybliżenie miejsca zerowego funkcji f.

   Wskazówka 1: funkcję f można zdefiniować np. tak:

   def f(x):
   	import math
   	return math.tan(x - math.pi)
   

   i dalej wywołać funkcję bisect na funkcji f: bisect(f)
   
   Wskazówka 2: zastosuj metodę “połowienia” przedziału <0;n> – podobnie jak to miało miejsce w przypadku wyszukiwania binarnego.

6. Napisz rekurencyjną funkcję rec_count(v, x), która dla listy v i liczby x zwróci liczbę wystąpień liczby x w liście v.
7. Napisz rekurencyjną funkcję find_sum(v, x), która sprawdzi, czy na liście v występują dwie kolejne liczby o sumie x.
8. Napisz rekurencyjną funkcję check_sort(v), która sprawdzi, czy lista v jest posortowana.
9. Napisz rekurencyjną funkcję rev_number(n), która dla danej liczby całkowitej n zwróci liczbę powstałą z n poprzez odwócenie porządku cyfr (np. rev_number(123)=321). Uwaga: chodzi o rozwiązanie używające wyłącznie operacji na liczbach całkowitych.
10. Napisz rekurencyjną funkcję strange_sum(n), która zwróci sumę kwadratów liczb parzystych mniejszych lub równych niż n i sześcianów liczb nieparzystych mniejszych lub równych niż n (np. strange_sum(3) = 1 + 4 + 27 = 32.

Jako, że sezon biegowy w pełni, w naszym pierwszym zadaniu zaliczeniowym postaramy się stworzyć system pomagający uporządkować jesienny trening grupie biegaczy. W pliku kilometraz.txt znajduje się zapis historii treningowej tej grupy, a poszczególne linie-wpisy mają postać:
runners_ID club distance time
runners_ID to liczba naturalna identyfikująca biegacza, club to nazwa klubu, do którego biegacz przynależy (nie zawiera spacji), distance jest liczbą rzeczywistą – liczbą kilometrów przebiegniętych przez biegacza, a time to liczba naturalna oznaczająca, ile sekund zajęło biegaczowi przebiegnięcie tego dystansu.
We wszystkich funkcjach w tym zadaniu zaliczeniowym, pierwszy parametr db_f będzie oznaczał plik z bazą danych treningowych w powyższym formacie.

Pierwszą częścią zadania będzie umożliwienie zawodnikom śledzenia swoich postępów. W związku z tym będziemy potrzebowali następujących funkcji:

1. (1.5p.)distance(db_f, id), która zwróci całkowitą liczbę kilometrów, które zawodnik o identyfikatorze id odnotował w naszej bazie danych
2. (1.5p.)best_velocity(db_f, id), zwracająca najlepszą prędkość spośród średnich osiąganych na poszczególnych treningach odnotowanych przez biegacza o identyfikatorze id (w km/h).

Jak wiadomo, trenerom łatwiej pracuje się, jeśli trenowana grupa jest w miarę możliwości jednorodna pod względem poziomu przygotowania. W związku z tym potrzebujemy funkcji, która pozwoli trenerom wybrać w swoim klubie grupę osób gotowych na planowany rodzaj treningu (3p.): funkcja group(db_f, club, min_distance, max_distance, min_average_velocity) powinna zwracać listę identyfikatorów zawodników klubu club, którzy w każdym treningowym biegu na dystansie pomiędzy min_distance i max_distance osiągali średnią prędkość co najmniej min_average_velocity (w km/h) (przyjmujemy, że jeżeli ktoś dotąd nie biegał na dystansach pomiędzy min_distance i max_distance, nie powinien być zaliczony do tej grupy).

Często po serii żmudnych treningów nadchodzi czas sprawdzenia swoich możliwości na zawodach. Aby ułatwić zadanie organizatorom zawodów, przygotujemy na podstawie naszej bazy danych prognozę popularności poszczególnych dystansów wśród biegaczy w bazie danych (4p.). Funkcja competitions(db_f, distances) przyjmuje jako parametr posortowaną rosnąco listę liczb całkowitych distances, zawierającą dystanse biegów, które odbędą się w ramach zawodów. Jako wynik, funkcja zwróci liczbę uczestników zainteresowanych poszczególnymi biegami. Przyjmiemy, że każdy biegacz jest zainteresowany tylko jednym dystansem, gdyż nie może jednocześnie biec w kilku biegach. Każdy przebiegnięty przez niego trening jest najbliższy któremuś z dystansów oferowanych przez organizatora zawodów. W przypadku treningów o długości równie bliskiej dwóm z oferowanych dystansów przyjmujemy, że taki trening bliższy jest dłuższemu dystansowi. Ulubiony dystans zawodnika będzie dystansem, który jest najbliższy największej ilości jego treningów (w przypadku remisów znowu preferujemy dłuższy z dystansów).

W najbliższym czasie pojawi się plik z przykładową bazą danych oraz wynikami przykładowych wywołań funkcji na tej bazie danych. Zadania w postaci kodu źródłowego (w jednym pliku zadanie1_nr-indeksu.py) przesyłają Państwo do wykładowcy i prowadzącego ćwiczenia (bartek@mimuw.edu.pl i (pawel.bednarz@mimuw.edu.pl lub mist@mimuw.edu.pl lub pwl@mimuw.edu.pl)) przed wykładem za trzy tygodnie (18 XI 2012, 12:15). Proszę o umieszczenie w tytule e-mail’a hasła [WDI-1].

Kolokwium 1
Poprawkowe kolokwium 1
Kolokwium 2
Poprawkowe kolokwium 2
Egzamin

1. W pliku HP1b.gff3 znajdują się dane o miejscach wiązania białka HP1b do nici DNA muszki owocowej. Znajdź średnią wartość sygnału dla chromosomu 2L na pozycjach od 1,000,000-5,000,000.
2. W pliku DNA.txt znajduje się fragment nici DNA człowieka. Znajdź listę wszystkich wystąpień sekwencji ACGT.
3. Używając maksymalnie trzech wywołań funkcji strip, rstrip, lstrip przejdź od:
   • abcccbca do ccc
   • bababa do ab
4. Zastąp spacje przez myślniki w napisie “Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nunc sit amet ligula in nisi varius mattis nec a urna. Phasellus tristique vehicula elit id imperdiet. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Nunc orci libero, accumsan quis cursus vel, pretium nec dui. Nunc lobortis mollis felis, at malesuada velit volutpat id. Pellentesque quis iaculis massa. Vestibulum commodo egestas fringilla. Proin quis justo nunc. Nam sed ultricies orci. Curabitur adipiscing, dolor vel rhoncus accumsan, sapien tellus volutpat eros, at luctus mi augue sit amet turpis. Aliquam sagittis, lacus id commodo volutpat, erat justo auctor massa, in faucibus quam lectus et libero. Curabitur laoreet risus in urna aliquet vel fringilla felis volutpat. Morbi suscipit purus velit.” używając
   • funkcji replace
   • funkcji split i join
5. (*)K-merami nazywamy sekwencje DNA długości k. Dla pliku DNA.txt wypisz najczęściej występujący 4-mer.
   Wskazówki:
   • stwórz funkcję, która dla danego k-meru znajdzie następny w stosunku do niego k-mer (w porządku leksykograficznym)
   • iterując po kolejnych 4-merach (począwszy od “AAAA”) znajdź liczbę ich wystąpień (używając funkcji z zadania 2); zapamiętaj najwyższy wynik i odpowiadający mu 4-mer

Slajdy z wykładu o plikach są tutaj.

1. Używając funkcji randint modułu random wygenerować 10 losowych list długości 10000, posortować je i wypisać.
2. Napisać funkcję merge z wykładu w wersji iteracyjnej.
3. Co robi funkcja f?

   			def f(a, b):
   				if b == 0:
   					return 0
   				return a + f(a, b - 1)
   			

4. Co się stanie jeśli w powyższym przykładzie zmienimi znak + na *?
5. Co zwracają funkcje e i o zdefiniowane poniżej?

   			def e(n):
   				if n == 0:
   				        return True
   			        else:
   				        return o(n - 1)
   
   			def o(n):
   				if n == 0:
   				        return False
   				else:
   				        return e(n - 1)
   			

6. Napisz rekurencyjną funkcję rec_find(v, x), która zadanej posortowanej listy v zwróci wartość True, gdy element x występuje na liście v. W przeciwnym przypadku funkcja zwraca wartość False.
7. Napisz rekurencyjną funkcję rec_pal(s) zwracającą True, gdy s jest palindromem. W przeciwnym przypadku funkcja zwraca wartość False.
8. Napisz rekurencyjną funkcję rec_rev(s), która dla zadanego napisu s zwróci odwrócony napis s.
9. Co zwracają funkcje take i skip zdefiniowane poniżej?

   			def take(l):
   				if l == []:
   					return []
   				else:
   					return [l[0]] + skip(l[1:])
   			def skip(l):
   				if l == []:
   					return []
   				else:
   					return take(l[1:])
   			

10. (*) Podziałem liczby naturalnej n nazwiemy ciąg liczb naturalnych sumujących się do n. Napisz rekurencyjną funkcję partition(n), która znajdzie wszystkie podziały liczby n.