{"id":"informatyka-2015-maj-matura-rozszerzona/zad/1.2","paper_id":"informatyka-2015-maj-matura-rozszerzona","number":"1.2","points":3,"ptype":"open","subject":"informatyka","category":"matura","year":2015,"month":"maj","level":"rozszerzona","text":"Zadanie 1.2. (0-3)\nZastosowana strategia S w algorytmie jest optymalna, jeśli dla każdego programu\ntelewizyjnego wynik algorytmu (zbiór P) zawiera największą możliwą liczbę filmów, które\nmoże obejrzeć telewidz.\nUwaga:\nStrategia A nie jest optymalna, ponieważ telewidz może obejrzeć trzy filmy: film 1,\nfilm 4 oraz film 2.\nDla strategii A, B i C podaj w przygotowanych tabelach przykłady programów telewizyjnych,\nz emisją czterech filmów w dwóch stacjach, będące dowodami, że żadna z tych strategii nie\njest optymalna.\nDla każdej strategii i podanego dla niej programu telewizyjnego podaj wynik działania\nalgorytmu oraz przykład ilustrujący, że telewidz może obejrzeć więcej filmów, jeżeli nie\nużywa tej strategii.\nWskazówka. Podaj takie godziny emisji czterech filmów, aby telewidz był w stanie obejrzeć\nnp. trzy lub więcej filmów, podczas gdy zastosowanie algorytmu z odpowiednią strategią\ndaje rozwiązanie zawierające co najwyżej dwa filmy.\nDowód dla strategii A:\nTelewizja\n/ stacja\nFilm i godziny jego emisji\nCzas trwania\nemisji filmu\nTV1\nfilm 1 (od do ),\nfilm 2 (od do )\nTV2\nfilm 3 (od do ),\nfilm 4 (od do )\nWynik działania algorytmu przy zastosowaniu strategii A:\nP\nLiczniejszy zbiór filmów, które może obejrzeć widz:\nDowód dla strategii B:\nTelewizja\n/ stacja\nFilm i godziny jego emisji\nCzas trwania\nemisji filmu\nTV1\nfilm 1 (od do ),\nfilm 2 (od do )\nTV2\nfilm 3 (od do ),\nfilm 4 (od do )\nWynik działania algorytmu przy zastosowaniu strategii B:\nP\nLiczniejszy zbiór filmów, które może obejrzeć widz:\nMIN_1R\nDowód dla strategii C:\nTelewizja\n/ stacja\nFilm i godziny jego emisji\nCzas trwania\nemisji filmu\nTV1\nfilm 1 (od do ),\nfilm 2 (od do )\nTV2\nfilm 3 (od do ),\nfilm 4 (od do )\nWynik działania algorytmu przy zastosowaniu strategii C:\nP\nLiczniejszy zbiór filmów, które może obejrzeć widz:","answer":null,"answer_text":"Zadanie 1.2. (0-3)\nIII. Rozwiązywanie problemów\ni podejmowanie decyzji z wykorzystaniem\nkomputera, z zastosowaniem podejścia\nalgorytmicznego.\nZdający opracowuje i przeprowadza wszystkie etapy\nprowadzące do otrzymania poprawnego rozwiązania\nproblemu: od sformułowania specyfikacji problemu\npo testowa nie rozwiązania (5.7.).\nZdający stosuje podejście zachłanne\nw rozwiązywaniu problemów (5.10.).\nPoprawna odpowiedź\nStrategia A\nTelewizja/kanał\nFilm i godziny jego emisji\nTV1\nfilm 1 (od 10:00 do 12:00),\nfilm 2 (od 12:00 do 14:00)\nTV2\nfilm 3 (od 10:00 do 11:00),\nfilm 4 (od 11:00 do 12:00)\nWynik algorytmu przy zastosowaniu strategii A:\nP={ film 1, film 2}\nWiększy zbiór filmów, które może obejrzeć widz:\nP={ film 3, film 4, film 2 }\nStrategia B\nTelewizja/kanał\nFilm i godziny jego emisji\nTV1\nfilm 1 (od 11:30 do 12:30),\nfilm 2 (od 15:00 do 16:00)\nTV2\nfilm 3 (od 10:00 do 12:00),\nfilm 4 (od 12:00 do 14:00)\nWynik algorytmu przy zastosowaniu strategii B:\nP={ film 1, film 2}\nWiększy zbiór filmów, które może obejrzeć widz:\nP={ film 3, film 4, film 2 }\nStrategia C\nTelewizja/kanał\nFilm i godziny jego emisji\nTV1\nfilm 1 (od 09:00 do 14:00),\nfilm 2 (od 15:00 do 16:00)\nTV2\nfilm 3 (od 10:00 do 12:00),\nfilm 4 (od 12:00 do 14:00)\nWynik algorytmu przy zastosowaniu strategii C:\nP={ film 1, film 2}\nWiększy zbiór filmów, które może obejrzeć widz:\nP={ film 3, film 4, film 2 }\nSchemat punktowania\n3 p. - za podanie dla trzech strategii programu telewizyjnego, poprawnego dla nich wyniku algorytmu\noraz poprawnego większego zbioru filmów, który może obejrzeć.\n2 p. - za podanie dla dwóch strategii programu telewizyjnego, poprawnego dla nich wyniku algorytmu\noraz poprawnego większego zbioru filmów, który może obejrzeć.\n1 p. - za podanie dla jednej strategii programu telewizyjnego, poprawnego dla niej wyniku algorytmu\noraz poprawnego większego zbioru filmów, który może obejrzeć.\n0 p. - za odpowiedź niepełną lub błędną albo za brak odpowiedzi.\nUwaga: sprawdzenie poprawności odpowiedzi wymaga zasymulowania działania algorytmu na\npodanym przez ucznia przykładzie oraz sprawdzenia, czy podany większy zbiór jest poprawny.","solution":"## Poprawna odpowiedź\n\nKontrprzykłady (po jednym dla A, B, C):\n\n**Strategia A (najdłuższy, w razie remisu najwcześniej kończący) - nieoptymalna:**\n\n| Telewizja | Filmy |\n| TV1 | film 1: 10:00-12:00; film 2: 12:00-14:00 |\n| TV2 | film 3: 10:00-11:00; film 4: 11:00-12:00 |\n\n- Wynik strategii A: P = **{film 1, film 2}** (2 filmy - film 1 najdłuższy 2h, koliduje z 3 i 4; potem film 2).\n- Większy zbiór: **{film 3, film 4, film 2}** (3 filmy).\n\n**Strategia B (najkrótszy, w razie remisu najwcześniej kończący) - nieoptymalna:**\n\n| Telewizja | Filmy |\n| TV1 | film 1: 11:30-12:30; film 2: 15:00-16:00 |\n| TV2 | film 3: 10:00-12:00; film 4: 12:00-14:00 |\n\n- Wynik strategii B: P = **{film 1, film 2}** (film 1 najkrótszy 1h, koliduje z 3 i 4; potem film 2 też 1h).\n- Większy zbiór: **{film 3, film 4, film 2}** (3 filmy).\n\n**Strategia C (najwcześniej zaczynający, w razie remisu najwcześniej kończący) - nieoptymalna:**\n\n| Telewizja | Filmy |\n| TV1 | film 1: 09:00-14:00; film 2: 15:00-16:00 |\n| TV2 | film 3: 10:00-12:00; film 4: 12:00-14:00 |\n\n- Wynik strategii C: P = **{film 1, film 2}** (film 1 zaczyna najwcześniej 9:00, koliduje z 3 i 4; potem film 2).\n- Większy zbiór: **{film 3, film 4, film 2}** (3 filmy).\n\n## Sposób 1 - analiza dlaczego dana strategia zawodzi\n\n**Strategia A (najdłuższy):** wybiera długi film, który blokuje wiele krótkich. Kontrprzykład: 1 długi film przeciw 2 krótkim, które się nie nakładają.\n\n**Strategia B (najkrótszy):** krótki film znajdujący się \"w środku\" innego długiego blokuje konfigurację z większej liczby krótkich. Film 1 jest najkrótszy (1h) i wyklucza film 3 i film 4.\n\n**Strategia C (najwcześniej zaczynający):** wybiera film startujący najwcześniej, nawet jeśli długo trwa. Film 1 startuje o 9:00 i blokuje wszystko między 9 a 14.\n\n## Sposób 2 - uzasadnienie optymalności strategii D\n\nStrategia D (najwcześniej kończący, w razie remisu najpóźniej zaczynający) to klasyczny **algorytm zachłanny dla problemu wyboru aktywności** - twierdzenie z teorii algorytmów mówi, że ZAWSZE daje optymalną liczbę niekolidujących przedziałów.\n\n**Dowód intuicyjny:** Wybierając film kończący się najwcześniej, zostawiamy MAKSIMUM czasu pozostałego dla kolejnych filmów. Twierdzenie wymiany (exchange argument) pokazuje, że dowolne rozwiązanie optymalne można \"przekształcić\" na rozwiązanie zaczynające się od najwcześniej kończącego filmu, bez utraty liczebności.\n\n## Reference informatyczny - twierdzenie o optymalności greedy\n\n> Reference - Activity Selection Theorem:\n> - Strategia \"earliest deadline first\" (najwcześniej kończący) jest optymalna dla problemu wyboru najliczniejszego zbioru niekolidujących aktywności.\n> - Dowód: indukcja po liczbie aktywności + exchange argument.\n> - Strategie inne (najdłuższy / najkrótszy / najwcześniej zaczynający) są w ogólności NIEOPTYMALNE.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 1.2, max 3 pkt):\n> - **3 pkt** - kontrprzykłady dla 3 strategii (program TV + wynik algorytmu + większy zbiór)\n> - **2 pkt** - dla 2 strategii\n> - **1 pkt** - dla 1 strategii\n> - **0 pkt** - niepełna albo brak\n\n## Typowe pułapki\n\n- Podanie tylko programu TV bez wyniku działania algorytmu - nieuznaje się.\n- Podanie programu, w którym strategia daje 3 filmy - to NIE jest kontrprzykład (musi dać <3).\n- Pominięcie warunku \"4 filmy w 2 stacjach\".\n- Mylenie czasu zakończenia / czasu zaczęcia.\n\n## Złożoność obliczeniowa\n\n- Sprawdzenie kontrprzykładu: O(1) (mała liczba filmów).\n- Algorytm wyboru aktywności (greedy z sortowaniem): O(n log n).","image":"img/informatyka-2015-maj-matura-rozszerzona/zad-1.2.webp","solution_image":null,"topics":null,"page_from":4,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturazai","text_source":"ocr","source_label":"Informatyka · Matura · maj 2015 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Zadanie 1.2. (0-3)
Zastosowana strategia S w algorytmie jest optymalna, jeśli dla każdego programu
telewizyjnego wynik algorytmu (zbiór P) zawiera największą możliwą liczbę filmów, które
może obejrzeć telewidz.
Uwaga:
Strategia A nie jest optymalna, ponieważ telewidz może obejrzeć trzy filmy: film 1,
film 4 oraz film 2.
Dla strategii A, B i C podaj w przygotowanych tabelach przykłady programów telewizyjnych,
z emisją czterech filmów w dwóch stacjach, będące dowodami, że żadna z tych strategii nie
jest optymalna.
Dla każdej strategii i podanego dla niej programu telewizyjnego podaj wynik działania
algorytmu oraz przykład ilustrujący, że telewidz może obejrzeć więcej filmów, jeżeli nie
używa tej strategii.
Wskazówka. Podaj takie godziny emisji czterech filmów, aby telewidz był w stanie obejrzeć
np. trzy lub więcej filmów, podczas gdy zastosowanie algorytmu z odpowiednią strategią
daje rozwiązanie zawierające co najwyżej dwa filmy.
Dowód dla strategii A:
Telewizja
/ stacja
Film i godziny jego emisji
Czas trwania
emisji filmu
TV1
film 1 (od do ),
film 2 (od do )
TV2
film 3 (od do ),
film 4 (od do )
Wynik działania algorytmu przy zastosowaniu strategii A:
P
Liczniejszy zbiór filmów, które może obejrzeć widz:
Dowód dla strategii B:
Telewizja
/ stacja
Film i godziny jego emisji
Czas trwania
emisji filmu
TV1
film 1 (od do ),
film 2 (od do )
TV2
film 3 (od do ),
film 4 (od do )
Wynik działania algorytmu przy zastosowaniu strategii B:
P
Liczniejszy zbiór filmów, które może obejrzeć widz:
MIN_1R
Dowód dla strategii C:
Telewizja
/ stacja
Film i godziny jego emisji
Czas trwania
emisji filmu
TV1
film 1 (od do ),
film 2 (od do )
TV2
film 3 (od do ),
film 4 (od do )
Wynik działania algorytmu przy zastosowaniu strategii C:
P
Liczniejszy zbiór filmów, które może obejrzeć widz:

","answer_text_html":"

Zadanie 1.2. (0-3)
III. Rozwiązywanie problemów
i podejmowanie decyzji z wykorzystaniem
komputera, z zastosowaniem podejścia
algorytmicznego.
Zdający opracowuje i przeprowadza wszystkie etapy
prowadzące do otrzymania poprawnego rozwiązania
problemu: od sformułowania specyfikacji problemu
po testowa nie rozwiązania (5.7.).
Zdający stosuje podejście zachłanne
w rozwiązywaniu problemów (5.10.).
Poprawna odpowiedź
Strategia A
Telewizja/kanał
Film i godziny jego emisji
TV1
film 1 (od 10:00 do 12:00),
film 2 (od 12:00 do 14:00)
TV2
film 3 (od 10:00 do 11:00),
film 4 (od 11:00 do 12:00)
Wynik algorytmu przy zastosowaniu strategii A:
P={ film 1, film 2}
Większy zbiór filmów, które może obejrzeć widz:
P={ film 3, film 4, film 2 }
Strategia B
Telewizja/kanał
Film i godziny jego emisji
TV1
film 1 (od 11:30 do 12:30),
film 2 (od 15:00 do 16:00)
TV2
film 3 (od 10:00 do 12:00),
film 4 (od 12:00 do 14:00)
Wynik algorytmu przy zastosowaniu strategii B:
P={ film 1, film 2}
Większy zbiór filmów, które może obejrzeć widz:
P={ film 3, film 4, film 2 }
Strategia C
Telewizja/kanał
Film i godziny jego emisji
TV1
film 1 (od 09:00 do 14:00),
film 2 (od 15:00 do 16:00)
TV2
film 3 (od 10:00 do 12:00),
film 4 (od 12:00 do 14:00)
Wynik algorytmu przy zastosowaniu strategii C:
P={ film 1, film 2}
Większy zbiór filmów, które może obejrzeć widz:
P={ film 3, film 4, film 2 }
Schemat punktowania
3 p. - za podanie dla trzech strategii programu telewizyjnego, poprawnego dla nich wyniku algorytmu
oraz poprawnego większego zbioru filmów, który może obejrzeć.
2 p. - za podanie dla dwóch strategii programu telewizyjnego, poprawnego dla nich wyniku algorytmu
oraz poprawnego większego zbioru filmów, który może obejrzeć.
1 p. - za podanie dla jednej strategii programu telewizyjnego, poprawnego dla niej wyniku algorytmu
oraz poprawnego większego zbioru filmów, który może obejrzeć.
0 p. - za odpowiedź niepełną lub błędną albo za brak odpowiedzi.
Uwaga: sprawdzenie poprawności odpowiedzi wymaga zasymulowania działania algorytmu na
podanym przez ucznia przykładzie oraz sprawdzenia, czy podany większy zbiór jest poprawny.

","solutions":[{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"

Poprawna odpowiedź

\n

Kontrprzykłady (po jednym dla A, B, C):

\n

Strategia A (najdłuższy, w razie remisu najwcześniej kończący) - nieoptymalna:

\n

| Telewizja | Filmy |
| TV1 | film 1: 10:00-12:00; film 2: 12:00-14:00 |
| TV2 | film 3: 10:00-11:00; film 4: 11:00-12:00 |

\n\n

Strategia B (najkrótszy, w razie remisu najwcześniej kończący) - nieoptymalna:

\n

| Telewizja | Filmy |
| TV1 | film 1: 11:30-12:30; film 2: 15:00-16:00 |
| TV2 | film 3: 10:00-12:00; film 4: 12:00-14:00 |

\n\n

Strategia C (najwcześniej zaczynający, w razie remisu najwcześniej kończący) - nieoptymalna:

\n

| Telewizja | Filmy |
| TV1 | film 1: 09:00-14:00; film 2: 15:00-16:00 |
| TV2 | film 3: 10:00-12:00; film 4: 12:00-14:00 |

\n\n

Sposób 1 - analiza dlaczego dana strategia zawodzi

\n

Strategia A (najdłuższy): wybiera długi film, który blokuje wiele krótkich. Kontrprzykład: 1 długi film przeciw 2 krótkim, które się nie nakładają.

\n

Strategia B (najkrótszy): krótki film znajdujący się "w środku" innego długiego blokuje konfigurację z większej liczby krótkich. Film 1 jest najkrótszy (1h) i wyklucza film 3 i film 4.

\n

Strategia C (najwcześniej zaczynający): wybiera film startujący najwcześniej, nawet jeśli długo trwa. Film 1 startuje o 9:00 i blokuje wszystko między 9 a 14.

\n

Sposób 2 - uzasadnienie optymalności strategii D

\n

Strategia D (najwcześniej kończący, w razie remisu najpóźniej zaczynający) to klasyczny algorytm zachłanny dla problemu wyboru aktywności - twierdzenie z teorii algorytmów mówi, że ZAWSZE daje optymalną liczbę niekolidujących przedziałów.

\n

Dowód intuicyjny: Wybierając film kończący się najwcześniej, zostawiamy MAKSIMUM czasu pozostałego dla kolejnych filmów. Twierdzenie wymiany (exchange argument) pokazuje, że dowolne rozwiązanie optymalne można "przekształcić" na rozwiązanie zaczynające się od najwcześniej kończącego filmu, bez utraty liczebności.

\n

Reference informatyczny - twierdzenie o optymalności greedy

\n
Reference - Activity Selection Theorem:
- Strategia "earliest deadline first" (najwcześniej kończący) jest optymalna dla problemu wyboru najliczniejszego zbioru niekolidujących aktywności.
- Dowód: indukcja po liczbie aktywności + exchange argument.
- Strategie inne (najdłuższy / najkrótszy / najwcześniej zaczynający) są w ogólności NIEOPTYMALNE.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 1.2, max 3 pkt):
- 3 pkt - kontrprzykłady dla 3 strategii (program TV + wynik algorytmu + większy zbiór)
- 2 pkt - dla 2 strategii
- 1 pkt - dla 1 strategii
- 0 pkt - niepełna albo brak
\n

Typowe pułapki

\n\n

Złożoność obliczeniowa

\n"}]}