CourseWare Wiki

courses:b4b33alg:zkouska:teorie_priprava

nemecj38 (nemecj38@undisclosed.example.com) — 2025-02-17T18:53:17+0200

Procvičování k teoretické části Řád růstu funkcí a asymptotická složitost Bez řešení a s řešením Rekurze Bez řešení a s řešením Chyba v řešení 5c) v sekci RECURSION MASTER THEOREM: Správně je $\log_4 n$ protože data se zmenšují čtyřikrát.

courses:b4b33alg:cviceni:00

nemecj38 (nemecj38@undisclosed.example.com) — 2025-02-17T18:36:49+0200

0 - Příprava na složitost Řešené úlohy Uvažování nad kódem Řešená úloha 1: Který fragment programu z následujících dvou proběhne rychleji? (Předpokládáme, že oba běží v identickém SW/HW prostředí.) int n = 100; int sum = 0; for (i = 0; i < n; i++) for (j = 0; j < i; j++) sum += i+j; $\sum_{i=0}^{99} i = 100\frac{99}{2} = 4950 < 5625 = 75^2$$q$$\sum_{i = 1}^{q} a_i = q \frac{a_1 + a_q}{2} $$100$$2000 / 100 = 20$$20$$70 - 20 = 50$$j$$49$$k$$n \times n$$2k$$2n^2$$n^2 / 2$$n(n+1) / 2…

courses:b4b33alg:cviceni:01 - [Další úlohy]

nemecj38 (nemecj38@undisclosed.example.com) — 2025-02-17T18:28:14+0200

1 - Asymptotická složitost Připomenutí teorie Přednáška 1 v oddíle Přednášky “”$f(n) \in \mathrm{O}(g(n)) \Leftrightarrow \exists c > 0, \exists n_0, \forall n > n_0: f(n) \leq c \cdot g(n)$$f(n) \in \Omega(g(n)) \Leftrightarrow \exists c > 0, \exists n_0, \forall n > n_0: f(n) \geq c \cdot g(n)$$f(n) \in \Theta(g(n)) \Leftrightarrow f(n) \in \mathrm{O}(g(n)) \land f(n) \in \Omega(g(n)) $ Vše to jsou množiny! Užitečná pravidla: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$$f(n) \in \mathrm{O…

courses:b4b33alg:cviceni:start - [Cvičení]

nemecj38 (nemecj38@undisclosed.example.com) — 2025-02-17T18:03:20+0200

Rozvrh na FEL Posluchači ALG Odevzdávací systém BRUTE Diskusní fórum Cvičení Zde je přehled cvičení, kvíz (pokud existuje) je čistě dobrovolný, případně může být využit na cvičení. Nahrávky z předchozích let by se vždy měly týkat stejného tématu a obsahovat podobné úlohy, následují ale jiný (předchozí) formát cvičení a potenciálně jiné úlohy. V

courses:b4b33alg:cviceni:10 - [Řešené úlohy]

nemecj38 (nemecj38@undisclosed.example.com) — 2025-02-17T17:47:17+0200

10 - Dynamické programování II Připomenutí teorie Přednášky 10 a 11 v oddíle Přednášky. Nejdelší rostoucí podposloupnost V této úloze nás zajímá sekvence (ne nutně sousedících) prvků v poli, taková, že každý prvek nalevo je menší než každý prvek napravo.$\mathrm{O}(n \log n)$$n$$A \in \mathbb{R}^{r \times m}$$B \in \mathbb{R}^{m \times c}$$A B$$r \cdot m \cdot c$$n$$n-1$$n$$\Theta(n^3)$$n \times n$$n$$k$$h_k$$h_k+1$$k$$p_k$$k$$h_k$$p_k(h_k + 1)$$n$$n$$n$$n$$\Theta(n^3)$$A,B$$m$$n$$m \times…

courses:b4b33alg:cviceni:06 - [Připomenutí teorie]

nemecj38 (nemecj38@undisclosed.example.com) — 2025-02-17T17:44:37+0200

6 - AVL + B-strom Připomenutí teorie Přednáška 6 v oddíle Přednášky. AVL Název je podle autorů (Adelson-Velsky a Landis), nemá význam. AVL udržuje vyváženost stromu a tak zajišťuje logaritmickou složitost operací. Potřeba vyvažovat se zjišťuje z rozdílu hloubek podstromů daného uzlu. Pokud je větší než 1, provádíme rotaci:$k$$2k$$k$$2k + 1$$k$$+1$$k - 1$$k$$(k-1) + 1 + k$$2k$$\left\lfloor \frac{k}{2} \right\rfloor$$u$$u$$\textrm{O}(1)$$\Theta(n)$$u$$1$$2$$\log n$$n$$u$$u$$\Theta(\log n)$$1…

courses:b0b17mtb:lecture_materials - [Course schedule]

adlervik (adlervik@undisclosed.example.com) — 2025-02-16T23:14:14+0200

Lecture materials Timetable The course takes place every Monday (B0B17MTB) from 16:15 to 18:30 in the room T2: A3-412 in Dejvice (unless stated otherwise on the title page). Semester schedule: [ See slide 6 and 7...] List of useful MATLAB functions Course schedule 1st week

courses:b4m33dzo:labs:0_matlab:dzo_00_intro.zip - created

drbohlav (drbohlav@undisclosed.example.com) — 2025-02-13T17:50:46+0200

courses:b4m33dzo:labs:0_matlab:dzo_01_intro.zip - created

drbohlav (drbohlav@undisclosed.example.com) — 2025-02-13T13:12:16+0200

courses:be5b99cpl:lectures:test_cpl_2025-02-13.pdf - created

krajnt1 (krajnt1@undisclosed.example.com) — 2025-02-13T08:56:52+0200

courses:be5b99cpl:lectures:cpl_2025-02-13_test.pdf - created

krajnt1 (krajnt1@undisclosed.example.com) — 2025-02-13T08:55:44+0200

courses:be5b99cpl:lectures:test_cpl_2025-02-13.zip - created

krajnt1 (krajnt1@undisclosed.example.com) — 2025-02-13T08:55:29+0200

courses:b0b33opt:zk4.pdf - created

wernetom (wernetom@undisclosed.example.com) — 2025-02-12T16:56:33+0200

courses:be5b33prg:exam_5.txt - created

nemymila (nemymila@undisclosed.example.com) — 2025-02-12T09:10:20+0200

courses:b4m39rso:lectures:skr.pdf - created

havravla (havravla@undisclosed.example.com) — 2025-02-11T14:29:47+0200

courses:b4m36san:exam_16_1_2025_eng.pdf - created

klema (klema@undisclosed.example.com) — 2025-02-10T15:43:11+0200

courses:b4m36san:exam_16_1_2025.pdf - created

klema (klema@undisclosed.example.com) — 2025-02-10T15:42:56+0200

courses:cgt:cgt_24_25_feb6.pdf - created

votroto1 (votroto1@undisclosed.example.com) — 2025-02-07T22:41:10+0200

courses:b0b33opt:zk3.pdf - created

wernetom (wernetom@undisclosed.example.com) — 2025-02-06T18:43:41+0200

courses:be5b33prg:exam_4.txt - created

nemymila (nemymila@undisclosed.example.com) — 2025-02-05T09:11:13+0200