- 19.02: Bity, bajty, słowa
Rozwiązania proszę umieszczać w repozytorium a poniżej zapisać datę rozwiazania zadania.
# | Nazwa | Paweł | Piotr N-J | Krzysiek | Piotr T |
---|---|---|---|---|---|
58 | Systemy liczbowe | 13.02 | 22.02 | ||
59 | Ciekawe liczby | 14.02 | 24.02 | ||
60 | Dzielniki | 17.02 | 26.02 | ||
61 | Ciągi arytmetyczne | 20.02 | 27.02 | ||
62 | Liczby ósemkowe | 20.02 | 28.02 | ||
63 | Ciągi zerojedynkowe | 23.02 | 28.02 | ||
64 | Obrazki | 2.03 | 18.05 | ||
65 | Ułamki | 6.03 | 10.03 | ||
66 | Trójki liczb | 6.03 | 10.03 | ||
67 | Binarny fraktal Fibonacciego | 14.03 | |||
68 | Napisy — anagramy | 8.03 | 15.03 | ||
69 | Geny | 8.03 | 15.03 | ||
70 | Zasłona | 16.03 | 22.03 | ||
71 | Funkcja | 17.03 | 22.03 | ||
72 | Podobne napisy | 22.03 | |||
73 | Statystyki tekstu | 02.04 | |||
74 | Hasła | 06.04 | |||
75 | Szyfr afiniczny | 17.04 | |||
76 | Szyfr | 15.05 | |||
77 | Szyfr Vigenère’a | 15.05 | |||
78 | Podpis elektroniczny | 16.05 | |||
79 | Okręgi | ||||
80 | Trójkąty | ||||
81 | Czworokąty | ||||
82 | Piraci | 8.03 | 25.02 | 23.02 | 25.02 |
83 | Wilki i zające | 9.03 | 27.02 | 01.03 | |
84 | LPG | 14.03 | 01.03 | 23.02 | 05.03 |
85 | Oscypki | 16.03 | 22.03 | 24.03 | 05.03 |
86 | Wybory | 17.03, 30:17.77 | 25.03 | 20.03 | |
87 | U-977 | 18.03 | 25.03 | 25.02 | 20.03 |
88 | Sprzedaż choinek | 20.03 | 30.03 | 21.03 | |
89 | Punkty rekrutacyjne | 01.04 | 04.03 | 08.03 | |
90 | Akademiki | 20.03 | 02.04 | 05.03 | 08.03 |
91 | Numery PESEL | 05.04 | 08.03 | 08.03 | |
92 | Olimpiady | 06.04 | 08.03 | 08.03 | |
93 | Podróże | 07.04 | 08.03 | 08.03 | |
94 | Centyle | 16.05 | 08.03 | 18.03 | |
95 | Giełda Papierów Wartościowych | 18.05 | 15.03 | 18.03 | |
96 | Prognoza liczby ludności w Polsce do roku 2050 | 15.03 | 19.03 | ||
97 | Stopa bezrobocia | 19.03 | 19.03 | ||
98 | Dziennik ocen | 24.03 | 28.04 | 1.03 | 24.03 |
99 | Bezpieczeństwo w szkole | 28.04 | 20.03 | 24.03 | |
100 | E-learning | 08.05 | 23.03 | ||
101 | Karta MaturaSport | 13.05 | 14.04 | ||
102 | Portal społecznościowy | 14.05 | |||
103 | Rentgenodiagnostyka | 14.05 | |||
104 | Leki refundowane | 14.05 | |||
105 | Rośliny ogrodowe | 15.05 | |||
106 | Obserwacje ptaków | 15.05 | |||
107 | Loty pasażerskie | 15.05 | |||
108 | Stacje benzynowe | 16.05 | |||
109 | Urządzenia budowlane | 16.05 | |||
110 | Miejscowości w Polsce | 18.05 | |||
111 | Malware | 18.05 | |||
112 | Kod EAN | 18.05 |
- Sprawdź, czy liczby do arkusza zaimportowane są jako liczby
Do domu: Proszę rozwiązać zadanie 10 "Dzielenie wielomianu" ze zbioru zadań.
Zaczniemy od omówienia zdania "Telefony".
Następnie zrobimy wspólnie zadanie "Wirujący dysk i mrówka" z próbnej matury 2015. (W arkuszu!)
Następnie samodzielnie rozwiążencie (w arkuszu!) zadanie "Zawody sportowe" z tej samej próbnej matury (2015). Dane do zadania.
Proszę rozwiązać za pomocą arkusza kalkulacyjnego zadanie "Telefony" - informator maturalny, zad. 18 (str. 47). Czas na rozwiązanie: 40 minut, rozwiązanie proszę umieścić w zadanym czasie w repozytorium. Dane do zadania.
Na pierwszej lekcji proszę rozwiązać zadanie arkusze/5_ceny.ods. W tym czasie porozmawiamy indywidualnie o ocenach z wcześniejszych zadań.
Na drugiej lekcji zrobimy zadanie 83 ze zbioru zadań - z użyciem wyłącznie arkusza.
Zadanie dodatkowe: zadanie 5 z matury.
Najpierw dwa przykłady, potem zadanie arkusze/3_kurs.ods.
Do domu: arkusze/4_domowe_kolokwium.ods.
Na początku proszę uważnie przerobić materiały ze strony ucze-sie.pl.
Dane do zadań można znaleźć w katalogu dane_do_zadan/.
- Liczba PI - matura maj 2016, zad. 4
- Bruker - informator maturalny, zad. 17
- Telefony - informator maturalny, zad. 18
vlookup()
right()
,left()
countif()
lubcountifs()
zlicza ilosc elementow pod okreslonymi warunkami. druga funkcja pozwala podawac kilka warunków.and()
,or()
funkcja koniunkcji oraz alternatywymod()
funkcja modulo przyjmuje jako argumenty liczbę a i b, zwraca a mod b.$
,&
- operator konkatenacji (sklejenia)sum()
if()
mid()
value()
iferror()
floor()
- zwraca wartość zaokrągloną do dołu, z precyzją (drugi argument) np.=floor(2,3;3)
zwraca0
ceiling()
- zaokrąglanie do góry, z precyzją (drugi argument) np.=ceiling(2,3;2)
zwraca4
<>
- symbol nierówność w EXCELu, (nie!=
)month()
,day()
,year()
- fukcje zwracają wartość liczbową, przedstawiającą numer miesiaca/dnia/roku, w zależności od podanej wejściowej warotść liczbowejweekday(number,[type])
- funkcja zwraca dzień w określony w drugim argumeńcie sposób:- 1 or omitted - Numbers 1 (Sunday) through 7 (Saturday). Behaves like previous versions of Microsoft Excel.
- 2 - Numbers 1 (Monday) through 7 (Sunday).
- 3 - Numbers 0 (Monday) through 6 (Sunday).
- 11 - Numbers 1 (Monday) through 7 (Sunday).
- 12 - Numbers 1 (Tuesday) through 7 (Monday).
- 13 - Numbers 1 (Wednesday) through 7 (Tuesday).
- 14 - Numbers 1 (Thursday) through 7 (Wednesday).
- 15 - Numbers 1 (Friday) through 7 (Thursday).
- 16 - Numbers 1 (Saturday) through 7 (Friday).
- 17 - Numbers 1 (Sunday) through 7 (Saturday).
text()
- rozbudowana funkcja, do konwersji różnych wartości w liczby, w tekst: https://support.office.com/en-us/article/TEXT-function-20d5ac4d-7b94-49fd-bb38-93d29371225c
Zadania 65, 67.
Zadanie 1 (Ciągi rekurencyjne) i 64 (Obrazki) ze zbioru zadań CKE.
Do domu: zadanie 58.
Na pierwszej lekcji omówimy zadania z arkusza I części próbnej matury.
Na drugiej lekcji rozwiążecie pierwsze zadanie z arkusza II części tej matury. Pliki do arkusza.
Kontynuujemy implementację kodowania Huffmana. Dotychczasowa implementacja.
def encode(text: str, table: Dict[str, str]) -> str:
"""1 + 2 -> 3"""
output = []
for letter in text:
output.append(table[letter])
return ''.join(output)
def decode(text: str, tree: Dict) -> str:
"""3 + 4 -> 1"""
i = iter(text)
result = []
t = tree
while True:
if isinstance(t, str):
result.append(t)
t = tree
else:
bit = next(i, None)
if bit is None:
break
elif bit == "0":
t = t[0]
elif bit == "1":
t = t[1]
return "".join(result)
def code_to_tree(code: Dict) -> dict:
tree = dict()
def str_to_tree_rec(value: str, key: str, drzewo: Dict):
if len(drzewo) is 1:
drzewo[value[0]] = key
if drzewo.get(value[0], False) is not None:
str_to_tree_rec(value[1:], key, drzewo[value[0]])
else:
drzewo[value[0]] = {}
str_to_tree_rec(value[1:], key, drzewo[value[0]])
Do zrobienia.
- Komentarze
- Testy
- Dokończenie implementacji
code_to_tree
- Zaimplementowanie
tree_to_code
- Zaimplementowanie
generate_tree
- Wymyślenie sposobu zapisu/odczytu drzewa z kodowaniem
- Projekt i implementacja funkcji
encode_to_file
(potrzebna biblioteka bitstream) - Projekt i implementacja funkcji
decode_from_file
(znów przyda się bitstream)
Dzis trudniejszy temat: kodowanie Huffmana.
Nie dostajecie gotowych sygnatur funkcji (czy klas). Na lekcji omówimy działanie algorytmu i spróbujemy wspólnie zaprojektować struktury danych oraz sygnatury funkcji na nich działających.
Do omówienia są operacje:
- Kompresja, gdy mamy dany zestaw kodów odpowiadających kodowanym symbolom (przyjmijmy, że tekst zawsze dzielimy na pojedyńcze litery). Czy do kompresji właściwe jest drzewo Huffmana, czy może inna struktura?
- Dekompresja, gdy mamy dane drzewo Huffmana.
- Konwersja pomiędzy strukturami z powyższych dwóch punktów.
- Tworzenie drzewa Huffmana dla danego tekstu.
- Przeczytamy wspólnie rozwiązanie zadania anagramy. Wynik działania programu na słowniku ponad 100 tysięcy polskich słów:
adekr ['darek', 'derka', 'kadre', 'kedra', 'kreda', 'radek', 'redak']
den ['den', 'dne', 'edn', 'end', 'nde', 'ned']
dhq ['dhq', 'dqh', 'hdq', 'hqd', 'qdh', 'qhd']
dot ['dot', 'dto', 'odt', 'otd', 'tdo', 'tod']
efj ['efj', 'ejf', 'fej', 'fje', 'jef', 'jfe']
efq ['efq', 'eqf', 'feq', 'fqe', 'qef', 'qfe']
egl ['egl', 'elg', 'gel', 'gle', 'leg', 'lge']
ehj ['ehj', 'ejh', 'hej', 'hje', 'jeh', 'jhe']
ejs ['ejs', 'esj', 'jes', 'jse', 'sej', 'sje']
aeknr ['ekran', 'karne', 'kerna', 'nerka', 'ranek', 'ranke']
eimn ['emin', 'mein', 'mien', 'mine', 'mnie', 'niem']
epr ['epr', 'erp', 'per', 'pre', 'rep', 'rpe']
eps ['eps', 'esp', 'pes', 'pse', 'sep', 'spe']
est ['est', 'ets', 'set', 'ste', 'tes', 'tse']
fin ['fin', 'fni', 'ifn', 'inf', 'nfi', 'nif']
ghi ['ghi', 'gih', 'hgi', 'hig', 'igh', 'ihg']
gps ['gps', 'gsp', 'pgs', 'psg', 'sgp', 'spg']
hpu ['hpu', 'hup', 'phu', 'puh', 'uhp', 'uph']
ips ['ips', 'isp', 'pis', 'psi', 'sip', 'spi']
ipt ['ipt', 'itp', 'pit', 'pti', 'tip', 'tpi']
aklsu ['kalus', 'klaus', 'kulas', 'lasku', 'lukas', 'luska']
aaklp ['kapal', 'kapla', 'klapa', 'lapka', 'palak', 'palka']
aiklw ['kiwal', 'kwali', 'lawki', 'walki', 'wikla', 'wilka']
alpu ['lapu', 'lupa', 'palu', 'paul', 'pula', 'upal']
lrt ['lrt', 'ltr', 'rlt', 'rtl', 'tlr', 'trl']
ailns ['lsnia', 'silna', 'slain', 'slina', 'snail', 'snila']
mop ['mop', 'mpo', 'omp', 'opm', 'pmo', 'pom']
aoprw ['opraw', 'parow', 'porwa', 'prawo', 'prowa', 'prwoa']
ceiisw ['siwiec', 'swicie', 'swieci', 'wiesci', 'wiesic', 'wiscie', 'wisiec']
Warto wspomnieć tu informatyczną zasadę "garbage in garbage out".
-
Wyznaczymy ochotnika, który opracuje krótką informację na temat algorytmów wyszukiwania wzorca w tekście.
-
Pozostały czas spędzimy na rozwiązaniu zadania '21. Podzielność' ze strony 71 informatora maturalnego. Pliki z danymi.
-
Dla osób, którym zadanie 21 nie sprawiło problemu, jest zadanie Don't Get Rooked. Proszę zwrócić uwagę, że zadanie pochodzi z kategorii Brute Force::Backtracking (znaczenie tych słów wyjaśnię zainteresownym).
- W katalogu text/ utwórz plik
anagram.py
i zaimplementuj funkcję
def is_anagram(a: str, b: str) -> bool
zwracającą True
jedynie jeśli wyrazy a
i b
są anagramami.
Następnie napisz program, który znajduje wszystkie grupy anagramów w słowniku wyrazów angielskich. Znajdź
- grupę najliczniejszą
- grupę (nie jedno-elementową) z największą liczbą liter.
Algorytmy omówimy na zajęciach.
- W katalogu numeric/ w pliku
bisect.py
zaimplementuj funkcję
def zero_bisect(f: Callable[[float], float], a: float, b: float, precision: float) -> float
znajdującą miejsce zerowe funkcji f
w przedziale [a, b]
z dokładnością precision
(metodą bisekcji). Zakładamy, że znaki f(a)
i f(b)
są różne a funkcja f
jest ciągła.
Wykorzystaj tę funkcję do obliczenia wartości log_2 3
(logarytmu z 3 o podstawie 2).
- W katalogu sorting/ utwórz plik
bucket.py
i zaimplementuj algorytm sortowania kubełkowego pisząc funkcję o sygnaturze
def bucket_sort(numbers: List[int], lowest: int, highest: int) -> List[int]:
gdzie lowest
jest najmniejszą wartością w liście a highest
największą. Nie zapomnij o unit testach i porównaj czas działania z czasem działania sortowania bąbelkowego i przez scalanie (wynik porównania pokaż za pomocą wykresu).
- W katalogu numeric/ w pliku
area.py
zaimplementuj algorytm obliczania pola pod wykresem funkcji pisząc funkcję o sygnaturze
def area(f: Callable[[float], float], a: float, b: float, n: int) -> float:
gdzie f
to dana funkcja, a
i b
to granice całkowania zaś n
to liczba przedziałów w rozbiciu [a, b]
.
Proszę przetestować program i zmianę dokładności wyniku obliczając pole pod wykresem funkcji y = 2sqrt(1 - x^2)
.
def f(x: float) -> float:
return 2 * (1 - x * x) ** (1/2)
a = area(f, -1, 1, n) # interesuje nas zmiana wyniku dla różnych wartości n
- W katalogu numeric/ w pliku
monte.py
zaimplementuj algorytm obliczania wartości liczby pi metodą Monte Carlo omówioną na lekcji.
def pi(n: int) -> float:
gdzie n
to liczba prób.
-
W katalogu sorting/: napisz implementacje sortowania bąbelkowego, przez wybór i przez scalanie. Do każdego napisz testy i przetestuj czas wykonania. Wzór jak testować znajdziesz w rozwiązaniu zadania fibonacci/.
-
W katalogu maxmin/ pokazana jest "naiwna" i "zoptymalizowana" wersja algorytmu znajdującego maksimum i minimum w ciągu wraz z benchmarkiem.
- W katalogu fibonacci/: napisz funkcje obliczające n-ty wyraz ciągu Fibonacciego na dwa sposoby: iteracyjnie i rekurencyjnie. Napisz testy poprawności i porównaj wydajność obu implementacji.
- W katalogu gcd: napisz funkcje obliczające największy wspólny dzielnik liczb a i b na dwa sposoby: iteracyjnie i rekurencyjnie. Napisz testy poprawności.
- W katalogu number_representation: napisz funkcje konwertujące liczby na reprezentację binarną, szesnastkową, dziesiętną i z powrotem. Napisz testy poprawności.
- W katalogu primality: napisz funkcje sprawdzające, czy dana liczba jest pierwsza lub doskonała. Napisz testy poprawności.
- W katalogu greedy_change: zaimplementuj funkcję 'wydającą resztę' metodą zachłanną. Napisz testy poprawności.
- reprezentacja liczb w dowolnym systemie pozycyjnym, w tym w dwójkowym i szesnastkowym,
- sprawdzanie, czy liczba jest liczbą pierwszą, doskonałą,
- rozkładanie liczby na czynniki pierwsze,
- iteracyjna i rekurencyjna realizacja algorytmu Euklidesa,
- iteracyjne i rekurencyjne obliczanie wartości liczb Fibonacciego,
- wydawanie reszty metodą zachłanną,
- jednoczesne znajdowanie największego i najmniejszego ele- mentu w zbio rze: algo rytm naiwny i optymalny,
- algorytmy sortowania ciągu liczb: bąbelkowy, przez wybór, przez wsta wianie linio we lub binarne, przez scalanie, szybki, kubełkowy,
- obliczanie wartości pierwiastka kwadratowego,
- obliczanie wartości wielomianu za pomocą schematu Hornera,
- zastosowania schematu Hornera: reprezentacja liczb w różnych syste mach liczbo wych, szybkie podnoszenie do potęgi,
- wyznaczanie miejsc zerowych funkcji metodą połowienia,
- obliczanie pola obszarów zamkniętych,
- sprawdzanie, czy dany ciąg znaków tworzy palindrom, anagram,
- porządkowanie alfabetyczne,
- wyszukiwanie wzorca w tekście,
- obliczanie wartości wyrażenia podanego w postaci odwrotnej notacji polskiej,
- kody znaków o zmiennej długości, np. alfabet Morse’a, kod Huffmana,
- szyfr Cezara,
- szyfr przestawieniowy,
- szyfr z kluczem jawnym (RSA),
- wykorzystanie algorytmów szyfrowania, np. w podpisie elektronicznym,
- sprawdzanie warunku trójkąta,
- badanie położenia punktów względem prostej,
- badanie przynależności punktu do odcinka,
- przecinanie się odcinków,
- przynależność punktu do obszaru,
- konstrukcje rekurencyjne: drzewo binarne, dywan Sierpińskiego, płatek Kocha.
Środowisko wirtualne (jednorazowa inicjalizacja)
python3 -m venv ~/envs/inf
Aktywowanie środowiska
source ~/envs/inf/bin/activate
Deaktywacja
deactivate
Upgrade pip
-a (jednorazowo)
python3 -m pip install --upgrade pip
Instalacja modułów (jednorazowo)
python3 -m pip install pylint