Category: teaching

Lab 8

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.

Wykład 7 – o zmiennych, czyli jak sobie nie zaszkodzic

Dzis zamiat slajdow do wykladu plik z kodem i komentarzami:

 

#WDI Wykład 6

#O zmiennych,
#czyli 100 sposobów strzelenia sobie w stopę

#Bartek Wilczyński

#zmienne lokalne w funkcjach

#Funkcje mogą używać zmiennych lokalnych
y=3
def f():
#tu juz nie widze zmiennej globalnej y
y=5
return y

#mogą też używać zmiennych globalnych
def g():
#tu widze zmienna y
return y

#ale nie mozemy mieszac tych dwoch stylow!

#to bedzie dzialac
def py():
print y

#a to juz nie!
def ppy():
print y
y=1

#Dlaczego? Dlatego, że zmienna y byłaby globalna w 1 linii i lokalna w 2giej

#Czasem chciałbym _zapisać_ coś na zmiennej globalnej
#mogę wtedy użyć deklaracji "global"
#np. tak:

count=0
def add_count():
global count
count+=1
return count

#to oczywiscie bez global nie zadziala...
def add_count():
#global count
count+=1
return count

#A jakie sa argumenty funkcji: globalne, czy lokalne?
y=1
def f(x):
x+=1
return x
print f(y)
y

#jak widac - lokalne,
#tzn nie nie mozemy nadpisac zmiennej globalnej, przekazanej przez parametr

#Ale, czy tak jest zawsze?

def f(x):
x+=x
#jesli uzyje f(liczba), to dobrze
y=1
f(y)
y

#ale dla list dzieje sie cos dziwnego...
l=[1,2]
f(l)
l

#co ciekawe, lekka zmiana funkcji f:
def f(x):
x=x+x

#naprawia dzialanie dla list
l=[1,2]
f(l)
l
# i nie psuje dla liczb:
y=1
f(y)
y

# O co tu chodzi????

#Podobny mechanizm bedzie dzialal dla list i slownikow przy wstawianiu

def f(x):
x[0]=1

#
l=[1]
f(l)
l

d={}
f(d)
d

#Otóż chodzi o to, że python "ulokalnia" zmienne tylko wtedy
#gdy używamy instrukcji przypisania np x=x+x
# a nie wtedy gdy "uzywamy" zmiennej:
#np x[0]=1 czy nawet x+=x

#Ale dlaczego f(x) dzialalo dla liczb? def f(x):
def f(x):
x+=x
print x
#jesli uzyje f(liczba), to dobrze
y=1
f(y)
y

#???

I jeszcze dla napisów też:
s="ala"
f(s)
s
#???????

#Otóż to się wiąże z różnymi rodzajami zmiennych:
# modyfikowalne (mutable) - takie jak listy i słowniki
# niemodyfikowalne (immutable) - takie jak liczby i napisy

#zmienne modyfikowalne będą "pozwalały" zmieniać swoją wartość
#a niemodyfikowalne - nie

#to się wiąże z pojęciem referencji, czyli "odnosnika" do wartosci
#w pythonie (jak w wiekszosci jezykow dynamicznych) miedzy wartosciami (miejsca w pamięci)
#a zmiennymi sa referencje
#zwykle podczas przypisania zmieniamy tylko referencje:

l=[1,2,3]
l2=l
l2+=[1]
l
# zmienna l2 jest tylko "referencja" do zmiennej l
# to samo dzieje sie w przypadku przekazywania parametrow
#python uzywa przekazywania "przez referencje"

#ale zmienne niemodyfikowalne sa bardziej skomplikowane:

s="ala"
s2=s
s2+="ala"
#tutaj w momencie przypisania dokonywane jest "odwiazanie" (dereferencja)...
print s
print s2

#Mozemy sprawdzac "rownosc" referencji przy pomocy funkcji id() i konstrukcji "is"

l=[1]
l2=l #ta sama lista
l3=[1] # inna lista...?

id(l)
id(l2)
id(l3)

l==l2 #?
l==l3 #?

l is l2 #?
l is l3 #?

#To oczywiscie dziala inaczej dla wartosci niemodyfikowalnych

s="ala"
s2=s # ten sam napis
s3="ala" # inny napis?

s is s3 #?

#Trzeba tez bardzo uważać zinicjowaniem list...
ll= [[]] *5
print ll
ll[0].append(0)
print ll[0] # ok

print ll #oops!

#ale tez z parametrami domyslnymi

def f(l=[]):
l.append(1)
return l

print f() #ok...
print f() # ???

#No to jak "rozplesc" dwie listy?

l=[1,2,3]
l2=l
l3=l[:]

l2.append(2)
l3.append(3)
print l2
print l3
print l #?

#ze slownikami jest podobnie, do kopiowania sluzy metoda .copy()

d={}
d2=d
d3=d.copy()

d[1]=[]
print d,d2,d3

d[1].append(1)
print d

#ale kopiowanie jest "plytkie"...
d4=d.copy()
print d4

d[1].append(2)
print d4
## Juz wartosci pod kluczami pozostaja "wspolne"....

#Mamy na szczescie modul copy
import copy

#ktory umie robic kopie "glebokie":
d5=copy.deepcopy(d)
print d,d5
d[1].append(4)

print d,d4,d5

#Sprobujmy sobie jeszcze skomplikowac zycie,
#I zdefiniujmy funkcje wewnatrz funkcji:

y=1
def f(x):
y=5
def g(x):
y=x+6
return y
print y
return y+g(x)

f(y) #?
y #?

y=1
def f(x):
y=5
def g(x):
global y # mala zmiana?
y=x+6
return y
print y #tego y'ka nie ruszylismy...
return y+g(x)

f(y)
y

# A co sie stanie jesli zmienimy wartosc zmiennej po deklaracji funkcji...

x=1
def f():
return x

f()
x=2
f()

#Chyba, ze uzyjemy "domkniecia":

def pomnoz_przez(x):
def f(y):
return x*y
return f

x=5
przez_5=pomnoz_przez(x)
przez_5(10)
x=20
przez_5(20)

#
#

Lab 6 (zadania na zbiory i słowniki)

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 5.2 (lab 4) korzystając ze słowników.

Zbiory:

  1. Stwórz zbiór słów 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).

Trochę zadań do poćwiczenia

  1. Binarny ciąg Van der Corputa powstaje poprzez odwracanie zapisu binarnego kolejnych liczb naturalnych. Przed odwróceniem zapisy binarne są najpierw uzupełniane zerami do odpowiedniego miejsca. Np. jeśli rozpatrujemy ciąg trzycyfrowy (w zapisie binarnym), to przed odwróceniem mamy ciąg zapisów: [000, 001, 010, 011, 100, 101, 110, 111], co tłumaczy się na ciąg [0, 1, 2, 3, 4, 5, 6, 7]. Po odwróceniu zapisów mamy natomiast [000, 100, 010, 110, 001, 101, 011, 111], co tłumaczy się na ciąg [0, 4, 2, 6, 1, 5, 3, 7]. Napisz funkcję vdcorput(p), która dla zadanej liczby cyfr p zwróci odpowiadający jej ciąg Van der Corputa.
  2. Napisz iteracyjną i rekurencyjną wersję funkcji incr_segment(v), która dla zadanej listy v zwróci jej najdłuższy rosnący segment (spójny kawałek).
  3. Napisz funkcję prefix(s, w), która dla dwóch słów s i w zwróci najdłuższy wspólny prefix obu słów.
  4. Napisz funkcję ol_concat(s, w), która sklei ze sobą dwa słowa być może nakładając na siebie koniec s z początkiem w lub koniec w z początkiem s (jeśli są identyczne) aby otrzymać najkrótsze w tym sensie połączenie tych słów. Np. dla słów ol_concat(kajak, kredka) powinno być równe kredkajak, gdyż można je skleić albo do kredkajak, albo do kajakredka, ale pierwsze z tych słów jest krótsze w zapisie.
  5. Napisz funkcję convert(n, p1, p2), która przekształci liczbę n w systemie p1-tkowym na liczbę w systemie p2-tkowym. Można założyć, że zarówno p1 jak i p2 są z przedziału [2, 9]. Np. convert(23, 10, 2)=10111.
  6. Zaimplementuj funkcję bucket_sort(v), która posortuje ciąg liczb całkowitych z przedziału [-10000; 10000] używając sortowania kubełkowego.

Pierwsze zadanie zaliczeniowe (10 punktów)

Plik dmel-4-r5.47.gff zawiera anotacje chromosomu 4 muszki owocowej. Każda linijka stanowi pojedynczy wpis – rekord, składający się z kilku pól, m.in. nazwy chromosomu (kolumna 0), typu rekordu i spełnianej w ramach tego typu roli (kolumny 1 i 2), początkowej i końcowej pozycji wpisu (liczby całkowite, w tysiącach par zasad – kolumny 3 i 4), opcjonalnie wartości odczytu (tzw. score, kolumna 5), znaku nici DNA, której dotyczy wpis (+ lub -, kolumna 6) i deskryptora (kolumna 8).

  1. (3p.) Napisz funkcję score(f_in, f_out, x), która dla zadanego parametru x znajduje w pliku f_in rekordy typu DGIL_snap (rola match_part) o score, którego wartość bezwzględna jest większa niż x. Rekordy spełniające te warunki powinny zostać posortowane według malejącej wartości bezwzględnej score. Wynik ma mieć postać
    p_1 k_1 s_1
    p_2 k_2 s_2
    …
    (wartości oddzielane spacjami, nowa linia po każdym wierszu, p_i i k_i oznaczają odpowiedznio początkową i końcową pozycję i-tego wpisu, a s_i oznacza wartość score (nie wartość bezwzględną, po której sortujemy – znak ma pozostać!). Wynik powinien zostać zapisany do pliku f_out.
    Jako wynik, oprócz kodu programu należy przysłać plik wynik1.txt, stanowiący efekt wywołania funkcji score(“dmel-4-r5.47.gff”, “wynik1.txt”, 20).
  2. (3p.) Wyszukaj wszystkie rekordy z pliku dmel-4-r5.47.gff typu OrthoDB (rola orthologous_to), podziel je wg gatunków, w których występują ortologiczne geny (wartośc po “to_species”; np. Dper, Dmel, Cele, Dyak, Drer, …) i dla każdego gatunku wypisz plik w formacie gff (możesz skopiować całe linijki z pliku wejściowego) zawierający tylko rekordy, w których ortologiczne fragmenty leżą na tej samej nici (ostatnia i 7. kolumna zawierają ten sam znak) co w Dmel. Dla każdego z gatunków plik nazwij “nazwa_gatunku.gff”, np. “Dper.gff”.
  3. (4p.) Wyszukaj w pliku dmel-4-r5.47.gff promotorów (rekordy typu promoter, rola match), które nie należą do żadnego obszaru 5′ Untranslated Transcribed Region (rola five_prime_UTR). Wypisz do pliku wynik3.gff wszystkie rekordy zawierające takie promotory (całe linijki).

Zadania w postaci kodu źródłowego (w jednym pliku zadanie1_nr-indeksu.py) i plików wynikowych (załączniki z rozszerzeniem .txt lub .gff, żadnych kompresji itp.) przesyłają Państwo do obu prowadzących ćwiczenia (bartek@mimuw.edu.pl i pawel.bednarz@mimuw.edu.pl) przed wykładem za dwa tygodnie (26. XI 2012, 12:15). Proszę o umieszczenie w tytule e-mail’a hasła [WDI-1] i o wysyłanie ze skrzynek studenckich (aby łatwiej było zidentyfikować autora i ew. “zapożyczenia”).

WdI wykład i zadania o plikach

Slajdy z wykładu tu

 

  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

WDI – lab 4

Powtórka przed kolokwium

Zadania na rekurencję:

  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.

WDI – lab 3

Zadania wg. P. Bednarza

  1. używając funkcji randint modułu random wygenerować 10 losowych list długości 10000, posortować i wypisać (Tutaj przyda się iteracyjna wersja merge)
  2. Co robi funkcja f? 
    			def f(a, b):
				if b == 0:
					return 0
				return a + f(a, b - 1)
  3. Co się stanie jeśli w powyższym przykładzie zmienimi znak + na *?
  4. 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)
  5. 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:])
  6. Napisz rekurencyjną funkcję rec_rev(s), która dla zadanego napisu s zwróci odwrócony napis s.
  7. Napisz rekurencyjną funkcję rec_find(v, x), która zadanego posortowanej listy v zwróci wartość True, gdy element x występuje na liście v. W przeciwnym przypadku funkcja zwraca wartość False.
  8. Napisz rekurencyjną funkcję rec_pal(s) zwracającą True, gdy s jest palindromem. W przeciwnym przypadku funkcja zwraca wartość False.
  9. 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.