Author: Pawel

Pierwsze zadanie zaliczeniowe

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].

Lab 4

  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

Lab 3

  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.

WdI – lab2

(gwiazdka oznacza zadania trudniejsze – dodatkowe/dla chętnych)

  1. Zaimplementuj funkcję kalkulator(d, a, b), która przyjmuje jako parametr rodzaj wykonywanego działania i dwa parametry liczbowe i zwraca wynik w postaci liczbowej. Można założyć, że działanie jest pojedynczym znakiem ze zbioru {“+”, “-“, “*”, “/”}. Przykładowo kalkulator(“+”, 2, 2) ma zwrócić 4.
  2. (*) Spróbuj rozwiązać to zadanie sprytniej przy pomocy funkcji eval.
  3. Rozwiąż problem double_sum.
  4. Napisz funkcję cezar(napis, przesuniecie), która dla parametru napisowego napis i parametru całkowitego przesuniecie zwróci napis zaszyfrowany szyfrem Cezara z odpowiednim przesunięciem (użyj funkcji chr i ord do kodowania i odkodowywania liter; załóż, że napis składa się z liter alfabetu angielskiego).
  5. Napisz iteracyjną funkcję fib(n), która dla zadanej liczby całkowitej dodatniej n zwróci n-ty wyraz ciągu Fibonacciego.
  6. (*) Napisz rekurencyjną wersję funkcji fib z poprzedniego zadania.
  7. Napisz funkcję palindom(s), która dla zadanego ciągu znaków s sprawdzi, czy napis ten jest palindromem.
  8. Anagramem słowa s nazywamy słowo w powstałe przez poprzestawianie liter w słowie s. Napisz funkcję anagram(s,w), zwracającą wartość True wtedy i tylko wtedy, gdy w jest anagramem s.
  9. Zaimplementuj funkcje insertion_sort(l), bubble_sort(l) i selection_sort(l), wykonujące odpowiednio sortowanie przez wstawianie, sortowanie bąbelkowe i sortowanie przez wybór.
  10. Napisz funkcję cezar z zadania 4 przy użyciu funkcji map.

Zadanie dodatkowe (5pkt.)

W związku z tym, że wiele osób chciałoby zdobyć więcej punktów aby zaliczyć zajęcia opracowaliśmy dodatkowe zadanie. Jeśli ktoś stwierdzi, że zdobycie dodatkowych 5 punktów pomoże mu w zaliczeniu, może przysłać (do końca sesji) rozwiązanie.

Zadanie polega na stworzeniu pakietu do obsługi list zakupów. Rozwiązanie będzie się składało z trzech modułów. Pierwszy moduł ma zawierać funkcje do wczytywania pojedynczych list z trzech różnych formatów, opisanych na końcu treści zadania. Należy napisać osobną funkcję do wczytywania każdego z formatów (csv, lst, dct) oraz jedną zbiorczą funkcję wczytaj(plik), która na podstawie rozszerzenia nazwy pliku plik zwróci listę zakupów w wewnętrznym formacie, wybranym przez autora rozwiązania.
Drugi moduł ma zawierać następujące funkcje do operowania na listach zakupów:
– zakupy(lista, lista_zrobionych_zakupow), która zostawia na liście lista tylko te produkty, które pozostały jeszcze do kupienia (lub redukuje ilość produktu z listy lista w wypadku, gdy ilość danego produktu na liście lista jest większa niż na liście lista_zrobionych_zakupów)
– dodaj_zakupy(lista, nowe_zakupy), która doda do listy zakupów nowe produkty; w wypadku, gdy dany produkt jest już na liście lista, dodajemy po prostu do listy dodatkową ilość tego produktu z listy nowe_zakupy
– wczytaj_opis(opis), która dla każdego produktu wczyta i zapamięta jego kategorię – nie należy zakładać, że plik z opisem zawiera wpisy dla wszystkich produktów, które są obecne na aktualnej liście. Może też zawierać wpisy odnośnie produktów, których nie ma na aktualnej liście. Opis formatu pliku z opisem znajduje się poniżej.
Dodatkowo trzeci moduł służy do wypisywania listy zakupów w kilku formatach (tych, z których potrafimy wczytywać). Każda z funkcji wypisujących przyjmuje dodatkowy parametr kategorie, który jest listą i ma sprawić, żeby wypisane zostały tylko produkty z kategorii znajdujących się na liście. Produkty, które w chwili wypisywania nie mają przypisanej kategorii nie powinny zostać wypisane.

Plik z opisem jest postaci:
produkt kategoria

Formaty do wczytywania list:
1. Pliki z rozszerzeniem .csv:
masło 1, mleko 6, chleb 2
2. Pliki z rozszerzeniem .lst:
masło 1
mleko 6
chleb 2
3. Pliki z rozszerzeniem .dct:
{masło: 1, mleko: 6, chleb: 2}

Zadania w postaci spakowanego kodu źródłowego (w jednym pliku zadanie3_nr-indeksu.zip lub zadanie3_nr-indeksu.tar) przesyłają Państwo do obu prowadzących ćwiczenia (bartek@mimuw.edu.pl i pawel.bednarz@mimuw.edu.pl) do końca sesji (10.02.2013). Proszę o umieszczenie w tytule e-mail’a hasła [WDI-3] i o wysyłanie ze skrzynek studenckich (aby łatwiej było zidentyfikować autora i ew. “zapożyczenia”).

Powodzenia!