Jednotná státní zkouška analýza počítačových úloh 3.
Analýza úkolu 3 Jednotné státní zkoušky z informatiky 2017 z projektu demoverze. Jedná se o úkol základní úrovně obtížnosti. Přibližný čas na splnění úkolu jsou 3 minuty.
Testované obsahové prvky: schopnost prezentovat a číst data v různých typech informačních modelů (grafy, mapy, tabulky, grafy a vzorce).
Úkol 3:
Na obrázku vpravo je ve formě grafu znázorněna silniční mapa okresu N; Tabulka vlevo obsahuje informace o délce každé z těchto silnic (v kilometrech).
Vzhledem k tomu, že tabulka a diagram byly nakresleny nezávisle na sobě, číslování sídel v tabulce nijak nesouvisí s písmenným označením na grafu. Určete délku cesty z bodu B do bodu C. Zapište do odpovědi celé číslo - jak je uvedeno v tabulce.
Odpovědět: ________
Čára P5 musí odpovídat vrcholu, ze kterého vycházejí 4 oblouky.
Takový vrchol je V
P5 - B
Čára P6 musí odpovídat vrcholu, ze kterého vycházejí 2 oblouky.
Takový vrchol je A
P6 - A
Cesty z bodu A vedou do bodu B a bodu C.
Je zřejmé, že z bodu A do bodu B je délka 7 km, tedy do bodu B - 5 km.
To znamená, že přímka P1 odpovídá vrcholu B.
P1 - B
Úkol vyžaduje, abyste určili délku cesty z bodu B do bodu C.
Pomocí tabulky určíme, že cesta od B PROTI V rovná se 8 .
Pro efektivní přípravu v informatice je u každého úkolu uveden stručný teoretický materiál pro splnění úkolu. Bylo vybráno více než 10 školicích úkolů s analýzou a odpověďmi, které byly vyvinuty na základě demoverze z předchozích let.
Jednotná státní zkouška KIM z informatiky a ICT pro rok 2019 se nemění.
Oblasti, ve kterých budou znalosti testovány:
- Programování;
- Algoritmizace;
- nástroje ICT;
- Informační činnost;
- Informační procesy.
Nezbytné akce, když příprava:
- Opakování teoretického kurzu;
- Řešení testy v informatice online;
- Znalost programovacích jazyků;
- Zlepšit matematiku a matematickou logiku;
- K úspěchu při jednotné státní zkoušce nestačí používat širší škálu literatury – školního vzdělávacího programu.
Struktura zkoušky
Délka zkoušky je 3 hodiny 55 minut (255 minut), z toho hodinu a půl se doporučuje věnovat plnění úkolů první části KIM.
Úkoly na lístcích jsou rozděleny do bloků:
- Část 1- 23 úkolů s krátkou odpovědí.
- Část 2- 4 úkoly s podrobnými odpověďmi.
Z navržených 23 úloh první části zkouškové práce patří 12 do základní úrovně testování znalostí, 10 – do zvýšené složitosti, 1 – do vysoké úrovně složitosti. Tři úkoly druhé části jsou na vysoké úrovni složitosti, jedna je na vyšší úrovni.
Při rozhodování je nutné zaznamenat podrobnou odpověď (volná forma).
V některých úlohách je text podmínky prezentován v pěti programovacích jazycích najednou - pro pohodlí studentů.
Body za úkoly z informatiky
1 bod - za 1-23 úkolů
2 body - 25.
3 body - 24, 26.
4 body - 27.
Celkem: 35 bodů.
Pro vstup na střední technickou univerzitu musíte získat alespoň 62 bodů. Pro vstup na univerzitu hlavního města musí počet bodů odpovídat 85-95.
K úspěšnému napsání zkouškové práce je nutná jasná znalost teorie a konstantní praxe v řešeníúkoly.
Váš recept na úspěch
Práce + práce na chybách + pozorně si přečtěte otázku od začátku do konce, abyste se vyvarovali chyb = maximální počet bodů na Jednotné státní zkoušce z informatiky.
Počítačová věda. Jednotná státní zkouška
Úkol 3
Analýza typických úkolů:
Určete délku nejkratší cesty mezi body A a F za předpokladu, že můžete cestovat pouze po silnicích uvedených v tabulce.
Problém je vyřešen převedením tabulkového modelu na strom:
R 
Podívejme se na první řádek (sloupec) tabulky. Je zřejmé, že z bodu A se můžeme dostat do bodů B, C,D
,
F
. Dostaneme následující diagram:
R 
Podívejme se na druhý řádek (sloupec) tabulky: z bodu B se můžete dostat do bodu A (cesta AB je na diagramu již nakreslena a není třeba ji kreslit znovu, protože toto je cesta „zpět“ a taková trasa nebude nejkratší). Je tedy nutné umístit do diagramu jednu cestu (od B doD
, délka 5).
Analýzou 3. řádku (sloupce) tabulky přidáme do diagramu další cestu: z C doD délka 2.
Analýza 4 řádků (sloupců) tabulky přidává do našeho diagramu další dvě cesty (odD PROTIE AF ), protože silniceBD , CD , INZERÁT jsou již na diagramu přítomny. Od věciD na diagramu je nakresleno 3x, pak z každého boduD Pojďme dvěma způsoby:DE ADF . Pojďme na diagram
Podle řádku (sloupec) 5 tabulky vyneseme do diagramu cestuEF :
Podle schématu vypíšeme trasy od A doF a vypočítejte jejich délku:
AF – 14
ADF – 7+8=15
ADEF – 7+5+1=13
ACDF – 4+2 +8 =14
ACDEF – 4+2+5+1 = 12
ABDF – 3+5+8 = 16
ABDEF – 3+5+5+1 = 14
Nejkratší cesta je 12.
Mezi sídly A, B, C, D, E, F byly vybudovány silnice, jejichž délka je uvedena v tabulce. Absence čísla v tabulce znamená, že mezi body nevede žádná přímá cesta.
Kolik cest je z A do F, které procházejí pěti nebo více obydlenými oblastmi? Při výpočtu vezměte v úvahu body A a F. Nemůžete projít stejným kontrolním bodem dvakrát.
Stromový diagram sestavíme podobně jako č. 1. Rozdíl oproti předchozí úloze je v tom, že nás nezajímá délka tras a do diagramu vyneseme všechny body, kterých lze z tohoto bodu dosáhnout a které jsme předtím podél této větve nevykreslili:
Čtyři trasy (na schématu vyznačeny modře) se ukázaly jako slepá ulička, takže další pohyb po nich vede k opakované návštěvě bodů A resp.D . Zapisujeme si trasy vedoucí k boduF (na obrázku vyznačeno červeně) a spočítejte počet sídel, kterými každá trasa prochází:
AF – 2
ADF 3
ADEF 4
ACDF-4
ACDEF 5
ABDF 4
ABDEF – 5
Počet tras, které splňují podmínky problému, jsou 2.
Tabulka ukazuje náklady na přepravu mezi sousedními železničními stanicemi. Poskytněte schéma, které odpovídá tabulce.
4) 
Analýzou tabulky řádek po řádku (po sloupci) dostaneme: na diagramu by měly být 4 silnice: AB(4), AD (5), PŘED NAŠÍM LETOPOČTEM. (3), BD (6). Ze čtyř schémat tuto podmínku splňuje pouze jedno schéma (poslední). Odpověď: 4 schéma.
Na obrázku vpravo je znázorněna mapa okresu N ve formě grafu, tabulka obsahuje údaje o délkách těchto komunikací (v kilometrech).
Vzhledem k tomu, že tabulka a diagram byly nakresleny nezávisle na sobě, není číslování sídel v tabulce nijak spojeno s písmenným označením v grafu. Určete délku cesty z bodu B do bodu E. Zapište do odpovědi celé číslo - jak je uvedeno v tabulce.
Úkolem je zjistit shodu mezi číslováním sídel v grafu a v tabulce.
Rozeberme si graf: podle diagramu jsou 2 cesty do bodů A, B, D a K, 3 cesty do bodu D, 5 cest do C, 4 cesty do E. Porovnáním s tabulkou dostaneme: G je v tabulce P2, B je P6, E je P4. Nahraďte záhlaví řádků a sloupců v tabulce odpovídajícími písmeny:
Lekce je věnována řešení úlohy 3 jednotné státní zkoušky z informatiky
3. téma je charakterizováno jako úkoly základní úrovně složitosti, čas na dokončení - cca 3 minuty, maximální skóre - 1
* Některé obrázky stránek jsou převzaty z prezentačních materiálů K. Polyakova
Strukturování informací a informační modely
Podívejme se stručně na pojmy nezbytné k řešení úkolu 3 jednotné státní zkoušky.
Strukturování informací- jde o navázání hlavních prvků v informačních sděleních a navázání spojení mezi nimi.
Strukturování je hotovo s účel usnadnění vnímání a vyhledávání informací.
Strukturování je možné pomocí následujících struktur (informačních modelů):
seznam prvků shromážděných podle charakteristického znaku;
Vasja, Péťa, Kolja 1, 17, 22, 55
V sadě není nutné řazení prvků, tzn. Pořadí není důležité.
Důležité je pořadí prvků.
Zvýrazňují se tabulky objektů(záznamy jednotlivých tabulek) a vlastnosti(názvy sloupců nebo řádků): 
Uvažujme rodinné vztahy ve stromu:
Vykořenit– uzel bez předků (A).
Prostěradlo– uzel bez dětí (D, E, F, G).
Výška– největší vzdálenost od kořene k listu (počet úrovní).
Řekněme, že na pevném disku vašeho počítače jsou následující složky (adresáře) se soubory: 
Dostáváme strom: 
Někdy je velmi obtížné strukturovat informace pomocí popsaných struktur kvůli složitým „vztahům“ mezi objekty. Pak můžete použít grafy:
je množina vrcholů a spojení mezi nimi, které se nazývají hrany:
Graf zobrazující silnice mezi vesnicemi
je graf, který má cestu mezi některým ze svých vrcholů.
Strom je souvislý graf bez cyklů (uzavřené úseky).
Strom je souvislý graf bez cyklů
Vážené grafy mají „váhu hrany“: 
Z vážených grafů se získává váhová matice a je možná i inverzní transformace.
Nalezení nejkratší cesty (hrubá síla)
Určení nejkratší cesty mezi body A a D
- V úlohách Jednotné státní zkoušky na toto téma se nejčastěji používají dva informační modely - tabulky a diagramy.
- Informace ve stole je konstruován podle následujících pravidel: na průsečíku řádku a sloupce je informace, která charakterizuje kombinaci tohoto řádku a sloupce.
- Na diagramu informace jsou konstruovány podle následujícího pravidla: pokud existuje spojení mezi objekty diagramu, pak se zobrazí čárou spojující názvy těchto objektů na diagramu.
Řešení úkolů 3 jednotné státní zkoušky z informatiky
3_3: Řešení 3 úkolu Jednotná státní zkouška z informatiky (kontrolní verze č. 1 zkouškové práce 2018, S.S. Krylov, D.M. Ushakov):
Mezi osadami A, B, C, D, E, F byly vybudovány silnice, jejichž délka je uvedena v tabulce (pokud je buňka prázdná, žádná silnice není).
| A | B | C | D | E | F | |
| A | 7 | 3 | ||||
| B | 7 | 2 | 4 | 1 | ||
| C | 3 | 2 | 7 | 5 | 9 | |
| D | 4 | 7 | 2 | 3 | ||
| E | 1 | 5 | 2 | 7 | ||
| F | 9 | 3 | 7 |
Určete délku nejkratší cesty mezi body A A F .
✍ Řešení:
Výsledek: 11
Video analýza úkolu:
3_4:Řešení 3 jednotné státní zkoušky z informatiky (11. verze státní zkoušky z informatiky 2018):
Mezi sídly A, B, C, D, E, F byly vybudovány silnice, jejichž délka je uvedena v tabulce. Absence čísla v tabulce znamená, že mezi body nevede žádná přímá cesta.
| A | B | C | D | E | F | |
| A | 3 | 7 | 6 | |||
| B | 3 | 4 | 4 | |||
| C | 7 | 5 | 9 | |||
| D | 4 | 5 | 5 | |||
| E | 6 | 4 | 8 | |||
| F | 9 | 5 | 8 |
Určete délku nejkratší cesta mezi body A A F za předpokladu, že můžete cestovat pouze po silnicích uvedených v tabulce.
✍ Řešení:
Výsledek: 12
3_5: Řešení 2* Jednotné státní zkoušky z informatiky 2018, varianta 10 (FIPI, „Jednotná státní zkouška Informatika a ICT, standardní varianty zkoušek 2018“, S.S. Krylov, T.E. Churkina):
Mezi osadami A, B, C, D, E, F, Z Byly vybudovány jednosměrné silnice. V tabulce je uvedena délka každé silnice (neexistence čísla v tabulce znamená, že mezi body nevede žádná přímá cesta).
| A | B | C | D | E | F | Z | |
| A | 3 | 5 | 14 | ||||
| B | 2 | 8 | |||||
| C | 2 | 7 | |||||
| D | 1 | 4 | 4 | ||||
| E | 1 | 5 | |||||
| F | 12 | 1 | 9 | ||||
| Z |
Z kolika takových cest je A PROTI Z, který projít pěti nebo více osady? Položky A A Z vzít v úvahu při výpočtu. Nemůžete projít stejným kontrolním bodem dvakrát.
* v nových učebnicích byly úkoly 2 a 3 prohozeny: nyní 2 je Hledání nejkratší cesty a 3 je Algebra logiky
✍ Řešení:
Výsledek: 6
3_2: 3 úkol. Demoverze Unified State Exam 2018 computer science (FIPI):
Na obrázku je znázorněna silniční mapa okresu N-sky ve formě grafu, tabulka obsahuje informace o délce každé z těchto silnic (v kilometrech).
 |
 |
Vzhledem k tomu, že tabulka a diagram byly nakresleny nezávisle na sobě, číslování sídel v tabulce nijak nesouvisí s písmenným označením na grafu. Určete délku cesty z bodu A ukazovat G. Ve své odpovědi zapište celé číslo, jak je uvedeno v tabulce.
✍ Řešení:
- Spočítejme, kolik hran má každý vrchol:
Výsledek: 6
Pro podrobné řešení tohoto 3. úkolu z demoverze Unified State Exam 2018 se podívejte na video:
3_1: Jednotná státní zkouška z informatiky 2017, zadání ze sbírky Ushakova D.M., možnost 1:
Na obrázku je grafická mapa okresu N, tabulka obsahuje údaje o délkách těchto komunikací (v kilometrech).
 |
 |
Vzhledem k tomu, že tabulka a diagram byly nakresleny nezávisle na sobě, číslování sídel v tabulce nijak nesouvisí s písmenným označením na grafu.
Určete, jak dlouhá je cesta z bodu D ukazovat NA.
Ve své odpovědi zapište celé číslo, jak je uvedeno v tabulce.
✍ Řešení:
- Zvažte graf a spočítejte počet hran z každého vrcholu:
Výsledek: 20
Kromě toho se můžete podívat na video řešení tohoto úkolu jednotné státní zkoušky z informatiky:
3_6: Rozbor úlohy 3 Jednotné státní zkoušky varianta č. 1, 2019 Informatika a ICT Typické varianty zkoušky (10 možností), S.S. Krylov, T.E. Čurkina:
Obrázek ukazuje silniční mapu N-rayonu v tabulce, hvězdička označuje přítomnost silnice z jedné osady do druhé; Každé osídlení na diagramu odpovídá svému číslu v tabulce, ale není známo, které číslo.
 |
|
Určete, která čísla sídel v tabulce mohou odpovídat sídlům D A E na diagramu? Ve své odpovědi zapište tato dvě čísla ve vzestupném pořadí bez mezer a interpunkce.
✍ Řešení:
- Nejprve najdeme jedinečné vrcholy – ty, které mají jedinečný počet hran: toto A(2 žebra) a H(6 žeber). V tabulce odpovídají číslům 3 a 4:
- Podle diagramu zjistíme, že sousední vrcholy pro A jsou B A G. V tabulce určíme jim odpovídající čísla - 1 a 2. Protože nás podle zadání nezajímají, označíme je společně:
- Oba vrcholy B a G sousedí s již známými A a H a navíc s vrcholy F A C. Z prvního sloupce nebo prvního řádku zjistíme, že F nebo C bude odpovídat číslu 7 a ve druhém řádku číslu 8. Označme je v tabulce:
- Výsledkem je, že požadované vrcholy jsou D A E- čísla odpovídají 5 A 6 . Protože nezáleží na tom, které číslici má ten či onen vrchol odpovídat, v odpovědi jednoduše napíšeme tyto číslice vzestupně.
| 1 | 2 | A | H | 5 | 6 | 7 | 8 | |
| 1 | * | * | * | |||||
| 2 | * | * | * | |||||
| A | * | * | ||||||
| H | * | * | * | * | * | * | ||
| 5 | * | * | * | |||||
| 6 | * | * | * | |||||
| 7 | * | * | * | |||||
| 8 | * | * | * |
| B,G | B,G | A | H | 5 | 6 | 7 | 8 | |
| B,G | * | * | * | |||||
| B,G | * | * | * | |||||
| A | * | * | ||||||
| H | * | * | * | * | * | * | ||
| 5 | * | * | * | |||||
| 6 | * | * | * | |||||
| 7 | * | * | * | |||||
| 8 | * | * | * |
| B,G | B,G | A | H | 5 | 6 | F,C | F,C | |
| B,G | * | * | * | |||||
| B,G | * | * | * | |||||
| A | * | * | ||||||
| H | * | * | * | * | * | * | ||
| 5 | * | * | * | |||||
| 6 | * | * | * | |||||
| F,C | * | * | * | |||||
| F,C | * | * | * |
