/inf

Zajęcia z informatyki 2020-21

Primary LanguagePython

Zajęcia z informatyki 2020-21

Teoria

Zbiór zadań CKE

Zbiór zadań.

Dane do zadań.

Część "Algorytmy w praktyce"

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

Przestrogi i morały

  • Sprawdź, czy liczby do arkusza zaimportowane są jako liczby

Zajęcia

Zadania maturalne

9 grudnia

Do domu: Proszę rozwiązać zadanie 10 "Dzielenie wielomianu" ze zbioru zadań.

Arkusz kalkulacyjny

25 listopada

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.

20 listopada

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.

18 listopada

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.

13 listopada

Najpierw dwa przykłady, potem zadanie arkusze/3_kurs.ods.

Do domu: arkusze/4_domowe_kolokwium.ods.

4 listopada

Na początku proszę uważnie przerobić materiały ze strony ucze-sie.pl.

Lista zadań

Dane do zadań można znaleźć w katalogu dane_do_zadan/.

Lista funkcji

  • vlookup()
  • right() , left()
  • countif() lub countifs() zlicza ilosc elementow pod okreslonymi warunkami. druga funkcja pozwala podawac kilka warunków.
  • and() , or() funkcja koniunkcji oraz alternatywy
  • mod() 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) zwraca 0
  • ceiling() - zaokrąglanie do góry, z precyzją (drugi argument) np. =ceiling(2,3;2) zwraca 4
  • <> - 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ść liczbowej
  • weekday(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

28 października

Zadania 65, 67.

21 października

Zadanie 1 (Ciągi rekurencyjne) i 64 (Obrazki) ze zbioru zadań CKE.

Dane do zadań.

Do domu: zadanie 58.

14 października

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.

9 października

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)

2 października

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.

30 września

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

23 września

  • 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).

18 września

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

16 września

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

11 września

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

Algorytmy

Algorytmy na liczbach całkowitych

Algorytmy wyszukiwania i porządkowania (sortowania)

  • 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,

Algorytmy numeryczne

  • 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,

Algorytmy na tekstach

  • 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,

Algorytmy kompresji i szyfrowania

  • 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,

Algorytmy badające własności geometryczne

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

Konfiguracja

Ś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