8063591496

Procedura sortowania przez wstawianie: insertsort([],[]).

insertsort([X|R], Sorted) insertsort(R, Sortedl), insert(X, Sortedl, Sorted).

insert(X, [Y|Rest], [Y|Restl]):- X>Y, !, insert (X, Rest, Restl). insert(X,List[X|List]).

insert(X, [], [X]). //jak to zmienia działanie? Co by było, jakby tego nie było?

Takie sortowanie jest nieefektywne, gdyż złożoność jest w tym przypadku kwadratowa, jak zdefiniować sortowanie tak, żeby było efektywne? Trzeba zdefiniować dodatkowy związek pomiędzy wynikiem pośrednim, a końcowym. Zmienną gromadzącą wyniki pośrednie nazywamy akumulatorem.

insertsortl([X|R], Acc, Sorted) insert(X, Acc, Accl), insertsortl(R, Accl, Sorted). insertsortl([], Acc, Acc). // przecież to już wynik końcowy, czyli Sorted jest po prostu akumulatorem...

Wywołanie: insertsortl([l,5,7,3], [], Wynik). // pusty akumulator

Procedura rekurencyjna tutaj wykorzystuje rekursję w ogonie (taił recursion). Dzięki temu silnik może to rozwinąć w iterację (wiemy, że nie będziemy korzystali z wyniku pośredniego, więc możemy tak sobie rozwinąć i pominąć).

10. Wykład 10:

Materiał do kolokwium / projektu:

-    uzgadnianie argumentów

-    nawroty (zapamiętywanie punktów wyboru)

-    sens logiczny

-    konsekwencje:

*    operacje na strukturach wbudowanych w interpreter

*    obiekty częściowo / (nie) ukonkretnione

*    konstrukcje generuj / testuj

-    procedury niedeterministyczne

-    generatory szablonów

-    odpowiednik konstrukcji if-then-else (oraz uogólnienie w postaci możliwości wycofania się z dowolnego poziomu)

Rozwiązania zadań można wysyłać mailem, będzie tydzień na wykonanie, ale pracy na 2 godziny (;)). Kolokwium 30 pkt.

Projekt - Planer Sekwencji Akcji:

Planer wybiera sekwencję akcji tak, aby osiągnąć pewien stan wyjściowy z wejściowego w świecie klocków, zwracając sekwencję akcji.

jednym z podejść analizy przestrzeni rozwiązań jest MEANS-ENDS ANALYSIS (analiza celów środków) - bardziej optymalna od zwykłego przeszukiwania. W metodzie tej startujemy od celów (np. zbioru położeń klocków). Zastanówmy się, co jest potrzebne, żeby któryś cel osiągnąć w jednym kroku (jednej akcji). Wybieramy arbitralnie któryś z nich. Tworzymy pewien stan pośredni, w którym cel (np. G2) jest osiągnięty, a pozostałe nie. Tworzymy stany pośrednie przed G2, które dzieli od G2 jeden krok. Bierzemy pod uwagę tylko te stany, które są możliwe z punktu widzenia dostępnych ruchów w przestrzeni. Zbiór stanów pośrednich staje się nowym zbiorem celów. Za każdym razem sprawdzamy, czy osiągnięty stan pośredni nie zawiera celów częściowo zawartych w stanie początkowym.