Lekcja 12,13,14,15
Embedded Files
Cele lekcji:
Dowiesz się czym są problemy optymalizacyjne.
Zrozumiesz, na czym polega pojęcie zachłanne stosowane do rozwiązywania problemów.
Zaprogramujesz algorytmy zachłanne znajdujące optymalne rozwiązania problemu wydawania reszty oraz problemu kinomana.
Przekonasz się, jak ważny jest dobór odpowiedniego typu danych w rozwiązywaniu problemów, aby uniknąć konsekwencji błędów przybliżeń.
Nauczysz się stosować listy równoległe jako struktury danych.
Zagadnienia:
Problemy optymalizacyjne. Algorytmy zachłanne.
Listy równolegle
Problemy optymalizacyjne to takie, które wymagają znalezienia jak najlepszego rozwiązania spełniającego określone kryterium (wymaganie).
Jeżeli potrafisz udowodnić, że znalezione rozwiązanie problemu jest najlepsze z możliwych, to nazywamy je rozwiązaniem optymalnym. Inaczej możemy mówić tylko o rozwiązaniu przybliżonym.
Przykładem Algorytmu zachłannego jest Algorytm Euklidesa. Wyznaczanie NWD(a,b)
Wycinanka Euklidesa
Dla liczb całkowitych a i b wyznaczenie NWD(a,b) jest równoważne znalezieniu największego kwadratu, którym można by wypełnić prostokąt o bokach długości a i b
Z różnych algorytmów wyznaczania NWD dwóch liczn tylko algorytm Euklidesa wykorzystuje podejście zachłanne.
Problem kolorowania mapy zwany również ubogiego kartografa.
Warto wiedzieć:
w 1853r. postawiono hipotezę, że 4 kolory zawsze wystarcza do pokolorowania każdej płaskiej mapy. Dowód sformułowano dopiero w 1976. Dotąd nie udało sie udowodnić tego twierdzenia bez użycia komputera.
Wydawanie reszty metodą zachłanną [149]
Dąży się do tego, aby liczba monet była możliwie jak najmniejsza.
Ćwiczenie 2 [149]
W pliku który otrzymasz od nauczyciela L12mapa.png , znajduje się mapa konturowa Polski z podziałem na województwa. Pokoloruj ją, korzystając z możliwie najmniejszej liczby kolorów tak dwa sąsiednie województwa miały różne kolory. Wyniki opublikuj w notatce na swojej witrynie.
Ćwiczenie 3 [151]
Wyobraź sobie że korzystasz z automatu na dworcu kolejowym. Z jakich monet składa się reszta, jeżeli automat wydaje ją możliwie najmniejsza ilością monet, a ty płacisz banknotem 10 zł za zakup:
a. Wody za 2,70zł
b. herbaty za 3,40zł
c. przekąski za 4,19zł
Zakładamy, że w automacie nie brakuje żadnych monet
Zagadnienia:
kod źródłowy wydawania reszty.
Błąd przybliżeń
Jak można ominąć błąd przybliżeń?
Ćwiczenie 4 [152]
Zapisz kod źródłowy "wydawania reszty" L13a.py i uruchom program. Sprawdź jego działanie dla różnych wartości reszty, w tym dla 7.30, 7.79, i 7.85.
Czy zauważyłeś coś ciekawego?
Ćwiczenie 5 [153]
W programie utworzonym w poprzednim ćwiczeniu usuń w kodzie drugą część warunku logicznego , tj. i<N. Plik zapisz pod nazwą L13b.py . Sprawdź działanie programu dla różnych wartości reszty w tym dla 7.30, 7.79 i 7.85. Co obserwujesz?
Ćwiczenie 6 [154]
Zapisz kod programu "wydawanie reszty 2" L13c.py Uruchom program dla kilku różnych kwot np. 7zł30gr, 7zł 75gr.
Zmodyfikuj kod programu tak, aby można było wprowadzać kwotę większą niż 10zł, a resztę można było wydawać z użyciem monet i banknotów.
Zagadnienia:
Problem kinomana
Kinoman chce zobaczyć tyle filmów ile tylko będzie możliwe.
Zakładamy, że:
Nie może on w w tej samej godzinie zakończyć seansu jednego filmu i rozpocząć drugiego.
Potrzebuje czas na przemieszczenie się.
Filmy ogląda w całości.
W jaki sposób powinien postępować aby obejrzeć ich jak najwięcej?
Harmonogram festiwalu filmowego
Aby wybrać możliwie najwięcej filmów, możemy postępować zachłannie według różnych kryteriów. oto niektóre z nich:
kryterium 1: filmy zaczynające się najwcześniej,
kryterium 2: filmy najkrótsze,
kryterium 3 filmy kończące się najwcześniej.
innym kryterium które można zastosować w problemie kinomana jest jak najmniejsza liczba konfliktów filmu z innymi filmami.
Można wykazać, że zachłanny wybór najwcześniej kończących sie filmów (kryterium 3) daje zawsze rozwiązanie optymalne.
Ćwiczenie 7 [156]
W pliku otrzymanym od nauczyciela (L14a.jpg) oznacz filmy które obejrzy kinoman, jeżeli zastosuje kryteria 2 oraz 3. Wyniki przedstaw na swojej witrynie.
Zagadnienia:
Listy równoległe
Ćwiczenie 8 [159]
Zapisz pełen kod źródłowy Problem kinomana i uruchom program.
Wyniki swojej pracy przedstaw na swojej Witrynie.
Podsumowanie:
Podsumowanie:
Problemy optymalizacyjne to problemy, w których szukamy rozwiązania jak najlepszego spełniającego określone kryterium.
Podejście zachłanne w rozwiązywaniu problemu polega na rozwiązywaniu szeregu decyzji, z których każda wydaje się najkorzystniejsza w danym momencie, bez analizowania jej wpływu na optymalność całego rozwiązania. Stosowanie tej strategii prowadzi czasami do optymalnego a czasami tylko do rozwiązania przybliżonego.
Problem wydawania reszty polega na przedstawieniu danej kwoty reszty za pomocą najmniejszej liiczby banknotów i monet. Aby rozwiązać ten problem metodą zachłanną, należy wybierać w danym kroku jak największy nominał nie większy od kwoty, która pozostała jeszcze do wydania .
Aby zapobiec kumulowaniu się błędów przybliżeń, należy unikać używania typu zmiennoprzecinkowego float.
Przykładowe wykonanie zadań do L14
Ćwiczenie 7 [156]
W pliku otrzymanym od nauczyciela (L14a.jpg) oznacz filmy które obejrzy kinoman, jeżeli zastosuje kryteria 2 oraz 3. Wyniki przedstaw na swojej witrynie.
Lekcja 14
Ćwiczenie 7 [156]
W pliku otrzymanym od nauczyciela (L14a.jpg) oznacz filmy które obejrzy kinoman, jeżeli zastosuje kryteria 2 oraz 3. Wyniki przedstaw na swojej witrynie.
wybrałem 4 filmy
wybrałem 5 filmów
kryterium wyboru filmów kończących się najwcześniej okazało się najlepsze
Page updated
Report abuse