Programování 1 pro matematiky

Ve školním roce 2019/2020 vedu cvičení z předmětu Programování 1 [NMIN111], což je základní kurs programování pro studenty matematiky. Cvičení se koná každý pátek od 10:40 v učebně K11.

Programujeme v Pythonu 3, používáme interaktivní prostředí IDLE.

Pokud se mnou chcete cokoliv probrat, jste vítáni v mé pracovně S322 na Malé Straně. Případně napište e-mail na adresu mares+p1m@kam.mff.cuni.cz.

Zápočet se udílí za získání alespoň 70 bodů za domácí úkoly. Úkoly se odevzdávají v ReCodExu.

Co jsme dělali

datum téma
4. 10.
11. 10.
18. 10.
  • Slidy: Seznamy
  • Výpis seznamu pozpátku
  • Fibonacciho čísla
  • Eratosthenovo síto
  • Další úkoly: Je dána posloupnost čísel...
    • zjistěte, jestli jsou všechna navzájem různá.
    • najděte dvojici s co nejmenším rozdílem.
    • vypište všechna opakující se čísla (ale každé jen jednou).
    • Umíte předchozí úkoly vyřešit efektivněji, pokud víte, ze všechna zadaná čísla leží od 1 do 100?
25. 10.
1. 11.
  • Slidy: Funkce
  • Napište funkci, která:
    • vrátí nejmenší ze tří čísel: řešení
    • vrátí n-té Fibonacciho číslo: řešení
    • spočítá, kolik je v seznamu sudých čísel: řešení
    • vybere ze seznamu sudá čísla (a vrátí jejich seznam): řešení
    • dostane dva seřazené seznamy čísel a vrátí jejich průnik: řešení
    • dostane koeficienty kvadratické rovnice ax2 + bx + c = 0 a vrátí seznam jejích kořenů: řešení
8. 11.
  • Slidy: Seznamy, řezy a řetězce
  • Napište funkci, která:
    • otočí řetězec (datelletad)
    • otočí číslo v desítkové soustavě (10244201; může se hodit, že int(x) převádí z řetězce na číslo a str(x) opačně)
    • spočítá, kolik zadaný řetězec obsahuje slov (oddělených mezerami)
    • … kolik různých slov
    • vyhodnotí výraz se sčítáním (12+34+147)
    • vyjádří číslo česky (123"sto dvacet tři"): řešení
  • Řešení příkladů
15. 11.
  • Slidy: List comprehensions
  • Napište funkci, která:
    • vytvoří tabulku násobilky (a×b pro všechna a, b od 1 do daného čísla)
    • zjistí průnik dvou (neuspořádaných) seznamů
    • vybere z textu slova, která jsou palindromická (čtou se stejně popředu jako pozpátku)
    • spočítá skalární součin dvou vektorů
    • vynásobí dvě matice (ne nutně čtvercové)
    • seřadí slova na řádku podle jejich délky (nápověda: nejprve slova převést na dvojice (délka, slovo), ty pak setřídit a nakonec z dvojic zase udělat slova)
  • Řešení příkladů
22. 11.
  • Slidy: Množiny a slovníky
  • Příklady: robůtek, kontakty
  • Napište funkci, která:
    • Vrátí True nebo False podle toho, zda jsou dané dva seznamy stejné až na pořadí prvků. Co když se mohou prvky v seznamech opakovat?
    • Vrátí True nebo False podle toho, zda jsou všechny prvky daného seznamu navzájem různé.
    • Řešení
  • Spočítejte frekvence všech k-gramů (k-tic znaků) v textu. K-gramy vypište uspořádaně podle frekvence (řešení, jiné řešení). Můžete vyzkoušet třeba na originálu Psa baskervillského z Projektu Gutenberg. Řádky souboru můžete načítat pomocí for řádek in open('soubor').
  • Aplikace k-gramů:
    • Pro každý k-gram zjistěte, jaká všechna písmena po něm mohou následovat. Pokud jedno písmeno opakuje, uložte ho vícekrát.
    • Předchozí tabulku využijte k náhodnému generování textu. První k-gram zvolte náhodně a pak opakovaně vybírejte náhodné následující písmeno. Pro náhodný výběr ze seznamu se může hodit random.choose(seznam) (nezapomeňte na import random).
    • Řešení.
29. 11.
  • Slidy: Třídy a objekty
  • Příklad definice třídy
  • Nadefinujte třídu Rect reprezentující obdélníky v rovině: (domácí úkol)
    • atributy x1, y1, x2, y2 pro souřadnice levého dolního a pravého horního vrcholu
    • vytváření objektů voláním Rect((x1,y1), (x2,y2))
    • konverze na řetězec
    • metoda perimeter pro výpočet obvodu
    • metoda area pro výpočet obsahu
    • operátor == (metoda __eq__(self, other)) pro rovnost obdélníků (vrátí True nebo False)
    • operátor in (metoda __contains__(self, other)) pro test, zda je jeden obdélník podmnožinou druhého (neostře)
    • operátor & (metoda __and__(self, other)) pro průnik obdélníků (vrátí nový obdélník)
  • Nadefinujte třídu RoundRect odvozenou od Rect pro obdélníky se zakulacenými rohy (s jednotkovým poloměrem; předpokládejme že délky všech stran jsou alespoň 2). Předefinujte metody, aby dávaly smysl.
6. 12. Pokračování objektů.
13. 12.
  • Slidy: Triky s funkcemi
  • Je dán seznam řetězců tvaru "jméno příjmení":
    • Setřiďte je primárně podle příjmení, sekundárně podle jména.
    • Najděte osobu s nejdelším příjmením.
    • Na rozmyšlení: Jak byste naložili s osobami, které mají více křestních jmen, případně více příjmení?
  • Cvičení na redukci seznamů:
    • Napište funkci red(s,f), která dostane seznam s a funkci f(x,y) a spočítá s[0] f s[1] f s[2] f ... f s[-1]. Zápisem x f y myslíme zavolání f(x,y), celý výraz se vyhodnocuje zleva doprava.
    • Zapište pomocí redukce součet prvků seznamu.
    • Zapište pomocí redukce nalezení maxima seznamu.
    • Zapište pomocí redukce nalezení prvního nenulového prvku (není-li, vraťte 0).
    • Co redukce udělá pro operátor -?
    • Co udělá red(s, lambda x, y: (x,y))?
    • (*) Zapište pomocí redukce test, zda jsou všechny prvky seznamu stejné.
    • Na rozmyšlení: Jak byste redukci definovali pro jednoprvkové seznamy? Může dávat nějaký smysl pro prázdné seznamy?
    • (mimochodem, redukci má Python zabudovanou a jmenuje se reduce)
  • Napište generátor, který dostane dva seznamy a bude generovat jejich kartézský součin.
  • Napište funkci compose(f,g), která pro dvě funkce f a g (obě s jedním parametrem) vrátí funkci, jež je jejich složením.
20. 12.
  • Slidy: Soubory a výjimky
  • Napište program, který dostane textový soubor a:
    • Spočítá, kolik je v něm řádků, slov a viditelných znaků (tedy bez mezer a konců řádků)
    • Zkopíruje ho do jiného souboru …
    • … tak, aby řádky šly v opačném pořadí (první se stane posledním atd.)
    • … tak, aby šla v opačném pořadí i slova na řádcích
    • Najde na každém řádku všechna čísla (oddělená mezerami) a vypíše jejich součet; slova, která nejsou čísly, ignoruje.
10. 1.
  • Slidy: Standardní knihovna
  • Příklady:
    • Simulujte 1000 hodů kostkou. Spočítejte výskyty každého čísla. Kolik jich je nejméně a kolik nejvíce? (řešení)
    • Generujte náhodně body ve čtverci [-1,1] × [-1,1]. Počítejte, kolik z nich padlo do jednotkového kruhu, a tím aproximujte π. (řešení)
    • Generujte náhodně permutace slov věty "Nemám rád zbytečně použité permutace." Kolik z nich dávalo smysl? :) (řešení)
    • Vygenerujte náhodně permutaci na množině 1 až N a spočítejte, kolik má pevných bodů. Opakováním experimentu odhadněte, jaká je pravděpodobnost, že náhodná permutace nemá pevný bod. (řešení)
    • Pomocí Malé Fermatovy věty testujte, zda je nějaké velké číslo pravděpodobně prvočíslem. Hodí se tříparametrová funkce pow(a, b, c), která efektivně spočítá ab mod c.
    • Simulujte náhodnou procházku po celých číslech od 0 do N. Začínáme v 0, v každém kroku náhodně buď zvýšíme nebo snížíme o 1 (v 0 jen zvyšujeme). Po kolika krocích se dostaneme do N? Jak dopadne dvojrozměrná verze (ze středu čtverce se chceme dostat k okraji)?

Odkazy

Stránku spravuje Martin Mareš