>Wiktor Hajduk
# [WH] Zajęcia z programowania - notatki

Link do sekcji na Themisie: https://themis.ii.uni.wroc.pl/KORJ/

## Zakres materiału do matury

**a) algorytmy na liczbach całkowitych**
- [x] reprezentacja liczb w dowolnym systemie (w tym 2. i 16.), zamiana pomiędzy systemami
- [x] działanie na ułamkach z wykorzystaniem NWD i NWW
- [x] sprawdzanie czy liczba jest pierwsza, doskonała
- [x] rozkładanie liczby na czynniki pierwsze
- [x] iteracyjna i rekurencyjna metoda algorytmu Euklidesa
- [x] wydawanie reszty metodą zachłanną i dynamiczną
- [x] problem plecakowy
- [x] obliczanie elementów ciągu (np. Fibonacciego) metodą iteracyjną i rekurencyjną
- [x] generowanie sita Eratostenesa

**b) algorytmy wyszukiwania i porządkowania (sortowania)**
- [x] ~~jednoczesne znajdowanie największego i najmniejszego elementu w zbiorze: algorytm naiwny i optymalny~~
- algorytmy sortowania ciągu liczb:
- [x] bąbelkowy
- [x] przez wybór
- [x] przez wstawianie liniowe ~~lub binarne~~
- [x] przez scalanie
- [x] szybki
- [x] kubełkowy
- [x] znajdowanie lidera w zbiorze
- [x] wyszukiwanie elementu za pomocą wyszukiwania binarnego
- [x] znajdowanie podciągu o pewnej własności, np. spójnego niemalejącego

**c) algorytmy numeryczne**
- [x] ~~obliczanie wartości pierwiastka kwadratowego~~
- [ ] ~~obliczanie wartości wielomianu za pomocą schematu Hornera~~
- ~~zastosowania schematu Hornera:~~
- [ ] ~~reprezentacja liczb w różnych systemach liczbowych~~
- [ ] szybkie podnoszenie do potęgi <-
- [x] wyznaczanie miejsc zerowych funkcji metodą połowienia
- [ ] ~~obliczanie pola obszarów zamkniętych~~
- [ ] ~~obliczanie przybliżonej wartości $\pi$ za pomocą metody Monte Carlo~~

**d) algorytmy na tekstach**
- [x] sprawdzanie, czy dany ciąg znaków tworzy palindrom, anagram
- [ ] porządkowanie alfabetyczne
- [ ] wyszukiwanie wzorca w tekście metodą naiwną i metodą hashowania
- [x] ~~obliczanie wartości wyrażenia podanego w postaci odwrotnej notacji polskiej~~

**e) algorytmy kompresji i szyfrowania**
- [ ] kody znaków o zmiennej długości, np. alfabet Morse’a ~~, kod Huffmana~~
- [x] szyfr Cezara (ROT13)
- [ ] szyfr przestawieniowy <-
- [ ] ~~szyfr z kluczem jawnym (RSA)~~
- [ ] ~~wykorzystanie algorytmów szyfrowania, np. w podpisie elektronicznym~~

**f) algorytmy badające własności geometryczne**
- [x] ~~sprawdzanie warunku trójkąta~~
- [x] ~~badanie położenia punktów względem prostej~~
- [x] ~~badanie przynależności punktu do odcinka~~
- [x] ~~przecinanie się odcinków~~
- [ ] ~~przynależność punktu do obszaru~~
- konstrukcje rekurencyjne
- [ ] ~~drzewo binarne~~
- [ ] ~~dywan Sierpińskiego~~
- [ ] ~~płatek Kocha~~
- [ ] ~~zbiór Cantora~~
- [ ] ~~obliczanie przybliżonej wielkości pola obszarów zamkniętych~~

**g) inne**
- struktury danych:
- [ ] kolejka <-
- [x] stos
- [x] vector (lista)
- [ ] grafy

*Źródła:*
[Podstawa 2015](https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Podstawa_programowa/Tom_6_Edukacja_matematyczna_i_techniczna.pdf)
[Podstawa 2023](https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2023/podstawa_programowa/informatyka.pdf)

## 17.05.2022

### Tablica
https://miro.com/app/board/uXjVO0XOtMk=/

### Zadanie dodatkowe
**Wejście:** Liczba całkowita *n*.
**Wyjście:** Wszystkie ciągi o długości *n* złożone z liter A i B.

// Tu napisz rozwiązanie zadania:

## 13.05.2022

### Tablica
https://miro.com/app/board/uXjVO1ZQx5I=/

## 08.04.2022

### Tablica
https://miro.com/app/board/uXjVO-Pein0=/

## 01.04.2022

### Tablica
https://miro.com/app/board/uXjVOAN5cz0=/

### Zadanie 2.3

def fib(n):
    if(n < 2)
        return 1
    return fib(n-2) + fib(n-1)
    

def fib2(n):
    if n == 1 or n == 2:
        return 1
    if(n % 2 == 0:
        t1 = fib2(n/2+1)
        t2 = fib2(n/2-1)
        return t1*t1 - t2*t2 # :)
       else:
        return fib2((n+1)/2)*fib2((n+1)/2) + fib2((n-1)/2)* fib2((n-1)/2) # :(

### Zadanie domowe
> Mea culpa. W poprzednim zadaniu domowym popopełniłem dwa błędy. Jeden z nich można było wyłapać i mnie o nim powiadomić - zadanie PRZESTAW zdecydowanie nie pasuje do mojego opisu, jakoby było to zadanie podchodzące pod szyfr przestawieniony. Drugą pomyłką był opis do zadania KOLEJKA. Zostało ono napisane przez Ciebie poprawnie. Natomiast, by przeszło na themisie NIE NALEŻY w niej używać kolejki dostarczonej przez bibliotekę STL, a napisać własną, np. na tablicy.

#### Poprawione zadanie domowe
- https://themis.ii.uni.wroc.pl/KORJ/KOLEJKA (za pomocą tablicy)
- https://themis.ii.uni.wroc.pl/KORJ/ACPP132 tu `queue` się przyda :)
- https://themis.ii.uni.wroc.pl/KORJ/RL_PRZESTAW - zamiast zadania PRZESTAW
- pozostałe zadania z 18.03.2022

## 18.03.2022

### Zadanie domowe
- https://themis.ii.uni.wroc.pl/KORJ/KOLEJKA ~~$\leftarrow$ należy zrobić to zadanie za pomocą struktury `queue`~~ (https://www.cplusplus.com/reference/queue/queue/)
- https://themis.ii.uni.wroc.pl/KORJ/OKNO - zadanie na myślenie
- https://themis.ii.uni.wroc.pl/KORJ/ROT13 - w ramach przypomnienia
- ~~https://themis.ii.uni.wroc.pl/KORJ/PRZESTAW~~ - zadanie podchodzące pod szyfr przestawieniowy (http://www.crypto-it.net/pl/proste/szyfry-przestawieniowe.html)
- https://themis.ii.uni.wroc.pl/KORJ/FASTPOW_EASY - szybkie podnoszenie do potęgi (uproszczone)
- https://themis.ii.uni.wroc.pl/KORJ/CFUNKCJE1 - szybkie podnoszenie do potęgi

### Szybkie potęgowanie
> Źródło: algorytm.edu.pl

## 11.03.2022

### Poruszone pojęcia
- Sortowania
- Czy słowo jest anagramem/palindromem
- Wyszukiwanie binarne
- Algorytm euklidesa
- Obliczanie NWD, NWW
- Złożoność obliczeniowa

### Tablica
https://miro.com/app/board/uXjVOFjc4xA=/

## 25.02.2022 Sortowanie kubełkowe
Dodatkowe zadanie domowe:
[Sortowanie kubełkowe](https://themis.ii.uni.wroc.pl/KORJ/BUCKETS) z ostrożnym zajmowaniem pamięci

### Tablica
https://miro.com/app/board/uXjVOJwu0kY=/

## 17.02.2022 Sortowanie szybkie
Zadanie domowe:
- [Sortowanie przez scalanie](https://themis.ii.uni.wroc.pl/KORJ/SORT_MERGE) z sortowaniem w miejscu / nie zajmowaniem zbędnie pamięci
- [Sortowanie szybkie](https://themis.ii.uni.wroc.pl/KORJ/SORT_QUICK)

### Tablica
https://miro.com/app/board/uXjVOLi1Mus=/

## 03.02.2022 Vectory i wczytywanie danych
https://miro.com/app/board/uXjVOQdo92g=/

## 20.01.2022 Sortowanie przez scalanie
Zadanie domowe:
- [Sortowanie przez wstawianie](https://themis.ii.uni.wroc.pl/KORJ/SORT_INSERT) z wyszukiwaniem miejsca do wstawienia liniowo / za pomocą wyszukiwania binarnego
- [Sortowanie przez scalanie](https://themis.ii.uni.wroc.pl/KORJ/SORT_MERGE)

### Tablica
https://miro.com/app/board/uXjVOUdYzrg=/

## 13.01.2022 Sortowanie przez wstawianie - liniowe i binarne, sortowanie przez zliczanie i wstęp do sort. przez scalanie

Zadanie domowe:
- [Sortowanie przez wstawianie](https://themis.ii.uni.wroc.pl/KORJ/SORT_INSERT) z wyszukiwaniem miejsca do wstawienia za pomocą wyszukiwania binarnego
- [Sortowanie przez zliczanie](https://themis.ii.uni.wroc.pl/KORJ/CTABLES3)
- [Scalanie](https://themis.ii.uni.wroc.pl/KORJ/MERGE1)

### Notatki
Tablica: https://miro.com/app/board/uXjVOVqbgcI=/

## 06.01.2022 Sortowanie przez wybór
Zadanie domowe:
- [Matura 2019, część 1.](https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Arkusze_egzaminacyjne/2019/formula_od_2015/informatyka/MIN-R1_1P-192.pdf) - Zadania 2.3 i 3.

### Notatki
[Kopia tablicy](https://jaskiewi.cz/zajecia/tablica-06.01.22.pdf)

## 23.12.2021 Sortowanie bąbelkowe
Zadanie domowe:
- [Matura 2020, część 1.](https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Arkusze_egzaminacyjne/2020/formula_od_2015/informatyka/MIN-R1_1P-202.pdf) - Zadanie 3.
- https://themis.ii.uni.wroc.pl/KORJ/BUBSORT

### Notatki
Matura część 1. typu napisz algorytm:
https://hackmd.io/@barnij/r1i9nRbiK

Tablica:
https://miro.com/app/board/uXjVOZbPf_g=/

## 12.12.2021 Matura i geometria
Zadanie domowe:
- https://themis.ii.uni.wroc.pl/KORJ/ODCINKI
- https://themis.ii.uni.wroc.pl/KORJ/WSPLN
- [Matura 2021, część 1.](https://cke.gov.pl/images/_EGZAMIN_MATURALNY_OD_2015/Arkusze_egzaminacyjne/2021/Informatyka/poziom_rozszerzony/EINP-R1-100-2105.pdf) - Zadania od 2.3 do 3.3

### Tablica
https://miro.com/app/board/uXjVObDAJdA=/

## 05.12.2021 Ciąg Fibonacciego
Rekurencyjnie (bez/ze spamiętywaniem) i iteracyjnie.
\+ Zadanie 2.2 MATURA PRÓBNA OPERON 2020/21

Zadanie domowe:
Themis: Przerwany Fibonacci, Prawie ciąg fibbonacciego

### Tablica
https://miro.com/app/board/uXjVOdN329Q=/

## 28.11.2021 Rekurencja i problem wież Hanoi
Zadanie domowe:
[Zadanie 1.2 MATURA PRÓBNA OPERON 2020/21](https://operon.pl/Oferta/Egzaminy/Matura-z-Operonem/Baza-arkuszy#EDYCJA%202020/2021)

### Tablica
https://miro.com/app/board/uXjVOffxBzE=/

## 21.11.2021 Podstawy rekurencji

### Tablica
https://miro.com/app/board/o9J_lh3nrKo=/

## 12.11.2021 Znajdowanie zera funkcji metodą połowienia

### Tablica
https://miro.com/app/board/o9J_lj3InPo=/?invite_link_id=863986099618

## 04.11.2021 Obliczanie pierwiastka kwadratowego i znajdowanie zera funkcji metodą połowienia

### Tablica
https://miro.com/app/board/o9J_ll3ZNY8=/?invite_link_id=821147037965

## 28.10.2021 Liczby pierwsze/doskonałe i warunki budowy trójkąta

### Tablica
https://miro.com/app/board/o9J_lnXqtlE=/?invite_link_id=421184393660

## 24.10.2021 Zamiana liczb o różnych podstawach

### Tablica
https://miro.com/app/board/o9J_loJ7luk=/?invite_link_id=462908003088

## 14.10.2021 ONP i stos
### Tablica
https://miro.com/app/board/o9J_lqF2grE=/?invite_link_id=669294251918

---
CZĘŚĆ PIERWSZA: https://hackmd.io/@barnij/SJdo8iCM_