Zaawansowane algorytmy i struktury danych/Ćwiczenia 12: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
 
Linia 1: Linia 1:
 
== Zadanie 1 ==
 
== Zadanie 1 ==
 
{{kotwica|zadanie 1|}}
 
{{kotwica|zadanie 1|}}
 
+
Pokaż, że procedura [[../Wykład 12#ZBIÓR-ODCINKÓW-SIĘ-PRZECINA|ZBIÓR-ODCINKÓW-SIĘ-PRZECINA]] działa poprawnie nawet wtedy gdy trzy lub więcej odcinków przecina się w tym samym punkcie.
 
 
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
+
Rozumowanie w takim przypadku jest analogiczne do rozumowania przeprowadzonego na wykładzie. Niech <math>p</math> będzie punktem przecięcia najbardziej na lewo oraz niech będzie to punkt przecięcia <math>k</math> odcinków. Zauważmy, że istnieje takie położenie miotły <math>x</math>, że te <math>k</math> odcinków będzie występowało kolejno w porządku <math><_x</math>. Zauważmy, że każda para tych punktów się przecina, a więc w momencie, w którym umieszczone one zostały na miotle w tej kolejności wykryte zostało ich przecięcie. 
 
</div>
 
</div>
 
</div>
 
</div>
Linia 12: Linia 11:
 
== Zadanie 2 ==
 
== Zadanie 2 ==
 
{{kotwica|zadanie 2|}}
 
{{kotwica|zadanie 2|}}
 
+
Pokaż, że procedura [[../Wykład 12#ZBIÓR-ODCINKÓW-SIĘ-PRZECINA|ZBIÓR-ODCINKÓW-SIĘ-PRZECINA]] działa poprawnie nawet wtedy gdy obecne są pionowe odcinki, a ich dolne końce traktujemy jako lewe końce, a górne końce jako prawe. Położenie odcinków w porządku na miotle wyznaczamy na podstawie współrzędnej <math>y</math> dolnego końca.
 
 
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
+
Zauważ, że przy takim traktowaniu końcy odcinków pionowych w trakcie działania procedury zostanie sprawdzone, czy odcinek przecina się z z najniższym odcinkiem leżącym ponad dolnym końcem. Taki test wystarczy do sprawdzenia czy odcinek pionowy przecina się z jakimkolwiek innym odcinkiem. Zostanie tez sprawdzone, czy odcinek przecina się z najwyższym odcinkiem leżącym poniżej dolnego końca, a to wystarczy do przetestowania przecinania się odcinków pionowych między sobą.
 
</div>
 
</div>
 
</div>
 
</div>
 
  
 
== Zadanie 3 ==
 
== Zadanie 3 ==
 
{{kotwica|zadanie 3|}}
 
{{kotwica|zadanie 3|}}
 
+
Masz dane dwa zbiory <math>n</math> punktów <math>P = \{p_1,\ldots,p_n\}</math> oraz <math>Q=\{q_1,\ldots,q_n\}</math>. Zakładamy, że w sumie tych zbiorów nie ma trzech współliniowych punktów. Pokaż, że można dobrać w pary punkty <math>P</math> do punktów w <math>Q</math> tak aby utworzone w ten sposób odcinki się nie przecinały. Zaproponuj algorytm wyznaczający takie parowanie.
 
 
 
 
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
+
Pokażemy teraz że istnieje taka para <math>(p,q)</math>, że po obydwu stronach prostej <math>p-q</math> występuje tyle samo punktów ze zbioru <math>P</math> co ze zbioru <math>Q</math>. Wybierzmy dowolny punkt <math>p \in P</math> i posortujmy pozostałe punkty z <math>P \cup Q</math> po współrzędnych polarnych względem tego punktu. Oznaczmy ten posortowany ciąg przez <math>s_1,\ldots,s_{2n}</math>. Oznaczmy przez <math>t_i</math> różnicę między liczbą punktów z <math>P</math> występujących po jednej ze stron prostej <math>p-s_i</math> oraz liczbą punktów z <math>Q</math> występujących po tej samej stronie prostek <math>p-s_i</math>. Zauważmy, że <math>|t_i - t_{i+1}| \le 1</math>, ponieważ przy zmianie prostej co najwyżej jeden punkt zmienia stronę. Zauważmy, że z tej dyskretnej równości wynika, że dla pewnego <math>i</math> musi zachodzić <math>t_i =0</math>. Takie <math>i</math> możemy znaleźć w czasie <math>O(n\log n)</math>. Mając taką prostą możemy rozbić problem na dwa mniejsze problemy. Ponieważ zagłębień tek rekursji będzie co najwyżej <math>O(n)</math>, to algorytm wyznaczania parowania punktów z <math>P</math> do punktów z <math>Q</math> działać będzie w czasie <math>O(n^2 \log n)</math>.
 
</div>
 
</div>
 
</div>
 
</div>

Aktualna wersja na dzień 16:25, 30 wrz 2006

Zadanie 1

Pokaż, że procedura ZBIÓR-ODCINKÓW-SIĘ-PRZECINA działa poprawnie nawet wtedy gdy trzy lub więcej odcinków przecina się w tym samym punkcie.

Rozwiązanie

Zadanie 2

Pokaż, że procedura ZBIÓR-ODCINKÓW-SIĘ-PRZECINA działa poprawnie nawet wtedy gdy obecne są pionowe odcinki, a ich dolne końce traktujemy jako lewe końce, a górne końce jako prawe. Położenie odcinków w porządku na miotle wyznaczamy na podstawie współrzędnej dolnego końca.

Rozwiązanie

Zadanie 3

Masz dane dwa zbiory punktów oraz . Zakładamy, że w sumie tych zbiorów nie ma trzech współliniowych punktów. Pokaż, że można dobrać w pary punkty do punktów w tak aby utworzone w ten sposób odcinki się nie przecinały. Zaproponuj algorytm wyznaczający takie parowanie.

Rozwiązanie