Zadanie 1.1. (0-2)
Dla
podanego
programu
telewizyjnego
podaj
wyniki
wykonywania
algorytmu
po zastosowaniu strategii B, C i D:
Strategia S
Zawartość zbioru P po zakończeniu wykonywania algorytmu
B
C
D
Miejsce na obliczenia.
Wypełnia
egzaminator
Nr zadania
1.1.
Maks. liczba pkt.
2
Uzyskana liczba pkt.
MIN_1R
Zadanie 1.1. (0-2)
Wymagania ogólne
Wymagania szczegółowe
III. Rozwiązywanie problemów
i podejmowanie decyzji z wykorzystaniem
komputera, z zastosowaniem podejścia
algorytmicznego.
Zdający stosuje podejście algorytmiczne
do rozwiązywania problemu (5.2.).
Zdający opracowuje i przeprowadza wszystkie etapy
prowadzące do otrzymania poprawnego rozwiązania
problemu: od sformułowania specyfikacji problemu
po testowanie rozwiązania (5.7.).
Poprawna odpowiedź
strategia B: P={ film 5, film 2 }
strategia C: P={ film 1, film 4, film 2 }
strategia D: P={ film 1, film 4, film 2 }
Schemat punktowania
2 p. - za podanie poprawnych odpowiedzi dla trzech strategii.
1 p. - za podanie poprawnych odpowiedzi dla dwóch strategii.
0 p. - za odpowiedź niepełną lub błędną albo za brak odpowiedzi.
| Strategia | Zbiór P |
| B (najkrótszy, najwcześniej kończący) | {film 5, film 2} |
| C (najwcześniej zaczynający się, najwcześniej kończący) | {film 1, film 4, film 2} |
| D (najwcześniej kończący, najpóźniej zaczynający) | {film 1, film 4, film 2} |
Lista filmów:
\nStrategia B - najkrótszy, w razie remisu najwcześniej kończący
\nStrategia C - najwcześniej zaczynający się, najwcześniej kończący
\nStrategia D - najwcześniej kończący, w razie remisu najpóźniej zaczynający
\nNajwcześniej kończy film 1 (12:00). Dodaj. Usuń kolidujące: film 3 (11-16 koliduje), film 5 (11:30-12:30 koliduje).
\n```python
filmy = {
'film 1': (9.0, 12.0),
'film 2': (15.0, 17.0),
'film 3': (11.0, 16.0),
'film 4': (12.0, 14.0),
'film 5': (11.5, 12.5),
}
def koliduje(a, b):
s1, e1 = a; s2, e2 = b
return s1 < e2 and s2 < e1
def algorytm(filmy, klucz):
T = dict(filmy)
P = []
while T:
nazwa = min(T, key=lambda x: klucz(x, T[x]))
P.append(nazwa)
wybrany = T.pop(nazwa)
T = {n: t for n, t in T.items() if not koliduje(t, wybrany)}
return P
klucz_B = lambda n, t: (t[1] - t[0], t[1])
\nklucz_C = lambda n, t: (t[0], t[1])
\nklucz_D = lambda n, t: (t[1], -t[0])
\nprint('B:', algorytm(filmy, klucz_B))
print('C:', algorytm(filmy, klucz_C))
print('D:', algorytm(filmy, klucz_D))
Wynik: B = ['film 5', 'film 2'], C = ['film 1', 'film 4', 'film 2'], D = ['film 1', 'film 4', 'film 2'].
\nReference - Activity Selection Problem:\n
- Klasyczny problem: dany zbiór przedziałów, wybierz najwięcej niekolidujących.
- Optymalna strategia zachłanna: sortuj wg czasu zakończenia rosnąco, bierz pierwszy, usuń kolidujące, powtarzaj. To jest strategia D.
- Złożoność: O(n log n) (sortowanie) + O(n) (wybór).
- Strategie A, B, C nie są optymalne - łatwo skonstruować kontrprzykład.
Klucz CKE (zadanie 1.1, max 2 pkt):\n
- 2 pkt - poprawne odpowiedzi dla trzech strategii
- 1 pkt - poprawne odpowiedzi dla dwóch strategii
- 0 pkt - niepełna lub błędna albo brak