# Zadanka do egzaminu inżynierskiego
link do egzaminów: https://drive.google.com/drive/u/0/folders/1sVRsMvr_4KBXupye_4NROo7VlDql689i
link do notatek jeża z algebry (średnio przydatne):
https://ii.uni.wroc.pl/~aje/Alg2019/notatki.pdf

## Luty 2021

### Programowanie A

drzewo binarne - liczba synów każdego wierzchołka wynosi nie więcej niż dwa.

Pre-order: ![Uploading file..._92v3gw2jn]()
In-order: ![Uploading file..._418vqxwhv]()
Post-order: ![Uploading file..._7op7jkug0]()

1)

; Predykaty:
(define (tree? x)
  (or (leaf? x)
      (and (node? x) (number? (node-val x))
           (tree? (node-left x))
           (tree? (node-right x)))))

(define (leaf? x)
    (null? x))

(define (node? x)
    (and (list? x)
         (= (length x) 4)
         (eq? (car x) 'node)))
         
; Selektory:       
(define (node-val x) (cadr x))
(define (node-left x) (caddr x))
(define (node-right x) (cadddr x))

; Konstruktory:
(define (make-node v l r)
    (list 'node v l r))
    
(define leaf null)

Alternatywna wersja jest dla definiowania liścia jako 'leaf, wtedy wszystko zostaje tak samo, ale zmienia się konstruktor liścia i predykat czy coś jest liściem.

;Predykat:
(define (leaf? x) (eq? x 'leaf))

;Konstruktor:
(define leaf 'leaf)

2)
**Nieużytek** - część pamięci, która zostaje zaalokowana, ale nigdy później nie jest wykorzystana. Np. gdy używamy (append xs ys). Wtedy lista xs jest kopiowana - 'xs, i powstaje nowy twór 'xs + ys. Oryginalny xs już nigdy nie zostanie użyty i staje się **nieużytkiem**, pochłoniętym przez garbage collectora.

3)

; a
(define (bin-tree? t)
  (or (node? t)
       (leaf? t)))

(define (node? x)
  (and (list? x)
       (= (length x) 4)
       (eq? (first x) 'node )
       (bin-tree? (third x))
       (bin-tree? (fourth x))))

(define (leaf? x) (eq? x 'leaf ))

(define (make-tree v l r) (list 'node v l r))
(define (make-leaf) 'leaf)

; c
(define (abs x) (if (< x 0) (* -1 x) x))
(define (left t) (third t))
(define (right t) (fourth t))

(define (balanced? tree)
  (define (get-balance t)
    (if (leaf? t)
      (cons 0 #t)  //#t == true
      (let* ([left-balance (get-balance (left t))]
             [right-balance (get-balance (right t))])
            (cons (+ (max (car left-balance) (car right-balance)) 1)
                  (and (cdr left-balance)
                       (cdr right-balance)
                       (<= (abs (- (car left-balance) (car right-balance))) 1))))))
  (cdr (get-balance tree)))

;;;;;;;;;
(define first-node (make-tree 1 'leaf 'leaf))
(define third-node (make-tree 3 'leaf 'leaf))
(define sec-node (make-tree 2 first-node third-node))


1)

class Leaf:
    def __init__(self):
        pass

    def node_val(self):
        return None


class Node:
    def __init__(self, v, l, r):
        self.v = v
        self.l = l
        self.r = r

    def node_val(self):
        return self.v

    def node_left(self):
        return self.l

    def node_right(self):
        return self.r


def tree_walk(tree: Node):
    current = tree
    stack = []
    while True:
        if current.node_val() is not None:
            stack.append(current)
            current = current.node_left()
        elif stack:
            current = stack.pop()
            print(current.node_val())
            current = current.node_right()
        else:
            break

2)

def check_bst(tree: Node):
    result = []
    current = tree
    stack = []
    while True:
        if current.node_val() is not None:
            stack.append(current)
            current = current.node_left()
        elif stack:
            current = stack.pop()
            result.append(current.node_val())
            current = current.node_right()
        else:
            break
    for i in range(1, len(result)):
        if result[i] < result[i - 1]:
            return False          
    return True

3

class Leaf {}

class BinaryTreeNode<T> {
  constructor(
    public value: T,
    public left: BinaryTreeNode<T> | Leaf,
    public right: BinaryTreeNode<T> | Leaf
  ) {}
}

class BinaryTree<T> {
  constructor(public root: BinaryTreeNode<T> | Leaf) {}
}


const removeMinFromBST = <T>(tree: BinaryTree<T>) => {
  if (tree.root instanceof Leaf) {
    return;
  }

  if (tree.root.left instanceof Leaf) {
    tree.root = tree.root.right;
    return;
  }

  let parent = tree.root;
  let child = tree.root.left;
  while (true) {
    if (child.left instanceof Leaf) {
      parent.left = child.right;
      break;
    } else {
      parent = child;
      child = child.left;
    }
  }
};

### Programowanie B

#### Zadanie 1

a)
Wyraz abbaabbac nie należy do języka. Jeśli "c" możemy uzyskać tylko za pomocą produkcji X -> cXd i X -> cXc. Biorąc pod uwagę że u nas "c" występuje pojedynczo i nie następuje po nim "d", to nie możemy otrzymać takiej formy naszymi produkcjami.

b)
**Gramatyka jednoznaczna** - taka, w której każde słowo ma co najwyżej jedno drzewo wyprowadzenia.

Gramatyka nie jest jednoznaczna, kontrprzykład:

Dla abba:

* S -> SS -> SabSba -> $\epsilon$abba -> abba
* S -> SS -> abSbaS -> abba$\epsilon$ -> abba

Koniec dowodu.

**UWAGA - gdyby gramatyka była jednoznaczna:**
Przykładowy dowód jak pokazać, że gramatyka jest jednoznaczna:

Dla Gramatyki G2-jednoznacznej zadanej jako:
* S -> aS,
* S-> bbS,
* S -> $\epsilon$

**Podstawa indukcji:**
niech n=1, będą to możliwe wyrazy do otrzymania z symbolu startowego S w pierwszym kroku - wyrazy o długości 1.
* S -> aS -> a$\epsilon$ $\in$ G2 i ma jedno drzewo rozbioru
* S -> bbS -> bb$\epsilon$ $\in$ G2 i ma jedno drzewo rozbioru
* S -> $\epsilon$ $\in$ G2 i ma jedno drzewo rozbioru

baza: a nalezy bo a,empty
bb nalezy bo bb,empty

**Krok indukcyjny:**

*Założenie indukcyjne*:
załóżmy ze wszystkie słowa o długości <= n tworzone przez gramatyke G2 maja dokładnie jedno drzewo rozbioru.

weźmy słowo w należące do G2 o dlugosci n+1
* jeśli w=aw': to w tworzymy przez S->aS gdzie to S ma zrobic w'. A w' nalezy do G2 i |w'| == n i jest jednoznaczne, wiec w jest jednoznaczne z zal. ind
* jesli w=bbw': to tworzone przez S->bbS, gdzie ... |w'| == n-1.

c)
S -> SS, S -> X, X -> $\epsilon$, X -> cXd

d)
Zbiór A2 = L(G1) $\cap$ *L*((a + b + c)$^*$)
Czyli mając produkcje z gramatyki G1, powinniśmy skreślić produkcje:
* S -> SS,
* S -> abSba,
* S -> X,
* X -> $\epsilon$,
* ~~X -> cXd~~
* X -> cXc

Czy `is_ab_seq` miało sprawdzać czy to jest stworzone z produkcji S-> abSba?

Poniżej jest źle:

def is_ab_seq(x: str):
    if x == '':
        return True
    return x.startswith('ab') and is_ab_seq(x[2:])


def is_in_lang(x: str):
    if x == '':
        return True
    xs = x.split('c')
    has_proper_ab_len = len(xs) == 3 and len(xs[0]) + len(xs[2]) == len(xs[1])
    has_proper_seqs = all(map(is_ab_seq, xs))
    if not has_proper_ab_len or not has_proper_seqs:
        return False

    ys = x.split('ab')
    return len(ys) == 2 and len(ys[0]) % 2 == 0 and len(ys[1]) % 2 == 0

### Matematyka dyskretna
#TODO

### Metody numeryczne

#### Zadanie 1

* Zadanie dobrze uwarunkowane - to zadanie, mała względna zmiana danych nie powoduje dużej, względnej zmiany wyniku.
* Zadanie **źle** uwarunkowane - jeżeli mała, względna zmiana danych powoduje dużą, względną zmianę wyniku.
* Algorytm numerycznie poprawny - Jeśli wynik działania algorytmu może być zinterpretowany jako mało zaburzony wynik dokładny dla mało zaburzonych danych - algorytm wtedy nazywamy numerycznie poprawnym.

Odp: Otrzymany w ten sposób wynik jest wiarygodny, co więcej jest to jedyna możliwa gwarancja otrzymania poprawnego wyniku przy pomocy obliczeń komputera, gdyż dzięki numerycznie stablinemu algorytmowi mamy pewność, że nie kumulujemy dużego błędu, a przez dobre uwarunkowanie zadania, mamy gwarancję, że drobne zmiany danych wejściowych nie zaburzą nam jakości wyniku.

**JUST IN CASE**: jak obliczyć wskaźnik uwarunkowania zadania oraz przykłady zadań źle uwarunkowanych.

#### Zadanie 2


Algorytm bisekcji:
Rekurencyjnie konstruujemy taki ciąg przedziałów:

* $I_k = [a_k, b_k]$, (k=0,1,...)
że: W $I_0$ zawiera się $I_1$, w $I_1$ zawiera się $I_2$,..., itd.
oraz A - czyli nasze miejsce zerowe zawiera się w $I_k$ (k=0,1,...).

* Wyznaczamy środek przedziału $I_k: m_{(k+1)} = \frac{a_k + b_k}{2}$

* Jeśli $f(m_{(k+1)}) = 0$ to $A = m_{(k+1)}$ SUKCES!
* W przeciwnym razie:

$I_{(k+1)} = [a_{(k+1)}, b_{(k+1)}]$ i:
* Jeśli $f(m_{(k+1)})$ > 0 to $[a_k, m_{(k+1)}]$
* Jeśli $f(m_{(k+1)})$ < 0 to $[m_{(k+1)}, b]$

**Czyli podsumowując:**
Szukamy środków przedziałów i sprawdzamy czy to jest miejsce zerowe, jeśli nie to sprawdzamy czy miejsce zerowe leży po prawej, czy po lewej stronie środku przedziału i sprawdzamy tę strefę dzieląc ją rekurencyjnie na pół. Skąd wiemy po której stronie możemy znaleźć środek? Dzięki obserwacji zmiany znaku.

**Ile kroków metody?**

Znalezienie A z błędem względnym <= E należy wykonać
$$
\floor {log_2(\frac{b_0 - a_0}{2E})} + 1
$$
kroków metody bisekcji.

**JUST IN CASE**: 

#### Zadanie 3


Wiemy, że mamy dostęp do elementów $T_{0, m-1}, T_{1, m-2},...,T_{m-1,0}$. Aby mieć wszystkie potrzebne elementy potrzebujemy wyliczyć wyraz $T_{m,0}$. Bez problemu otrzymujemy go korzystając ze wzoru:
$$
T_{m,0} = \frac{4^m T_{m-1,1} - T_{m-1,0}}{4^m -1}
$$
A co z pierwszą wartością wiersza, czyli $T_{0,m}$? Korzystamy z własności, że $T_{0,m} = T_{2^m} = h_m \cdot \sum^{2^m}_{i=0}''f(x_i^{m})$ czyli złożonego wzoru trapezów.


### Algebra

#### Zadanie 1


**Macierz M jest dodatnio określona wtedy i tylko wtedy gdy przekształcenie (u,v) -> u^t * M * v jest iloczynem skalarynym**

Dodatniookreśloność Macierzy możemy badać z Kryterium Sylwestra, taka macierz musi być:
* symetryczna,
* wszystkie wyznaczniki |Mk| > 0, gdzie 

**Wracając do zadania:**
Jest symetryczna, teraz używamy sposobu (inne przykłady):


Jak będzie w tym przykładzie?
Odpowiedź:

Tutaj błąd 12 - 1= 11 > 0

#### Zadanie 2



#### Zadanie 3

## Egzamin czerwiec 2020

### Programowanie

#### Zadanie 1


a)
Tak należy:
S -> cSc -> ccScc -> ccXcc -> ccaaXcc -> ccaabbXcc -> **ccaabbcc**

b)

c)

Można skreślić produkcję X -> XX, bo produkcje X -> aaX i X -> bbX pokrywają wszystkie przypadki jej użycia.

d)

G_3:
X -> aaaaaaX, X -> bbbbbbX, X -> e, S -> X, S -> ccScc

e)

def is_in_lang(x):
    def foo(x: str, starting):
        if x == "":
            return True
        elif x.startswith("c") and starting:
            return x[:2] == "cc" and x[-2:] == "cc" and foo(x[2:-2], True)
        elif x.startswith("c") and not starting:
            return False
        elif x.startswith("a"):
            return x[:6] == "a" * 6 and foo(x[6:], True)
        elif x.startswith("b"):
            return x[:6] == "b" * 6 and foo(x[6:], True)
        else:
            return False

    return foo(x, True)

#### Zadanie 2

(W prologu więc jebać)

#### Zadanie 3

;; a)
(define (set? expr)
  (and 
    (list? expr)
    (= (length expr) 2)
    (eq? (first expr) 'set )
    (list? (second expr))))

(define (set-val s) (second expr))

(define (binop? expr symbol)
  (and 
    (list? expr)
    (eq? (length expr) 3)
    (eq? (first expr) symbol)
    (set? (second expr))
    (set? (third expr))))

(define (union? expr) (binop? expr 'union ))

(define (intersection? expr) (binop? expr 'intersection ))

(define (difference? expr) (binop? expr 'difference ))
     
(define (binop-left expr) (second expr))

(define (binop-right expr) (third expr))


;; b)
(define (eval-difference s1 s2)
  (define (diff s1 s2)
    (cond 
      [(empty? s1) s1]
      [(empty? s2) s1]
      [(member? (car s1) s2) (diff (cdr s1) (cdr s2))]
      [else (cons (car s1) (diff (cdr s1) s2))]))
  (list 'set (diff (set-val s1) (set-val s2))))


;; c)
(define (eval expr)
  (cond
    [(set? expr) expr]
    [(union? expr) (eval-union s1 s2)]
    [(intersection? expr) (eval-intersection s1 s2)]
    [(difference? expr) (eval-difference s1 s2)]
    [else #f]))

### Numerki

#### Zadanie 1


**Utrata cyfr znaczących** występuje wtedy, gdy odejmujemy liczby o zbliżonych wartościach. Wtedy duże części mantysy i cechy są takie same, x-y po normalizacji wpisywane są zera lub to co w pamięci żeby zapełnić puste miejsca.


Bo teraz dla x<0 będziemy mieć dodawanie.

#### Zadanie 2

https://drive.google.com/drive/u/0/folders/1Hv2crYWNdQAfGp2cA8yMcHFV-n05rPax
:arrow_up:
wykład 4., rozdział 2.2


<!--  -->


#### Zadanie 3


Można posłużyć się metodą faktoryzacji, o złożoności $O(n^3)$.


### Algebra

#### Zadanie 1


**Rząd macierzy** to wymiar przestrzeni generowanej przez kolumny tej macierzy (traktowanych jako wektory w $F^n$ (F to po prostu oznaczenie ciała)). Oznaczamy go przez rk(M).

**kombinacja liniowa** Dla wektorów v1, v2, . . . , vk ich kombinacja liniowa to dowolny wektor postaci $\sum αivi$ dla i=1,. . .,k, gdzie α1, . . . , αk jest ciągiem skalarów z ciała F.

**na chłopski rozum:** kombinacja liniowa wektorów to po prostu jakiś wektor, który jest sumą wektorów z danej przestrzeni pomnożonych przez skalary

**obraz** ogólnie jeśli mowa o obrazie to zazwyczaj mówimy o przekształceniu liniowym. Takie przekształcenie można opisać macierzą i będzie wtedy obraz macierzy. Definicja obrazu to: **Obraz przekształcenia Im(F) = {u : ∃vF(v) = u}** czyli będą to takie wektory u, które mają swoje odzwierciedlenie w macierzy F, a dokładnie są w przestrzeni rozpinanej przez macierz F.


#### Zadanie 2


Żeby dowieść, że $\phi$ jest *izomorfizmem* trzeba pokazać, że:
1. $\phi$ jest HOMOMORFIZMEM
* **homomorfizm**: $\phi$: G -> H, gdy zachowuje działania grupowe tj. $\phi$(ab) = $\phi$(a) * $\phi$(b)
2. $\phi$ jest BIJEKCJĄ -> trzeba pokazać, że $\phi$ jest "na" oraz różnowartościowa, czyli:
* RÓŻNOWARTOŚCIOWA
$\phi$(a) = $\phi$(b) $\Rightarrow$ a = b
* 'NA'
$\forall$a$\in$ G $\exists$ b$\in$ G : $\phi$(b) = a

##### Ważne definicje, z których skorzystano w rozwiązaniu:
* **element odwrotny**: $\forall g$$\in$ G $\exists g^-1$ : g$^-1$ * g = g * g$^-1$ = e
* **element neutralny**: $\forall g$$\in$ G : g *e = e * g = g

Gdy to pokażemy będziemy wiedzieć, że $\phi$ jest izomorfizmem.

**UWAGA** istotne jest, że działanie $\phi$ nie jest przemienne $\Rightarrow$ nie można sobie przestawiać literek. Gdyby działanie było przemienne grupa G byłaby tzw. *grupą abelową*.


### Metody programowania

#### Zadanie 1


1)

Niech liczby to będzie zbiór L, symbole to zbiór A.

S -> LX, S -> AZ, S -> (S), S -> S S
X -> LX, X -> empty, Z -> AZ, Z -> LZ, Z -> empty

2)

class Number:
    def __init__(self, number) -> None:
        self.number = number

    def get_val(self):
        return self.number


class Symbol(Number):
    pass



class S_expresion:
    def __init__(self, *args):
        self.elems = list(args)

    def get_val(self):
        return self.elems

3)

def convert_to_S(x: str):
    if x.isnumeric():
        return Number(x)
    elif x.startswith("("):
        if not x.endswith(")"):
            return False
        x = x[1:-1].split()
        return S_expresion([convert_to_S(elem) for elem in x])
    elif x[0].isnumeric() and not x[1:].isnumeric():
        return False
    else:
        return Symbol(x)

#### Zadanie 2


1) reprezentacja -- czyli jak te cosie co nas interesuja maja wygladac (czyli te definy do p i elem w naszym przypadku)
2) abstrakcja -- definiujemy jak ma wygladac nasz jezyk gdybysmy go wczytywali ze stringa
3) interpreter -- czyli to cos, gdzie robi sie (cond [(cos-z-abstrakcji? x) (ewaluacja x))

; 1
; paragraph
(define (make-p text) (list 'p text))

(define (p-text p) (second p))

(define (p? p)
  (and 
    (list? p)
    (eq? (length p) 2)
    (eq? (first p) 'p )))

; element
(define (make-elem tag children) (list 'elem tag children))

(define (elem-tag elem) (second elem))

(define (elem-children elem) (third elem))

(define (elem? elem)
  (and
    (list? elem)
    (eq? (length elem) 3)
    (eq? (first elem) 'elem )
    (andmap doc? (elem-children elem))))

(define (elem-tag? tag) (lambda (elem) (and (elem? elem) (eq? (elem-tag elem) tag))))

; document
(define (doc? d) (or (p? d) (elem? d)))

; 2
(define (p?? expr)
  (and 
    (list? expr)
    (eq? (length expr) 1)
    (eq? (car expr) 'p? )))

(define (elem-tag?? expr) 
  (and 
    (list? expr) 
    (eq? (length expr) 2) 
    (eq? (car expr) 'tag? )
    (string? (cadr expr))))

(define (in-children?? expr) 
  (and 
    (list? expr) 
    (eq? (length expr) 2) 
    (eq? (car expr) 'in-children? )))

(define (in-descendants?? expr) 
  (and 
    (list? expr) 
    (eq? (length expr) 2) 
    (eq? (car expr) 'in-descendants? )))

(define (subquery query) (cadr query))

(define (doc-children doc) (caddr doc))

(define (flatten-once lst)
  (apply append lst))

(define (doc-descendants doc)
  (if (p? doc)
    null
    (let* ([children (doc-children doc)]
          [descendants (flatten-once (map doc-descendants (doc-subquerable children)))])
      (append children descendants))))

(define (doc-subquerable docs) (filter (lambda (doc) (not (p? doc))) docs))

; sample queries
;; '(p?)
;; '(tag? "article")
;; '(in-children? (tag? "article")
;; '(in-children? (in-children? (tag? "article")))
;; '(in-descendants? (p?))'

(define (select-children expr children)
  ; (writeln children)
  (if (empty? children)
    children
    (let ([res (expr (car children))])
      (cond 
        [(eq? res #f) (select-children expr (cdr children))]
        [(eq? res #t) (cons (car children) (select-children expr (cdr children)))]
        [else (append res (select-children expr (cdr children)))]))))

(define (select query)
  (lambda (doc)
    (cond 
      [(p?? query) (p? doc)]
      [(elem-tag?? query) ((elem-tag? (cadr query)) doc)]
      [(in-children?? query) 
        (if (p? doc)
          #f
          (select-children (select (subquery query)) (doc-children doc)))]
      [(in-descendants?? query)
        (if (p? doc)
          #f
          (select-children (select (subquery query)) (doc-descendants doc)))])))

(define (assert actual expected) (if (eq? actual expected) #t (raise 'assert-failed #t)))

(define lorem (make-p "lorem-ipsum"))
; p tests
(define query1 '(p?))
(define doc1 lorem)
(assert ((select query1) doc1) #t)

; tag tests
(define query2 '(tag? "article"))
(define doc2 (make-elem "article" (list lorem lorem)))
(assert ((select query2) doc2) #t)

(define query3 '(tag? "article"))
(define doc3 (make-elem "heading" (list lorem lorem)))
(assert ((select query3) doc3) #f)

; children query tests
(define query4 '(in-children? (p?)))
(define doc4 (make-elem "heading" (list lorem lorem)))
(define res4 ((select query4) doc4))
(assert (length res4) 2)
(assert (length (filter p? res4)) 2)

(define query5 '(in-children? (tag? "article")))
(define subdoc5 (make-elem "article" (list lorem)))
(define doc5 (make-elem "heading" (list subdoc5 lorem)))
(define res5 ((select query5) doc5))
(assert (length res5) 1)
(assert (length (filter (elem-tag? "article") res5)) 1)

(define query6 '(in-children? (in-children? (p?))))
(define res6 ((select query6) doc5))
(assert (length res6) 1)
(assert (length (filter p? res6)) 1)

; descendants query tests
(assert (length (doc-descendants doc5)) 3)
(define x (doc-descendants doc5))

(define query7 '(in-descendants? (p?)))
(define res7 ((select query7) doc5))
(assert (length res7) 2)
(assert (length (filter p? res7)) 2)

(1 i 2 całkiem łatwe, ewaluator może nie tak bardzo)

### Dyskretna

## Egzamin luty 2020

### Programowanie

#### Zadanie 1

a)
Tak [1+1] * [0+1] należy do $L(G1)$. Dlaczgeo?
Odp: S -> S*S -> [S] * [S] -> [S+S] * [S+S] -> [1+1] * [0+1]

b)
Gramatyka $G_1$ nie jest jednoznaczna, gdyż za pomocą różnych drzew rozbiorów można dojść do tego samego wyrazu
Np. 1 + 0 * 1

Sposób 1: S -> S + S -> 1 + S * S -> 1 + 0 * 1
Sposób 2: S -> S * S -> S + S * 1 -> 1 + 0 * 1

W przypadku tej gramatyki brak jednoznaczności może prowadzić do błędnego nawiasowania wyrazu. (?)

c)
Lewa strona przecięcia tych dwóch zbiorów (o ile dobrze rozumiem) może generować dowolne ilości lewych nawiasów, zer prawych nawiasów i plusów. Dlatego z gramatyki $G_1$ wystarczy usunąć produkcje pozwalające nam na na tworzenie innych struktur - czyli S -> S * S oraz S -> 1.

Zatem oczekiwana gramatyka to:
S -> S + S, S -> [S], S -> 0

d)

def check_if_valid(x: str):
    if x == "":
        return True
    elif x[0] not in ["0", "[", "]"]: # pozbywamy się tych wyrazów, w których plus nie jest otoczony zerami
        return False
    elif x.startswith("["):
        return x.endswith("]") and check_if_valid(x[1:-1])
    elif x[0] == "0": # wywalamy od razu plusa za zerem, jeśli będziemy sprawdzać same "0", python dla x[2:] wyrzuci "" więc True 
        return check_if_valid(x[2:])

#### Zadanie 2


; a
(define (max-profit xs)
  (largest-difference xs))

(define (largest-difference xs)
  (define (find-largest-difference xs prev-max prev-largest)
    (if (empty? xs)
      prev-largest
      (let* ([current-max (if (> (first xs) prev-max) (first xs) prev-max)]
              [difference (- current-max (first xs))]
              [current-largest (if (> difference prev-largest) difference prev-largest)])
            (find-largest-difference (cdr xs) current-max current-largest))))
  (find-largest-difference (reverse xs) 0 0))

; b
(define (num-of-occurrences x xs)
  (define (walk xs n)
    (if (empty? xs) 
      n
      (walk (cdr xs) (if (= (car xs) x) (+ n 1) n))))
  (walk xs 0))

(define (sort-bits xs)
  (define (create-sorted-bit-list zeros ones)
    (cond 
      [(> zeros 0) (cons 0 (create-sorted-bit-list (- zeros 1) ones ))]
      [(> ones 0) (cons 1 (create-sorted-bit-list zeros (- ones 1)))]
      [else null]))
  (define zeros (num-of-occurrences 0 xs))
  (define ones (num-of-occurrences 1 xs))
  (create-sorted-bit-list zeros ones))

Nie było takich cudów na naszych metodach ;____;

#### Zadanie 3

; nie mozna nazwac tego eval, bo wtedy nie zadziala kek
(define (foo expr)
    (cond
      [(eq? expr '0 ) #f]
      [(eq? expr '1 ) #t]
      [(eq? (car expr) '+ ) (ormap foo (cdr expr))]
      [(eq? (car expr) '* ) (andmap foo (cdr expr))]))

(writeln (foo '(+ 0 1) ))

### Numerki

#### Zadanie 1


Oczywiście zakładamy, że funkcja nie jest liniowa ani kwadratowa, bo wtedy mamy jawne wzory -> $x = -\frac{b}{a}$ albo w przypadku kwadratowej -> $x_{1,2} = \frac{-b +- \sqrt{\Delta}}{2a}$.

Metoda bisekcji została opisana wyżej więc warto tutaj przywołać metodę Newtona albo metodę siecznych:

* Metoda Newtona:


* Metoda siecznych:


#### Zadanie 2


Zadanie iterpolacji wielomianowej Lagrange'a:
Dla danych, parami różnych liczb $x_0, x_1, ..., x_n$ oraz odpowiadających im wartościom $y_0, y_1, ..., y_n$ znaleźć wielomian $L_n \in \prod_n$ spełniający warunki: $L_n(x_k) = y_k (k=0,1,...,n)$.

Jak zrobić to optymalnie? Należy użyć tzw. postaci Newtona. Znajdujemy takie współczynniki $b_0, b_1, ..., b_n$, dla których:

$L_n(x) = b_0 + b_1(x-x_0) + b_2(x-x_0)(x-x_1)+..+b_n(x-x_0)...(x-x_n)$

gdzie $x_i$ to parami różne węzły. Można to wygodnie przeprowadzić za pomocą budowania tablicy ilorazów różnicowych.

#### Zadanie 3


Można na przykład użyć kwadratur i złożonego wzoru trapezów.

### Algebra

#### Zadanie 1


a)

Odp: $w(x)=(x-1)(x^4+x^3+1)$

b)

#### Zadanie 2


Tutaj link jak się to liczy: http://maciej.grzesiak.pracownik.put.poznan.pl/Prez-wektory-wlasne.pdf

https://blog.etrapez.pl/macierze/wartosci-i-wektory-wlasne-macierzy/

NIE SKRACAMY OPERACJAMI NA KOLUMNACH/WIERSZACH !!!

a)


b)
Krotności algebraiczne każdej z tych wartości wynoszą 1.

krotność geometryczna = 1
Te geometryczne są jakieś zjebane :(

### Dyskretna

## Egzamin 2019 czerwiec

### Numerki

#### Zadanie 1


Easy, było wyżej. Wystarczy opisać metodę.

#### Zadanie 2


a)
Definicja NIFS3:
Niech dane będą: $n \in N$, $x_0<x_1<...<x_n$ (węzły) oraz liczby $y_0,y_1,...,y_n$. Funkcje $S$ nazywamy NIFS3, jeśli spełnia warunki:
* $S(x_k) = y_k (k=0,1,...,n)$ - żeby była interpolacyjna
* $S, S', S'' \in C[x_0,x_n]$ - "gładkość"
* $S_{[x_{k-1}, x_k]} \in \prod_3 (k=1,2,...,n)$ - kawałkami wielomian stopnia $\leq3$
* $S''(x_0) = 0, S''(x_n) = 0$ - "naturalność"

b)
Rozwiązujemy układ równań, trochę jebania z tym jest ale łatwe.

#### Zadanie 3



Dane: n - liczba pkt. kontrolnych
tab - tablica wartości pkt. kontrolnych

Algorytm:
1. Wykonaj podstawienia:
$B = (1-u)^n$ #algorytm szbkiego potęgowania - $O(log n)$
wynik = B * tab[0]
$C = \frac{u}{(1-u)}$

2. Dla i = 1,2,...,n wykonuj:
$B = B * C * \frac{(n-i)}{(i+1)}$
wynik = wynik + tab[i] * B

3. Zwróć wynik.

### Algebra

#### Zadanie 1

Uwagi do zadania:
1. macierz jest dobrze obliczona, jak sie zapisze w odwrotnej kolejności to też będzie działać, to tylko macierz przekszałcenia liniowego.
2. Baza obrazu jest policzona dobrze, sprowadza się macierz przekształcenia Gaussem do postaci schodkowej i bierze niezależne wiersze.
3. Jądro jest policzone ppb. źle - wzięłam ten wektor, który oryginalnie przechodzi na zero. Trzeba tu pójść z df i rozwiązać układ równać Tx = 0, wtedy wyjdzie jądro, później z tego trzeba zrobić wektory niezależne i wyjdzie nam baza jądra.


#### Zadanie 2



#### Zadanie 3



### Dyskretna


## Egzamin luty 2019

### Numerki

#### Zadanie 1


Było już wyżej.

#### Zadanie 2

Definicja też pojawiła się wcześniej.


#### Zadanie 3


Było ostatnio podobne, tylko był podany wzór na wielomiany Beziera.

### Algebra

#### Zadanie 1


#### Zadanie 2


### Dyskretna


## Egzamin czerwiec 2018

### Programowanie

#### Zadanie 1
TODO

#### Zadanie 2
TODO

#### Zadanie 3
TODO

### Metody Numeryczne

#### Zadanie 1

łatwiejszy przykład niż e^$x^2$ xddd

#### Zadanie 2



#### Zadanie 3


**Uwaga** wniosek: gdy wyznaczymy postać schodkową macierzy dla kolumn, otrzymamy liczbę niezależnych wektorów kolumnowych i ta liczba to rząd macierzy A

**Uwaga 2** co gdy dla pewnego r: a _rr = 0?
Wtedy nasz algorytm zawodzi, kolejny krok nie może być wykonany, nie oznacza to jednak, że tego kroku nie da się wykonać.

Z numerycznego punktu widzenia powinno zależeć nam na tym, by elementy główne (m _r-1,i) co do modułu były <= 1 $\Rightarrow$ jest to **metoda eliminacji Gaussa z częsciowym wyborem elementów głównych**

Gdy zakładamy, że możemy przeprowadzać kolejne kroki, na pewno istnieje takie a _pp != 0, wtedy wystarczy zamienić ze sobą aktualnie rozpatrywaną kolumnę z kolumną p-tą (co nie zmienia rozwiązania), tak aby po przeindeksowaniu kolejny krok eliminacji Gaussa był możliwy. Przestawienie kolumny r-tej z p-tą kosztuje nas liniowo (po prostu robimy max na elemetntach danego kroku). Koszt zostaje zatem O(n$^3$).

### Algebra

#### Zadanie 1


#### Zadanie 2



## Egzamin czerwiec 2017

### Metody Numeryczne

#### Zadanie 1
Już było, ale napisałam ładnie, więc wstawiam.

#### Zadanie 2

#### Zadanie 3


### Algebra

#### Zadanie 1
znajdowanie pierwiastków równania 3st tu polega głównie na "zgadywaniu" -> próbujemy liczby od -5 do 5 i modlimy się żeby jakkolwiek to poszło xd

#### Zadanie 2


### Dyskretna

## Egzamin luty 2016

### Algebra

#### Zadanie 1

#### Zadanie 2
można to tak pokazać, pewnie trzebaby wymyślić jakiś wzorek na używając c_ij

okej tu lepiej

### Metody Numeryczne

#### Zadanie 1

#### Zadanie 2

#### Zadanie 3

## Egzamin wrzesień 2013

### Algebra

#### Zadanie 1

#### Zadanie 2

#### Zadanie 3
Sposób ze stacka:
Poniżej sposób od pana Jeżyka:


### Metody Numeryczne

ogólnie to to zadanie jest raczej bardzo trudne, ale wydaje mi się, że max co tu trzeba to trzeba napisać algorytm, który jest do mnożenia macierzy, pamiętać, że mnożenie macierzy nie jest przemienne i najpierw wymnożyć (A*x) a potem zrobić (Ax)*B, z tego tworzymy układ równań przyrównując do elementów macierzy jednostkowej.
Wstawiam szkic rozwiązania.

## Egzamin 06.02.2013

### Algebra



## Luźne zadanka

#### Zadanie 1