python_prog2_lab2

2098 days ago by macieksk

%jsmath Zadanie 1 Napisz w Python-ie klasę macierzy binarnych kodowanych bitowo: class BitMatrix W klasie BitMatrix macierz zapisana jest jako kolekcja (np. lista) wierszy. Każdy wiersz to wektor zero-jedynkowy kodowany bitowo, czyli kolekcja (lista) obiektow typu "int". Klasa BitMatrix powinna posiadać operacje pozwalające na: tworzenie macierzy, transformowanie do innych różnych reprezentacji macierzy, transponowanie macierzy, mnożenie macierzy, wykonanie operacji znalezienia silnie spójnych składowych grafu reprezentowanego przez macierz poprzez obliczenie M^N W tym celu, wykonajmy kilka mniejszych ćwiczeń: 
       
\newcommand{\Bold}[1]{\mathbf{#1}}\begin{array}{l} \verb|Zadanie|\phantom{x}\verb|1|\\ \phantom{x}\\ \verb|Napisz|\phantom{x}\verb|w|\phantom{x}\verb|Python-ie|\phantom{x}\verb|klasę|\phantom{x}\verb|macierzy|\phantom{x}\verb|binarnych|\phantom{x}\verb|kodowanych|\phantom{x}\verb|bitowo:|\phantom{x}\verb|class|\phantom{x}\verb|BitMatrix|\\ \phantom{x}\\ \verb|W|\phantom{x}\verb|klasie|\phantom{x}\verb|BitMatrix|\phantom{x}\verb|macierz|\phantom{x}\verb|zapisana|\phantom{x}\verb|jest|\phantom{x}\verb|jako|\phantom{x}\verb|kolekcja|\phantom{x}\verb|(np.|\phantom{x}\verb|lista)|\phantom{x}\verb|wierszy.|\\ \verb|Każdy|\phantom{x}\verb|wiersz|\phantom{x}\verb|to|\phantom{x}\verb|wektor|\phantom{x}\verb|zero-jedynkowy|\phantom{x}\verb|kodowany|\phantom{x}\verb|bitowo,|\phantom{x}\verb|czyli|\phantom{x}\verb|kolekcja|\phantom{x}\verb|(lista)|\phantom{x}\verb|obiektow|\phantom{x}\verb|typu|\phantom{x}\verb|"int".|\\ \phantom{x}\\ \verb|Klasa|\phantom{x}\verb|BitMatrix|\phantom{x}\verb|powinna|\phantom{x}\verb|posiadać|\phantom{x}\verb|operacje|\phantom{x}\verb|pozwalające|\phantom{x}\verb|na:|\\ \phantom{xxxx}\verb|tworzenie|\phantom{x}\verb|macierzy,|\\ \phantom{xxxx}\verb|transformowanie|\phantom{x}\verb|do|\phantom{x}\verb|innych|\phantom{x}\verb|różnych|\phantom{x}\verb|reprezentacji|\phantom{x}\verb|macierzy,|\\ \phantom{xxxx}\verb|transponowanie|\phantom{x}\verb|macierzy,|\\ \phantom{xxxx}\verb|mnożenie|\phantom{x}\verb|macierzy,|\\ \phantom{xxxx}\verb|wykonanie|\phantom{x}\verb|operacji|\phantom{x}\verb|znalezienia|\phantom{x}\verb|silnie|\phantom{x}\verb|spójnych|\phantom{x}\verb|składowych|\phantom{x}\verb|grafu|\phantom{x}\verb|reprezentowanego|\phantom{x}\verb|przez|\phantom{x}\verb|macierz|\phantom{x}\verb|poprzez|\phantom{x}\verb|obliczenie|\phantom{xx}\verb|M^N|\\ \phantom{x}\\ \phantom{x}\\ \verb|W|\phantom{x}\verb|tym|\phantom{x}\verb|celu,|\phantom{x}\verb|wykonajmy|\phantom{x}\verb|kilka|\phantom{x}\verb|mniejszych|\phantom{x}\verb|ćwiczeń:| \end{array}
%latex {\bf Cw 1.} Zbadajmy ile bitow da sie zakodowac bitowo w int(). Przekonaj się w Pythonie dla jakich "i" 0..65 poniższe obiekty są wciąż klasy "int": \begin{itemize} \item $(1<<i) $ \item $-(1<<i) $ \item $(-1<<i) $ \item $(-1<<i)*2$ \item $(1<<i)*2$ \end{itemize} 
       
%python print (1<<50) print (-1<<50) 
       
1125899906842624
-1125899906842624
%python # Cw 2. # Napisz funkcję to_bit_vector(lst), która dostawszy na wejściu listę 0,1 dowolnej długości, # utworzy bit_vector odpowiadający tej liście. # Niech bit_vector to będzie lista długości "n" obiektów typu int. # Każdy z tych obiektów koduje "k" bitów (k z poprzedniego ćwiczenia). # Jeśli na liście zapisanych jest N bitów, czyli N=len(lst) to jakie musi być "n"? def to_bit_vector(lst): return bvec # Cw 2.1 # Napisz funkcję from_bit_vector(lst), ktora dostawszy na wejsciu bit_vector utworzy liste 0-1-kową def bit_vector_to_list(bvec): return lst # Przetestuj swoje funkcje. # Czy ich zlozenie jest idempotentne? def test_my_f(): return 
       
 
       
%python # Cw 3 # Napisz funkcję, ktora dostawszy macierz w formacie array (numpy), wygeneruje listę wierszy które są bit_vector-ami # Przypomnienie: # Macierz numpy.array można stworzyć z listy list import numpy as np ar = np.array( [ [ int(i != j) for j in xrange(5)] for i in xrange(4)] ) print(ar) # Dostęp do elementów macierzy numpy: ar[0][1]==ar[0,1]==1 
       
[[0 1 1 1 1]
 [1 0 1 1 1]
 [1 1 0 1 1]
 [1 1 1 0 1]]
True
%python # Cw 4. # Napisz odpowiedniki powyższych funkcji transformujące w drugą stronę 
       
%python # Cw 5. # Wykonaj wizualizacje binarnej macierzy bit_vectorów import matplotlib.pyplot as plt ### Zmien opcje w.plt imshow na odpowiadające Tobie bardziej. p=plt.imshow(ar,interpolation='nearest') plt.savefig('matrixmap.png') #Tak wyswietlamy obrazki na sage # plt.show() # To wykonujemy lokalnie z konsoli # Sprawdź "obrazkowo" poprawność funkcji z 3 i 4 def visualize_bitmatrix(bm): return 
       
%python # Cw 5. # Napisz funkcję, ktora mnoży przez siebie dwie macierze bit_vector-ów. # Postaraj się użyć funkcji zip. # Wskazówka: Jak otrzymać element (M1*M2)[i,j] tylko przy pomocy operacji logicznych? # Wskazówka 2: # Cw 6. # Napisz funkcję, ktora transponuje macierz bit_vector-ów (pozostając w reprezentacji "lista wierszy" zamienia M(i,j) na M(j,i)). # Rozważ następujące metody wykonania zadania: # a) wykorzystanie numpy # b) wykorzystanie transponowania w pythonie: http://www.ehow.com/how_8448012_transpose-list-lists-python.html # c) napisanie funcje pomocniczą: def getitem_bv(bv,x,y): ''' Returns element (x,y) from a bit_vector. ''' return elem 
       
%python 
       
0
%python N=100 k=10 ar = np.array( [ [ (i==j or i==j+k or i==j-k) for j in xrange(N)] for i in xrange(N)] ) p=plt.imshow(ar,interpolation='nearest') plt.savefig('matrixmap.png') # Cw 8. # Wykorzystując mnożenie macierzy bit_vector-ów napisz funkcję, która policzy spójne składowe grafu reprezentowanego przez powyższą binarną symetryczną macierz. # Wskazówka: Do policzenia różnych składowych użyj typu "set", # ale pamiętaj, że nie można wrzucać do niego list tylko tuple. # tuple(lst) konwertuję listę do tuple. def connected_components(bv_matrix): return cc 
       
 
       
# Klasy będą na następnych zajęciach.