Wykład drugi

Question 1

Co to krzywa Hilberta n-tego rzędu?

Answer 1

jest złożona z 4 krzywych rzedu n-1, zmniejszonych dwukrotnie i odpowiednio obróconych, Krzywa H_1 może być traktorwana jako złożenie czterych pustych krzywych H_0 powiązanych trzema odcinkami

Question 2

Algotytm z powracaniem co to?

Answer 2

jest to ogólna techika algorytmiczna, wykorzystująca rekurencje, która polega na
rozwiązywaniu problemu obliczeniowego w następujący sposób:
1. Stopniowo budujemy rozwiązanie problemy sprawdzając czy aktualna kombinacja jest rozwiązanie danego problemu.
2. Jeśli dana kombinacja nie jest dopuszczalna lub nie jest rozwiązaniem algotyrm powraca do stanu, w którym może wygenerować innego kandydata i stopniowo nuduje dalej.
3. Jeśli dana kombinacja jest rozwiązaniem problemu algorytmu konczy działanie.

Question 3

Przykłady algorytmów z powracaniem?

Answer 3

1.problem ośmiu hetmanów
2.problem trwałego małzeństwa
3.problem znalezienia cyklu Hamiltona w grafie

Question 4

Czym są problemy kombinatoryczne?

Answer 4

jest opisany za pomocą skończonego zbioru parametrów wejściowych oraz warunków jakie mają spełniać dane wyjściowe

Question 5

Na jakie porblemy możemy podzielić problemy kombinatoryczne?

Answer 5

• decyzyjne = definiuje się jako skończony zbiór parametrów, które nie muszą mieć nadanych wartości oraz pytanie na które odpowiedz brzmi tak lub nie.
• optymalizacyjne = to maksymalizacja lub minimalizacja określonej funckji celu związanej z danym problem
  kombinatorycznym.
• przeszukiwania = wymaga natomiast kompletnego rozwiązania lub odpowiedzi nie jeśli takie rozwiązanie nie istnieje

Question 6

Przykład problemów decyzyjnych?

Answer 6

1. problem decyzyjny 𝚷
2. problem plecakowy

Question 7

Jakie mamy reguły kodowanie?

Answer 7

• reguła kodowania binarnego: posiada alfabet czteroliterowy = {0,1, ,.}.
• reguła kodowania jedynkowego: posiada alfabet trzyliterowy = {1, ,.}.

Question 8

Którą metodę należy odrzucic i dlaczego?

Answer 8

Jednak regułę jedynkową należy odrzucić bo powoduje nadmiarowy wzrost rozmiaru kodowanej instancji w stosunku
do każdej innej reguły kodowania.

Question 9

Rodzaje błedów w programach?

Answer 9

• językowe = wynikające ze złego użycia składni języka. Stosunkowo łatwo wykrywa je kompilator.

-logiczne = to złe użycie języka, nie zrozumienie jego semantyki(znaczenia). Prowadzi do budowy programu poprawnego składniowo ale nie wykonującego zadanego algorytmu.

-algorytmiczne = błedny jest sam algorytm, nie rozwiązuje on zadanego problemu algorytmicznego

Question 10

Jak dowiezć całkowitej poprawności algorytmu?

Answer 10

-metoda niezmienników Floyda = służy do wykazania częściowej poprawności algorytmu. Wykazuje się w niej ze pewne niepoządane sytuacje nie mogą wystąpić