Seminář Programování I - úterý 15:40 S1

Pokyny pro posílání domácích cvičení z Pascalu

tyto pokyny se během semestru ještě změní

• Mail posílejte na adresu KRYL@KSVI.MFF.CUNI.CZ
• Do subjectu mailu napište
  DCVPRM "VaseJmeno" "Nazevulohy", např.
  DCVPRM Josef Vosolsobe treti nejvetsi
• Program pošlete jako přílohu, nikoli v textu mailu
• Soubor v priloze by mel mit nejvyse osmiznakove jmeno - vasejmeno a prilohu pas, napr.
  JosVosol.pas
  Pokud možno tuto osmiznakovou přezdívku dodržujte ve všech úkolech
• Program pište s ukončovánim řádek jako v DOS/Win,
• Na první řádek programu napište komentář s vaším celým jménem

1. seminář 4.října 2005
   • Úlohy na algoritmizaci:
     • Tři největší prvky
     • Největší prvek z N prvků na N-1 porovnání, algoritmus držení dosud nejlepšího, algoritmus turnaje, rychleji to nejde
     • Druhý největší z 8 prvků na 9 porovnání
     • Lámání čokolády
     • Cesty věže po šachovnici
     • Hledání odlišné koule ze 3 koulí (je tam nejvýše 1 jiná)
   • Na rozmyšlenou:
     • Na kolik porovnání jde najít druhého největšího z N prvků
     • Zkuste dokázat, že tento počet je optimální
     • Otimalizujte počet cest elektrikáře nahoru a dolů při párování žil mnohažilového kabelu
     • Úloha o vězních
     • Víme, že mezi N koulemi je nejvýše jedna odlišná - na kolik vážení jde zjistit, jaká je situace skutečně.
     • Cesty věže po šachovnicích s odstaněným 1 nebo 2 rohy
     • Jak daleko od hrany stolu se teoreticky může vzdálit věž postavená z N stejných cihel ?
2. seminář 11.října 2005
   Všechny nevyřešené problémy z minula zůstávají
   • vzorec pro počet porovnnání potřebných pro nalezení druhého největšího z n
   • elektrikář zůstává - počet cest nutných k vyřešení je malý a konstantní (nezávislý na počtu žil kabelu)
   • Dílčí výsledky úlohy o koulích - např. ze 4 koulí s jednou správnou jde na 2 vážení
   • Návod na řešení úloh o cestách věže na šachovnici
   • Nové úlohy na přemýšlení:
     • Synchtronizace konečných automatů - generál, voják, zadák, řada vojáků má vystřelit salvou (bez ohledu nadélku řady)
     • Velbloud nosnosti 1000 banánů a spotřebu 1banán na 1 km má z počáteční hromady 3000 banánů dopravit do co největší vzdálenosti 1000 banánů
       Zkuste řešit i obecně
     • Princ, princezna a otočný stolek se 4 sklenicemi
     • Na políčcích pásky sudé dély jsou napsána kladná čísla prémií. Hráči střídavě ustřihují jedno z krajních políček.
       Vyhraje, kdo získá větší součet prémií. Poraďte začínajícímu hráči.
3. seminář 18.října 2005
   Všechny nevyřešené problémy z minula zůstávají
   • Řešení úlohy o vězních
   • Řešení úlohy o velbloudovi
     Zůstává obecné řešení
   • Řešení úlohy o elektrikáři
   • Cesty věží na šachovnicích s uřízlými rohy,
     Zůstává popsat algoritmus pro hledaní cesty z daného bílého políčka na šachovnici s jedním uřízlým černým rohem
   • Nim s jednou hromádkou, ve kterém se smí brát 1-3 mince
   • Řešení úlohy s 13 podezřelými koulemi a jednou správnou na tři vážení
     Horní odhad počtu koulí, pro které jde úlohu vyřešit na k vážení
   • Nové úlohy na přemýšlení:
     • NIM s jednou hromádkou, v němž se může brát
       • liše mincí
       • 1,3,4 nebo 5 mincí
       • 2,3 nebo 4 mince
       • mocnina dvojky mincí
     • NIM s dvěma hromádkami (a stejným počtem mincí, které je možno v jednom tahu vzít (musejí být z jedné hromádky)
     • Hry s kameny
       • se dvěma - mohou být dva na stejném poli
       • se dvěma - nemohou být dva na stejném poli
       • se třemi kameny
       • se čtyřmi kameny
     • Kulový blesk
   • Písemný domácí úkol:
     Nalezněte třetí největší číslo z pěti (můžete předpokládat, že jsou po dvou různé)
     na co nejmenší počet porovnání. Soustřeďte se na způsob popisu algoritmu pokud nedokážete "optimální algoritmus hezky popsat, popište třeba horší lépe. (So
   • Fotografie
 
4. seminář 25.října 2005
   Všechny nevyřešené problémy z minula zůstávají
   • Synchronizace automatů - rekapitulace úlohy
     návod: pokuste se najít střed řady vojáků
   • Obecné řešení úlohy o velbloudovi - rozmyslet důkaz.
   • Princ a princezna
   • Kulový blesk
   • Páska sudé délky
   • Hra s dvěma kameny, s třemi a čtyřmi zůstává.
   • NIM na jedné hromádce bere se
     • liše
     • 2,3 nebo 4
     • ostatní zůstávají
   • Nové úlohy na přemýšlení:
     • Na vstupu je posloupnost kladných celých čísel, ukončená číslem -1.
       Máme najít minimum a maximum této posloupnosti spolu s jejich četnostmi
     • Na vstupu je posloupnost kladných celých čísel, ukončená číslem -1, která je navíc "vloženými" nulami rozdělena na úseky.
       Máme nají třetí největší číslo z druhého nejdelšího úseku.
     V obou případech smíme vstup číst pouze jednou.
     Všichni si rozmyslí kolik proměnných potřebují k vyřešení té které úlohy (budeme se snažit jejich počet minimalizovat).
     Ti, kteří se již nemohou dočkat psaní programů a programování někdy (v minulém životě) měli, zkusí napsat příslušné programy.
 
5. seminář 1.listopadu 2005
   Všechny nevyřešené problémy z minula zůstávají
   • Třetí z pěti na 6 porovnání.
   • Synchtronizace konečných automatů - generál, voják, zadák,
   • Algoritmus pro hledaní cesty z daného bílého políčka na šachovnici s jedním uřízlým černým rohem
   • Návody pro:
     • Úlohu o N koulích
     • Hru se čtyřmi kameny
   • Na vstupu je posloupnost kladných celých čísel, ukončená číslem -1.
     Máme najít minimum a maximum této posloupnosti spolu s jejich četnostmi
     • Kolik proměnných je třeba
     • Program
   • Na vstupu je posloupnost kladných celých čísel, ukončená číslem -1, která je navíc "vloženými" nulami rozdělena na úseky.
     Máme nají třetí největší číslo z druhého nejdelšího úseku.
     Kolik proměnných je třeba
     Program jako nepovinné domácí cvičení
   • Krátká písemka
 
6. seminář 8.listopadu 2005
   • Hra se čtyřmi kameny
   • Hra se třemi kameny
   • Co je třeba dokázat, chceme-li tvrdit, které pozice hry jsou vyhrané resp. prohrané pro hráče na tahu.
   • Dvourozměrné pole.
   • Funkce hledající největší prvek matice ze všech, které leží nad diagonálou.
   • Funkce počítající počet dělitelů čísla typu integer
   • Funkce počítající počet prvočíselných dělitelů daného čísla
   • Funkce, která vrací řádkový index třetího největšího čísla v matici.
   • Domácí úkol: funkce, která spočítá počet sudých čísel v poli čísel typu integer
 
7. seminář 15.listopadu 2005
   • Funkce počítající počet inversí v daném vektoru
   • Permutace a její vektor inversí
     Je-li {p_i} i=1,..D permutace čísel 1.. D,
     pak její vektor inversí je vektor {v_i} definovaný takto:
     v_i = počet indexů j > i, pro které je p_j < p_i
   • úsek programu počítající z prermutace její vektor inversí
   • úsek programu počítající z vektoru inversí permutaci (předpokládáme, že "vstupem" je vektor inversí nějaké permutace)
     Rozmyslet alternativní způsob naprogramování
   • lexikografocké uspořádání
   • nalezení permutace (bezprostředně) následující po zadané permutaci v lexikografickém uspořádání
     program jako písemné domácí cvičení
   • algoritmus počítající pořadí zadané permutace v lexikogragfickém uspořádání všech permutací této délky
   • inverzní algoritmus - k zadanému číslo K nalézt K-tou permutaci (z čísel 1..D) v lexikografickém uspořádání
   • Domácí úkol: Rozmyslet naprogramování těchto dvou algoritmů
Předvedení práce s překladačem Borland Pascal
první polovina v úterý 22.listopadu v 14:45 v pracovně cvičícího MS III.patro č. dv. 312
 
8. seminář 22.listopadu 2005
   • Komentář k domácím úlohám
   • pořadí zadané permutace v lexikogragfickém uspořádání všech permutací této délky
   • k zadanému číslo K nalézt K-tou permutaci (z čísel 1..D) v lexikografickém uspořádání
   • počet sousedních čísel v dané posloupnosti
   • Delka nejdelšího rostoucího začátku z dané posloupnosti
   • Domácí úkol:
     • Index prostředního výskuty daného čísla v poli - povinný úkol
     • nalezení permutace (bezprostředně) následující po zadané permutaci v lexikografickém uspořádání - dobrovolný
   Předvedení práce s překladačem Borland Pascal
   druhá polovina v úterý 29.listopadu v 14:30 v pracovně cvičícího MS III.patro č. dv. 312
9. seminář 29.listopadu 2005
   • Nemohu zrekonstruovat
   • Úlohy na rozmyšlenou
     • úlohy na čas a kalenář, např. kolik dní uplynulo mezi dvěma daty a pod.
     • šifra Monte Christo
     • Zarovnávání textu do bloku
   • Domácí úkol: Kolikrát bylo mezi dvěma daty pátek 13. ?
 
10. seminář 6.prosince 2005
    • Nabídka zápočtových úloh
    • Analýza úlohy šifra Monte Christo.
      Domácí úkol: napsat a odladit příslušný program
    • Kombinace k-té třídy z n prvků
    • Rozmyslet:
      • Zarovnávání textu do bloku - až do návrhu programu
      • Proceduru, které vytiskne všechny kombinace k-té třídy z n prvků
11. seminář 13.prosince 2005
    • Program, který vypisuje maximální (tj. takové, které nejdou prodloužit) aritmetické posloupnosti prvočísel menších než číslo zadané na vstupu.
      kolektivní tvorba - asi jsme se dopustili nepříjemné , i když snadno opravitelné, chyby - podívejte se na to
    • Rozmyslet: Na vstupu je šachovnice M krat N ( rozměry oba rozměry menší než 10) se zakázanými poli.
      • Domácí úkol - Dominance dam: Nalezněte nejmenší počet dam, které dominují této šachovnici (a vytiskněte jedno z jejich možných rozestavení)
      • Nezávislost dam: Nalezněte největší počet dam, které jde na tuto šachovnici umístit tak, aby se neohrožovaly (a vytiskněte jedno z jejich možných rozestavení) .
12. seminář 20.prosince 2005
    • Komentář k domácím úkolům
    • Analýza úlohy o kódování a dekódování morzeovky
    • Analýza úlohy o hledání všech výrazů (sestavených ze zadaných čísel a libovolných aritmetických operátorů) majících zadaný součet
    • Algoritmus vlny pro maharádže na šachovnici
    • Opakování práce s textovými soubory
    • Zadání zápočtových úloh
13. seminář 3.ledna 2006
    • Vytvoření tabulky kódu morseovky,
      alternativní řešení s hashovací funkcí (interpretace kódu jako zápisu čísla v trojkové soustavě)
    • Tisk "reklamního" kalendáře
    • "cenzurní" program
    • Diagonální latinský čtverec
    • Rozmyslet:
      Úlohy 40,42 a 43 ze sbírky
14. seminář 10.ledna 2006
    • Vytváření frekvenční tabulky výskytu slov
    • Dominance maharádžů na pneumatice
Dohodnuta hromadná (dobrovolná) konzultace u počítače v pátek 16. prosince od 14:00 v laboratoři K5 v Karlíně.
Každý, kdo se jí chce zúčastnit by si musí si zřidit v této laboratoři účet.
Předpokládám samostatnou práci jednotlivých studentů na vývoji nějakého programu s mojí podporou.
Můžete řešit jakýkoli program, bylo by vhodné si vzít takový, u kterého je reálná šance, že s ním za cca 2 1/2 hodiny pohnete.
Pro inspiraci Vám může sloužit seznam.
Předpokládaný konec cca 16:30.