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