Cvičení z programování I pro pokročilé

Ve školním roce 2011/2012 vedeme s Vojtou Tůmou speciální cvičení z předmětu Programování I [NPRG030] pro pokročilé studenty, kteří již nasbírali nějaké zkušenosti z programování (třeba v olympiádách a korespondenčních seminářích) a chtěli by se naučit víc.

Viz též letáček :-)

Cvičení se koná každý čtvrtek od 14:00 v S6, kdo chcete chodit, přihlašte se, prosíme, v SISu, případně nám pošlete mail, pokud vám to SIS nedovolí.

Podmínky k získání zápočtu jsou (AND):

Kontakt

Svým cvičícím pište na adresu mami@ucw.cz.

Zápočtový program

Domácí úkoly

Domácí úkoly jsou dvou druhů:

Na získání kýžené stovky bodů bohatě stačí praktické úlohy, pokud je řešíte včas.

Teoretické úkoly

DatumIDBodyPříklady
6. 10. funf5Co dělá funkce f() z letáčku?
funb5Co dělá funkce bc() z letáčku?
2mis15Princezně se rozsypaly perly z náhrdelníku (očíslované 1 až N) a dvě z nich se ztratily. Jak v lineárním čase a konstantní paměti zjistit, které?
20. 10. ndpx15Vymyslete n-rozměrnou variantu prefixových součtů, tedy strukturu, která si pro n-rozměrnou matici v lineárním čase něco předpočítá a pak bude umět v konstantním čase vypočíst součet libovolné n-rozměrné souvislé podmatice. Předpokládejte, že n je konstanta.
15. 12. gseq7Vymyslete algoritmus, který vypíše všechny posloupnosti n nul a jedniček v takovém pořadí, aby se každé dvě sousední lišily jen na jedné pozici.
gsek13Jak vypsat posloupnosti n nul a jedniček s právě k jedničkami v takovém pořadí, aby se dvě sousední lišily na právě dvou pozicích?
5. 1. pcol11Uvažujme algoritmus pro barvení rovinných grafů s očíslovanými vrcholy: na počátku nemá žádný vrchol barvu; pak vždy vybereme vrchol, který má nejvýše 5 neobarvených sousedů (pokud jich je více, tak vítězí vrchol s nejmenším pořadovým číslem), a přidělíme mu nejmenší barvu, kterou nepoužívají jeho sousedé. Dokažte, že pro každé K existuje rovinný graf, na jehož obarvení tento algoritmus spotřebuje alespoň K barev.

Co jsme dělali

datum co se cvičilo
6. 10.

Pár příkladů na úvod:

  • Měli jsme posloupnost 1…N. Někdo ji zamíchal a jedno číslo škrtnul. Jak v lineárním čase a konstantní paměti zjistit, které?
  • Je dána posloupnost přirozených čísel, ve které se všechna čísla vyskytují sudě-krát až na jedno nezbedné. Které?
  • Robin Hood s kouzelným lukem: V rovině je N bodů, najděte polopřímku, na které leží nejvíce z nich.
  • Je zadán řetězec znaků. Najděte v něm nejdelší souvislý úsek, ve kterém se neopakují znaky.
  • … totéž, ale s neopakováním slov v textu.
13. 10. Úlohy o posloupnostech: dvojice s daným součtem, úsek s daným součtem.
20. 10. Ještě posloupnosti: úsek se součtem co nejbližším zadanému, nejdelší vyvážený úsek. Největší nulová podmatice. 2D prefixové součty.
27. 10. Nejdelší rostoucí podposloupnost. Házíme vajíčka. Kompromisy mezi časem a pamětí: spočtěte všechna yk = x1 * … * xk-1 * xk+1 * … xn (kde * je nějaká asociativní operace).
3. 11. RGB třídění (ladění konstant a též verze pro k barev). Šroubky a matičky aneb o síle randomizace. Míchání karet.
10. 11. Módní přehlídka třídících algoritmů. Operace s haldou. Třídíme posloupnost obsahující jen O(log n) různých čísel. Nebo jen celá čísla z rozsahu 1 až n2. Střílíme po billboardech. Budou volby…
17. 11. Cvičení se nekoná, slavíme 2002. narozeniny císaře Vespasiana (mimo jiné).
24. 11. Prohledávání grafů, Dijkstrův algoritmus a přihrádkové struktury. Agenti a jejich šéf, stoky a jejich strážníci (jak hlídat každou stoku, jak kontrolovat mafiány, kolika způsoby to jde).
1. 12. Šéf agentů na mnoho způsobů.
8. 12. O stromech a mafiánech. Asfaltéři v neorientovaném městě.
15. 12.

Generování všech objektů s danou vlastností:

  • posloupnosti nul a jedniček délky n
  • … takové, které obsahují právě k jedniček
  • dobře uzávorkované posloupnosti délky n
  • rozklady čísla n na součty (na pořadí sčítanců nezáleží)
  • permutace na n-prvkové množině
Možné přístupy: rekurzivně, hledáním následníka, s co nejméně změnami …
22. 12. Generování, ranky a unranky.
5. 1. Symetrická orientace grafu se sudými stupni, dělení stupňů a párovaní v 2k-regulárním bipartitním grafu. Barvení rovinných grafů 6 a 5 barvami.
12. 1. Jeřábníkův problém. Co když je jeřáb strom? Kdy se jeřáb protne?
Stránku spravuje Martin Mareš