Zadania (Scheme)

1. Jakie są wartości następujących wyrażeń?
   
   

   ==> 10 
   
   
   ==> (+ 5 3 4) 
   
   
   ==> (- 9 1) 
   
   
   ==> (/ 6 2) 
   
   
   ==> (+ ( * 2 4) (- 4 6)) 
   
   
   ==> (let ((a 1) (b 2)) (+ a b (* a b))) 
   
   
   ==> a 
   
   
   ==> (define a 3) 
   
   
   ==> (define b (+ a 1)) 
   
   
   ==> (+ a b (* a b)) 
   
   
   ==> (= a b) 
   
   
   ==> (if (and (> b a) (< b (* a b))) 
           b 
           a) 
   
   
   ==> (cond ((= a 4) 6) 
             ((= b 4) (+ 6 7 a))
             (else    25))
   

2. Proszę napisać funkcje nwd a b oraz nww a b, których wartościami są największy wspólny dzielnik i najmniejsza wspólna wielokrotność.
   
   
3. Proszę napisać funkcję (new.< x y), (new.> x y), (new.= x y), (new.<= x y), (new.>= x y) oraz (new.<> x y). Należy z wbudowanych funkcji używać wyłącznie funckcję < (oraz predykaty oczywiście).
   
   
4. Proszę napisać funkcję (same-values? p1 p2 x y), której wartość jest #t, jeżeli (p1 x y) i (p2 x y) mają tą samą wartość i #f w przecziwnym przypadku.

   Przykłady: ==> (same-values? = new.= 3 1)
              #t
              ==> (same-values? < > 2 3)
              #f
   

5. Proszę napisać funkcje (odd? n) oraz (even? n), które sprawdzają, czy liczba naturalna n jest nieparzysta względnie parzysta. Należy używać wyłącznie funkcje #t, #f, zero? oraz "-1".
   
   
6. Proszę napisać rekurencyjną oraz iteracyną funkcję (fib n), która obliczy n-tą liczbę Fibonacci.
   
   
7. Potęgowanie b^e można szybko wykonać używając b^e = (b^(e/2))^2. Proszę napisać rekurencyjną oraz iteracyjną funkcję (exp b e) na podstawie tej właściwości. Używając model środowiska, proszę pokazywać, jak wyrażenie (exp 2 6) zostaje ewaluowane.
   
   
8. Niech będą dane następujące definicje funkcji.

   (define m 1)             (define n 1)
   (define (p m)            (define (q n)
      (pp 5))                  (define (qq x)
   (define (pp x)                 (+ x n))
      (+ x m))                 (qq 5))
   

   Jakie są wartości wyrazień (p 11) i (q 11)? Proszę wytłumaczyć wyniki używając model środowiska.
   
   
9. Proszę napisać funkcję (product term a next b) analogicznie do funkcji sum z wykładu. Proszę pokazywać, jak używając product można definiować funkcję silnia oraz przybliżać p na podstawie formuły   p/4 = 2 · 4 · 4 · 6 · 6 · 8 ··· / 3 · 3 · 5 · 5 · 7 · 7 ··· .
   
   
10. Proszę napisać funkcję (accumulate combiner null-value term a next b), która jest uogólnieniem funkcji sum i prod. Argumenty term, next, a i b zachowują to same znaczenie niż w funkcjach sum i prod. combiner jest dwuargumentową funkcją, która opisuja, jak (term a) zostaje dodane do akkumulacji dalszych termów. null-value jest wartością inicjalną do używania w końcowym przypadku.
    Proszę pokazywać, jak można definiować funkcje sum i prod używając accumulate.
    
    
11. Nawet funkcję accumulate można dalej uogólnić. Proszę napisać funkcję filter-accumulate, która ma dodatkowy argument pred. pred jest (jednoargumentowym) predykatem a filter-accumulate dodaje (term a) do wynika tylko, jeżeli a spełnie predykat pred.
    Używając filter-accumulate proszę obliczyć sumę kwadratów liczb pierwszych w interwale [a,b] oraz produkt wszystkich liczb naturalnych i mniejsze niż n, takie że nwd(i,n) = 1.
    
    
12. Niech będzie dana następująca definicja funkcji (comb f g).

    (define (comb f g)
       (lambda (x) (f (g x))))
    

    Używając model śdowiska, proszę pokazywać jak wyrażenie ((comb square double) 5) zostajy ewaluowane.
    
    
13. Proszę napisać funkcję (deriv f dx), którą wartość jest funkcją, która przybliża funkcję f' używając formułę

     Df(x) = (f(x+dx) - f(x)) / dx.
    

    Przykład:  ==> ((derive cube .001) 5)
               75.015
    

14. Proszę napisać następujące funkcje dla list:
    
    a) (append l m), która konkatenuje listy l i m.
    
    b) (reverse l), która obróci listę l.
    
    c) (last l), która znajduje ostatni element w liscie l.
    
    d) (delete x l), która skasuje element x z listy l.
    
    
15. a) Proszę napisać funkcję (square-list l), której wartość jest listą kwadratów elementów listy l.
    
    b) Proszę napisać funkcję (mapf f l), której wartością jest lista wartości f(e) dla wszystkich elementów e w liscie l.
    
    
16. Proszę zdefiniować funkcję (iter f n), której wartością jest funkcja fⁿ.
    
    
17. Używając funkcję fold proszę zdefiniować funkcje
    
    a) (prod l)
    
    b) (length l)
    
    c) (member x l)
    
    c) (delete l)
    
    d) (reverse l)
    
    
18. Proszę zdefiniować arytmetykę liczb wymiernich na podstawie liczb całkowitych.
    
    
19. Obiekty nie będące parami nazywają się atomy. Proszę napisać funkcję, która
    
    a) sprawdza, czy w liscie l znajdują się wyłącznie atomy.
    
    b) obliczy, ile jest atomów w liscie l.
    
    
20. Proszę napisać funkcję (member2 x l), któ sprawdza, czy gdzieś w liscie l znajduje się x.

    Przykłady: ==> (member2 'a '(b (c a) b))
               #t
               ==> (member2 '(a) '(b (c (a) d) e))
               #t
               ==> (member2 '(a) '(b c a))
               #f
    

21. Proszę powiększać funkcję deriv tak, żeby też mogła traktować termy typu u^n (na podstawie d(u^n) / dx = n * u^(n-1) * du / dx ).
    
    
22. Proszę implementować arytmetykę liczb zespolonych
    
    a) używając metodę "manifest types".
    
    b) używając metodę "message passing".
    
    
23. W Scheme też można pisać funkcje z dowolną ilością argumentów:

     (define (f x y z . l) (...))
    

    oznacza, że funkcja f ma conajmniej trzy argumenty (x,y i z). Jeżeli f dostaje więcej niż trzy argumenty, dodatkowe argumenty zostają zapisane do listy l .
    
    a) Proszę napisać funkcję plus, która podsumuje dowolną ilość liczb.
    
    b) Proszę napisać funkcję par dla dowolniej ilości (jednoargumentowych) funkcji f_i. Wartość funkcji par jest (jednoargumentową) funkcją, która dla argumenta x obliczy listę wszystkich
        wartości f_i(x).

      Przykłady: ==> ((par id square cube) 3)
                 (3 9 27) 
                 ==> ((par double double) 5)
                 (10 10)
    

24. Dlaczego wyrażenie if nie można sam definiować w następujący sposób?

    (define (new-if warunek alternatywa1 alternatywa2)
       (cond (warunek alternatywa1)
             (else    alternatywa2)))
    

25. Proszę napisać funkcję (ewal wyrażenie wartości), która oblicy wynik dla wyrażeń boolowskich. wyrażenie jest listą, której pierwszym elementem jest "typ" wyrażenia, a następne
    elementy tej listy, to podwyrażenia; na przykład lista '(and x (not y)) reprezentuje wyrażenie x∧¬y. wartości jest listą, w której znadują się wartości zmiennych.

    Przykłady: ==> (define w '((x . #f) (y . #t) (z . #f)))
               w
               ==> (ewal '(and y (not x)) w)
               #t
               ==> (ewal '(and y (and (not x) z))) w)
               #f
               ==> (ewal '(and y 1) w)
               #t
    

26. Niech a₁, a₂, ... będą wyrażenami. Reguła jest dana w formie {a_i1,...a_in} → a_i. Reguła jest faktem, jeżeli n = 0.
    Niech R będzie zbiorem reguł. Wyrażenie a jest prawdziwe w R, jeżeli
    
    (i) a jest faktem lub
    
    (ii) istnieje reguła {a_i1,...a_in} → a_i w R, taka że a_i = a oraz a_i1,... a_in są prawdziwe w R.
    
    Proszę napisać funkcję (valid a R), która sprawdza, czy wyrażenie a jest prawdziwe w R. Proszę użyć przy tym reprezentacje (fact a_i) dla faktu oraz (rule (a_i1 ... a_in) a_i)
    dla reguły {a_i1,...a_in} → a_i.

     Przykład:
     ==> (define R '((fact a1)
                     (rule (a1) a2)
                     (rule (a1 a5) a3)
                     (rule (a2) a5)
                     (rule (a2 a6) a4)))
     R
     ==> (valid 'a1 R)
     #t
     ==> (valid 'a3 R)
     #t
     ==> (valid 'a4 R)
     #f 
    

27. a) Proszę napisać funkcję (make-konto balance), która generuje nowe konto z balance złotymi. Na koncie mają być możliwie następujące operacje: Podjęcie, wpłacenie oraz
        informacje, ile jest na koncie.
    
    b) Proszę modifykować funkcję make-konto z cięci a), taka że ona generuje konta z hasłami, tzn. operacje zostają wykonywane tylko, jeżeli użytkownik używa prawdziwe hasło.

     Przykład: ==> (define konto (make-konto 100 'hasło))
               konto
               ==> ((konto 'hasło 'withdraw) 40)
               60
               ==> ((konto 'inne-hasło 'withdraw) 20)
               złe hasło
    

28. Proszę napisać funkcję (counting-version f), która ma jedonargumentową funkcję f jako argument. Wartość tej funkcji jest nową jednoargumentową funkcję, która liczy, ile razy
    funkcja f została używana.

     Przykład: ==> (define sq (counting-version square))
               sq
               ==> (sq 5)
               25
               ==> (sq 7)
               49
               ==> (sq 'ile)
               2
               ==> (sq 'reset)
               0
               ==> (sq 'ile)
               0
    

29. Proszę napisać destruktywną wersję append! funkcji append. Jakie są wartości następujących wyrażeń?

    ==> (define x '(a b)) 
    
    ==> (define y '(c d)) 
    
    ==> (append x y) 
    
    ==> (cdr x) 
    
    ==> (append! x y) 
    
    ==> (mcdr x) 
    

30. Co robi następująca funkcja?

     (define (coś x)
        (define (loop x y)
           (if (null? x)
               y
               (let ((temp (mcdr x)))
                  (set-mcdr! x y)
                  (loop temp x))))
        (loop x '()))
    

    Proszę narysować diagramy dla wyrażeń (define v '(a b c d)) i (define w (coś v))i po ich wykonywaniu.
    
    
31. Proszę napisać funkcję (count-boxes l), która obliczy, ile jest par w liscie l.

     Przykład:  ==> (define x '(a b c))
                x
                ==> (define z (cons x x))
                z
                ==> (count-boxes x)
                3
                ==> (count-boxes (append x x))
                6
                ==> (count-boxes z)
                4
    

32. Na wykładzie został podyskutowany simulator układów logicznych.
    
    a) Proszę napisać funkcję (or-gate o1 o2 output), która generuje bramkę or.
    
    b) Proszę napisać funkcję (full-adder a b c-in sum c-out), która generuje (pełny) sumator.
    
    c) Ripple-carry-adder, to układ, który sumuje dwie liczbe binarne a_n ... a₁ i b_n ... b₁. Wynik sumacji, to n bitów s_n ... s₁ oraz jeden bit c (carry).
        Proszę napisać funkcję (ripple-carry-adder A B S c), która generuje takiego sumatora. Argumenty A, B i S są listami kablów a_i, b_i i s_i, a c kablem carry.
        Proszę wygenerować ripple-carry-adder dla n = 4 bity i z nim obliczyć 1011 + 0011 oraz 1011 + 0110.