algorytmy i złożoność obliczeniowa (maszyna turinga, macierze, funkcje rekurencyjne)

0

Mam problem z zadaniami na studiach, niby mam jakieś materiały, ale ciężko mi z nich skorzystać. Wrzesień tuż, tuż a trzeba jakoś to ugryźć. Mamy przedmiot algorytmy i złożoność obliczeniowa, połowe testu ogarnąłem, ale drugiej na razie nie rozumiem. Są tu zadania typu.

Mamy jakąś funkcję rekurencyjną o jakimś wzorze, powiedzmy, że...:
f(n) = { n, gdzie n < 2
f(n-1) + f(n+1) + n^2 , gdzie n >= 2 }
I na przykładowe pytanie: ile razy funkcja będzie wołana do obliczenia f(8), podczas wywołania do obliczenia f(36).
Dla mniejszych ilości wywołań, mogę sobie narysować drzewko i odczytać z niego, ale jeśli mam do czynienia z dużymi wartościami, to takie drzewko rysowałbym przez cały czas testu... Musi istnieć jakiś prostrzy sposób, czy ktoś potrafi pomóc?

Następne: mam kilka macierzy (A1, ..., A5) o rozmiarach np. (kolejno) 3 x 4, 6 x 7, 7 x 4, itd. Następnie polecenie: Wyznacz najmniejszą liczbę mnożeń potrzebną do wyliczenia iloczynu A1A2...*A5 i podaj rozmieszczenie nawiasów realizujących tę liczbę mnożeń. Niby znam, (bynajmniej częsciowo) zasady mnożenia macierzy, jakoś bym te nawiasy rozmieścił, ale i tak różni się to nieco z odpowiedziami. Nie rozumiem tego do końca....

Na końcu zagadkowa maszyna turinga. Samo zadanie wygląda tak, jest dana maszyna Turinga M = (tu dane M), które się składa mi.in z K i z "Suma", następnie podane są wartości K oraz "Sumy" i program dany jest w tabeli. Następnie pytania: Podaj konfigurację maszyny M po trzech krokach wykonanych dla wejścia 0101:..., kolejne pytanie: Podaj konfigurację maszyny M w chwili zatrzymania dla tego samego wejścia. Dla mnie to czarna magia, nie kojarzę to z żadnym innym sposobem programowania, z którym gdzieś tam miałem do czynienia.

Podejrzewam, że te zadania wcale nie muszą być jakieś trudne, ale nie wiem jak do tego się zebrać. Proszę i dziękuję, za każdą pomoc, bo to co ja mam na ten moment, to jak dla profesora.

Pozdrawiam
Student zaoczny informatyki

1

Rekurencja, którą Podałeś akurat się nie kończy:); zaś ilość wywołań podobnej rekurencji będzie proporcjonalna do 2 do n. W temacie polecam CLRS, albo zajrzyj na kurs MIT:

Rekurencje sie, generalnie, rozwiązuje, a nie liczy wywołania.

Mnożenie macieży, te co Podałeś, znowu sie nie mnożą, liczba wierszy n w pierwszej musi być równa liczbie kolumn w drugiej, i zwyczajne mnożenie(tak jak to podają na algebrze) daje n ^ 3 mnożeń. tu o mnożeniu macierzy:

Maszyny Turinga, to polecam Spisera, "Introduction To the Theory Of Computation", lub bardzo dobry kurs na Udacity:
https://www.udacity.com/course/computability-complexity-algorithms--ud061
Lub ten wykład:

0
lion137 napisał(a):

Rekurencja, którą Podałeś akurat się nie kończy:); zaś ilość wywołań podobnej rekurencji będzie proporcjonalna do 2 do n. W temacie polecam CLRS, albo zajrzyj na kurs MIT:

Rekurencje sie, generalnie, rozwiązuje, a nie liczy wywołania.

Mnożenie macieży, te co Podałeś, znowu sie nie mnożą, liczba wierszy n w pierwszej musi być równa liczbie kolumn w drugiej, i zwyczajne mnożenie(tak jak to podają na algebrze) daje n ^ 3 mnożeń. tu o mnożeniu macierzy:

Maszyny Turinga, to polecam Spisera, "Introduction To the Theory Of Computation", lub bardzo dobry kurs na Udacity:
https://www.udacity.com/course/computability-complexity-algorithms--ud061
Lub ten wykład:

Jestem przy czwartej lekcji jeśli chodzi o kurs Udacity i na razie jest to najbardziej przystępny materiał, jaki miałem.

Co do zadania z rekurencją, to mam, taki przykład:
Do obliczenia wartości funkcji f : N0 -> N0,
f(n) = n n < 2
f(n - 2) + 2f(n - 1) + n^2 n >= 2
dysponujemy funkcją rekurencyjną opartą wprost na definicji. Ile razy funkcja będzie wołana do obliczenia f(2), podczas wywołania do obliczenia f(5). Odpowiedź to: 3 razy. I okej, ja mogę sobie narysować drzewko wywołań i to odczytać, ale przy większej ilości wywołań i innej funkcji, te drzewo, może być drzewem olbrzymem, że te rysowanie zamiast pomóc, to się jeszcze człowiek pomyli na tym.

Takie jest zadanie..., jest jakie jest, a ja muszę, to jakoś ogarnąć... Tylko inaczej jak przez rysowanie drzewka....

2

Akurat ta funkcja, którą Podałeś jest dość fartowna, bo będzie się wywoływała tyle razy ile rekurencja na ciąg Fibonacciego:). Niech len_fib(n) będzie ilością wywołań rekursywnej funkcji liczącej kolejną liczbę Fibonacciego - fib(n); to:
len_fib(n) = 2 * fib(n) - 1
Można to udowodnić indukcyjnie.

2

Zamiast drzewka narysuj sobie tabelkę i le razy wy woła sie dla n =1 , n=2 , n =3 id.
dla.
f(n) = n n < 2
f(n - 2) + 2f(n - 1) + n^2 n >= 2

szukamy dla np. 6
dla n <= 1 wy zwołuje się 1 raz na start.
dla n = 2 -> wywołujemy ją 1 raz na start i dla n=0 1 raz i n=1 kolejny 1 raz, razem 1+1+1=3,
dla n =3 wywołujemy ją raz 1 raz na start i dla n=1 1 raz i dla n =2 kolejne 3 razy , razem 1+1+3 =5;
dla n = 4 wywołujemy ją raz 1 raz na start i dla n=2 3 raz i dla n =4 kolejne 5 razy , razem 1+3+5 =9;
dla n = 5 wywołujemy ją raz 1 raz na start i dla n=3 5 raz i dla n =4 kolejne 9 razy , razem 1+5+9 =15;
dla n = 6 wywołujemy ją raz 1 raz na start i dla n=4 9 raz i dla n =5 kolejne 15 razy , razem 1+9+15 =25;

ponieważ to rekursja jest dość schematyczna to po chwili kolejne wyniki można zgadywać i jest na prawdę malutko liczenia :)

0

Dobra Panowie, pójdę za ciosem i wrzucę jeszcze zadanie z macierzy:

Dane są macierze A1, A2, A3, A4, A5 o rozmiarach odpowiednio 9x12, 12x14, 14x8, 8x11, 11x7. Wyznacz najmniejszą liczbę mnożeń potrzebnych do obliczenia iloczynu A1A2A3A4A5: ....... (<- tu odp.) i podaj rozmieszczenie nawiasów realizujące tę liczbę mnożeń: .......

Prosiłbym o rozwiązanie i dziękuję z góry.

0

Poczytaj o problemie nawiasowania ciągu macierzy. Jest na przykład na wikipedii.

Tutaj masz filmik:[

1 użytkowników online, w tym zalogowanych: 0, gości: 1