Třetí série pátého ročníku KSP

Tyto úlohy pocházejí z desetileté ročenky KSP. Jejich řešení bohužel nemáme v elektronické podobě, takže na ně budete muset přijít sami.

Zadání úloh

5-3-1 Obří matice

V souboru je uložena po řádcích matice čísel o rozměrech N×N, kde je 1≤ N≤ 1000. Vaším úkolem je navrhnout algoritmus a napsat program, který danou matici transponuje, tj. uloží ji do souboru po sloupcích. Smí při tom používat další pomocné soubory.

Příklad: Matice 3×3

( 10 7 9 )
-4 5 6
8 1 4

je uložena v souboru jako posloupnost čísel 10,7,9,-4,5,6,8,1,4 a váš program matici transponuje na posloupnost 10,-4,8,7,5,1,9,6,4.

5-3-2 Zase posloupnost

Je dáno pole čísel A[1] až A[N]. Vaším úkolem je nalézt algoritmus a napsat program, který pro dané číslo X určí i,j takové, že součet prvků A[i] + A[i+1] + … + A[j] se ze všech možných i,j nejvíce blíží číslu X. Dále se pokuste dokázat, že rychleji, než to děláte vy, to už nejde.

5-3-3 A do třetice...

Je dána posloupnost čísel a1, a2, … an. Napište program, který určí délku nejdelšího symetrického úseku (tzv. palindromu) v této posloupnosti, tedy nalezne největší d takové, že existuje p (počátek symetrického úseku) a pro všechna i , 0≤ i ≤ d platí ap+i = ap + d - i -1.

Příklad: Pro posloupnost čísel 1,2,3,4,5,4,3,2,3,4,5,4 program vypíše výsledek 9.

Poznámka: Nezapomeňte na důkaz správnosti algoritmu!

5-3-4 Plánovač

Úvod do problematiky dílků:

Na jednom procesoru má pseudoparalelně běžet několik procesů. Strojový čas procesoru se procesům přiděluje po stejně dlouhých úsecích nazývaných dílky (představujte si například, že 1 dílek = 55ms (tahle hrozná cifra je právě velikost jednoho tiku hodin PC)). Po dobu každého dílku běží některý z procesů (právě jeden). Dílky mají být procesům přidělovány tak, aby jednak celkové časy běhu jednotlivých procesů byly v zadaném poměru, a jednak aby si každý proces „líznul“ přiměřeně často (jinak by se třeba na obrazovce zastavily hodiny, počítač by nestíhal komunikovat přes modem a příliš by se usnadnilo hraní Tetrisu). Úkolem je navrhnout vhodný způsob přidělování dílků procesům a napsat program, který bude přidělování provádět. Situace je navíc komplikována tím, že procesy dynamicky vznikají a zanikají.

Příklad: Uvažujme tři procesy označené A, B a C, které mají dostávat strojový čas v poměru 1:2:3.14 (těmto číslům budeme říkat priority), tj. proces B dvakrát víc než A, proces C 3.14-krát víc než A. Pak jeden z možných způsobů přidělení dílků procesoru těmto procesům vypadá následovně:

C,B,A,C,B,C,C,B,A,C,B,C,…

Všimněte si, že v tomto (periodickém) úseku byl poměr dílků A:B:C přesně 1:2:3. Po určitém čase by tedy bylo třeba vložit „navíc“ nějaký dílek C, aby se poměr blížil k hodnotě 3.14. Kdyby posléze proces C zanikl, mohlo by přidělování vypadat např. takto:

B,A,B,B,A,B,B,A,B,B,A,…

Zadání:

  1. Navrhněte a podrobně popište vhodný plánovací algoritmus. Měl by jednak přidělovat dílky procesům tak, aby každý proces běžel přiměřeně často, jednak přidělovat dílky procesům v zadaném poměru. Uveďte, proč má váš algoritmus požadované vlastnosti (a jaké vlastně).
  2. Na základě svého plánovacího algoritmu napište knihovnu podprogramů pro plánování procesů obsahující tyto služby:
    • procedure Init – inicializuje všechno, co je třeba,
    • procedure AddProcess(Id:Integer; Pri:Real) – zahrne do plánování strojového času další proces se zadaným identifikačním číslem (každý proces má jiné) a zadanou prioritou,
    • procedure RemoveProcess(Id:Integer) – odstraní z plánování proces s identifikačním číslem Id,
    • function NextProcess:Integer – jeden krok plánování: vrátí identifikační číslo procesu, který má (podle vašeho plánovacího algoritmu) běžet v dalším dílku. Představujte si, že tuto vámi naprogramovanou funkci na začátku každého dílku zavolá jádro operačního systému (jak toho dosáhne, to už není vaše starost), aby se dozvědělo, který proces má nechat běžet. Tato funkce by měla běhat zatraceně rychle, aby procesům nezkracovala jejich dílek (viz výše uvedených 55ms).

Příklad:

Init;
        ...
AddProcess(1,1.0) ;
AddProcess(2,2.0) ;
AddProcess(3,3.14) ;
        ...
Id:=NextProcess; { Id=3 }
        ...
Id:=NextProcess; { Id=2 }
        ...
Id:=NextProcess; { Id=1 }
        ...
Id:=NextProcess; { Id=3 }
	...

5-3-5 Automaty

Doufáme, že od minulé série již každý z vás ví, co je to konečný automat a jak funguje. Pokud si zrovna nevzpomínáte, doporučujeme vám okamžitě si přečíst studijní text v kapitole 11. Pro vás ostatní jsme připravili další úlohy týkající se konečných automatů. Sestrojte konečné automaty rozpoznávající tyto jazyky:

L1={w∈{a,b}*;  w=xaa ya nebo w=xbb yb; x,y∈{a,b}*}

Lidsky řečeno: slovo musí obsahovat aa nebo bb; přitom pokud slovo obsahuje aa, musí končit na a, pokud obsahuje bb, musí končit na b. Pozor: Pokud slovo obsahuje aa i bb, pak může končit na a i na b.

Příklad: Slova aaba, aaa, aabbab, bababbb jsou slova z jazyka. Ale slova abba, aab, baba, aa nepatří do tohoto jazyka.

L2={w∈{a,b,c,d}*;  pro všechna x∈{a,b,c,d} platí: x∈w}

Lidsky řečeno: slova tohoto jazyka musí obsahovat každé z písmen {a,b,c,d} alespoň jednou.

Příklad: Slova bbcdbca, bcaaaaaad, ddbbcdda patří do jazyka. Slova abccba, dddbc, acd tam nepatří.

L3={w∈{a,b,c,d}*;  |w |=4, w∈L2}

Lidsky řečeno: slova tohoto jazyka obsahují každé z písmen {a,b,c,d} právě jednou.

Příklad: Slova cdba, abcd, acdb patří do jazyka. Slova abcda, bbcda, dcabd, aabc tam nepatří.