Cvičení 1 - Opakování

Téma 1: Opakování O-notace

Rozhodněte, zda následující vztahy platí nebo ne. Dokažte.

1. 20 ⋅ n + 6 ∈ O(n)
2. 20 ⋅ n + 6 ∈ Ω(n)
3. 20 ⋅ n + 6 ∈ Θ(n)
4. Σ_{i = 1, …, n} (i) ∈ O(n²)
5. n! ∈ O(n)

Téma 2: Opakování C/Pythonu

Jazyk C

Následující úkol pokrývá základní znalosti, ktere byste už měli mít z kurzu Jazyka C a Algortimů 1.

1. Vytvořte v C strukturu struct debtor pro záznam adresáře dlužníků obsahující:
   • jméno dlužníka (name),
   • příjmení dlužníka (surname),
   • věk dlužníka (age),
   • dlužnou částku (debt).
2. Vytvořte adresář dlužníků jako pole struktur z předchozího bodu (data si vymyslete; alespoň pět záznamů).
3. Napište následující funkce (parametr n je vždy velikost pole):
   • pro přístup k údajům dlužníka (význam je jasný z názvu):
     • string debtor_name(struct debtor* d),
     • string debtor_surname(struct debtor* d),
     • int debtor_age(struct debtor* d),
     • int debtor_debt(struct debtor* d);
     • Pokud ještě neznáte pointery, tak tyto funkce mohou působit potíže kvůli způsobu, jakým C předává parametry. Klidně je vynechte a používejte přímo debtorX.name, atd.
   • vypisující dlužnou částku na standardní výstup pro zadaný adresář, jméno a příjmení dlužníka: void print_debt(struct debtor debts[], int n, string name, string surname)
   • vracející dlužníka s největším dluhem (jeho index v adresáři) v zadaném adresáři: int max_debt(struct debtor debts[], int n)
   • navyšující dluh zadaného dlužníka o zadanou částku v zadaném adresáři: void increase_debt(struct debtor debts[], int n, string name, string surname, int amount)
   • snižující dluh zadaného dlužníka o zadanou částku v zadaném adresáři: void decrease_debt(struct debtor debts[], int n, string name, string surname, int amount)
   • vracející i-tého nejmladšího dlužníka (jeho index v adresáři) pro zadané i a zadaný adresář: int ith_youngest(struct debtor debts[], int i, int n)
   • Vypisujícíí zadaný adresář setřízený vzestupně podle věku dlužníka: void sort_debts(struct debtor debts[], int n)

Další informace:

• Chcete-li typ string místo pole znaků, jak je použit výše, tak jej musíte definovat pomocí typedef. Pokud to dělat nechcete, klidně místo stringu použijte pole znaků.

Jazyk Python

Následující úkol pokrývá základní znalosti, ktere byste už měli mít z kurzu Jazyka Python a Algortimů 1.

Ukázka naiviního použití tříd jako struktur.

1. Vytvořte v Pythonu třídu Debtor pro záznam adresáře dlužníků obsahující:
   • jméno dlužníka (name),
   • příjmení dlužníka (surname),
   • věk dlužníka (age),
   • dlužnou částku (debt).
2. Vytvořte adresář dlužníků jako seznam objektů této třídy (data si vymyslete; alespoň pět záznamů).
3. Napište následující funkce:
   • Pro přístup k údajům dlužníka (význam je jasný z názvu):
     • def name(debtor: Debtor) -> str
     • def surname(debtor: Debtor) -> str
     • def age(debtor: Debtor) -> int
     • def debt(debtor: Debtor) -> int
   • Vypisující dlužnou částku na standardní výstup pro zadaný adresář, jméno a příjmení dlužníka:
     • def print_debt(debts: list[Debtor], name: str, surname: str) -> None
   • Vracející dlužníka s největším dluhem (celý objekt) v zadaném adresáři:
     • def max_debt(debts: list[Debtor]) -> Debtor
   • Navyšující dluh zadaného dlužníka o zadanou částku v zadaném adresáři:
     • def increase_debt(debts: list[Debtor], name: str, surname: str, amount: int) -> None
   • Snižující dluh zadaného dlužníka o zadanou částku v zadaném adresáři:
     • def decrease_debt(debts: list[Debtor], name: str, surname: str, amount: int) -> None
   • Vracející i-tého nejmladšího dlužníka pro zadané i a zadaný adresář:
     • def ith_youngest(debts: list[Debtor], i: int) -> Debtor
   • Třídící zadaný adresář vzestupně podle věku dlužníka:
     • def sort_debts(debts: list[Debtor]) -> None