==== Cvičení TS 2020 ====

Informace ke cvičení, které vede [[http://neuro.felk.cvut.cz/team/#tomas-sieger|Tomáš Sieger]] - [[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B201/public/html/paralelky/C46/84/par4684006.107.html|paralelka 107]].

Řešení domácích úkolů prosím ofoťte a zašlete na [[siegetom@fel.cvut.cz|siegetom@fel.cvut.cz]] do půlnoci z pondělí na úterý následujícícho týdne. 


==== Cvičení 01 -- Asymptotická složitost. Reprezentace grafů. ====

24.9.2020

Prezentace: {{ :courses:b4m33pal:practices:cv01_ts.pdf |}}

Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/84cf11d48b067adbe3a9e7d101f33342f7c8f8e3-1600924801296/84cf11d48b067adbe3a9e7d101f33342f7c8f8e3-1600924801296.pdf|pdf]] 
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=84cf11d48b067adbe3a9e7d101f33342f7c8f8e3-1600924801296|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/84cf11d48b067adbe3a9e7d101f33342f7c8f8e3-1600924801296/84cf11d48b067adbe3a9e7d101f33342f7c8f8e3-1600924801296.mp4|mp4]]

Řešili jsme úlohy 1, 2, 3, 4.

Domácí úkol: dokončit úlohu 2, vyřešit úlohy 5 a 8.


==== Cvičení 02 -- Minimální kostra grafu. ====

1.10.2020

Prezentace: {{ :courses:b4m33pal:practices:cv02_ts.pdf |}}

Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/ca84e2dc2574e59bbde4dad86a8cfbb265216b49-1601529961763/ca84e2dc2574e59bbde4dad86a8cfbb265216b49-1601529961763.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=ca84e2dc2574e59bbde4dad86a8cfbb265216b49-1601529961763|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/ca84e2dc2574e59bbde4dad86a8cfbb265216b49-1601529961763/ca84e2dc2574e59bbde4dad86a8cfbb265216b49-1601529961763.mp4|mp4]]

Řešili jsme úlohy 1, 2.

Domácí úkol: úlohy 3, 4, 9 (ostatní volitelně ;-) ).

==== Cvičení 03 --  Algoritmy pro orientované grafy. ====

8.10.2020

Prezentace: {{ :courses:b4m33pal:practices:cv03_ts.pdf |}}

Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/e1a63a776afef84f58688877853c8e114d67a4ee-1602134701700/e1a63a776afef84f58688877853c8e114d67a4ee-1602134701700.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=e1a63a776afef84f58688877853c8e114d67a4ee-1602134701700|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/e1a63a776afef84f58688877853c8e114d67a4ee-1602134701700/e1a63a776afef84f58688877853c8e114d67a4ee-1602134701700.mp4|mp4]]

Řešili jsme úlohy 3/1, 3/2, 3/4, 3/9.

Domácí úkol: úlohy (3/3), 3/5, 3/6, 3/8 (ostatní volitelně ;-) ).


==== Cvičení 04 --  Haldy. ====

15.10.2020

Prezentace: {{ :courses:b4m33pal:practices:cv04_ts.pdf |}}

Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/0607f459c50bf7c820fa6629beb059be0930793e-1602739502412/0607f459c50bf7c820fa6629beb059be0930793e-1602739502412.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=0607f459c50bf7c820fa6629beb059be0930793e-1602739502412|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/0607f459c50bf7c820fa6629beb059be0930793e-1602739502412/0607f459c50bf7c820fa6629beb059be0930793e-1602739502412.mp4|mp4]]

Řešili jsme úlohy 1, 2, 5.

Domácí úkol: 
  - zkusit sestrojit algoritmus řešící úlohu 3/5 (cesty délky 3) pracující rychleji než v O(n^4)
  - zkusit sestrojit algoritmus pro řešení úlohy 3/8 (homogenní graf)
  - rozmyslet si řešení zbývajících problémů 3/x
  - připravit se na následující cvičení


==== Cvičení 05 --  Izomorfismy obecných grafů a stromů ====

22.10.2020

Prezentace: {{ :courses:b4m33pal:practices:cv05_ts.pdf |}}


Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/eec462a71a1b0e48c8e3fd1f0f6c50adc586e2ec-1603344301950/eec462a71a1b0e48c8e3fd1f0f6c50adc586e2ec-1603344301950.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=eec462a71a1b0e48c8e3fd1f0f6c50adc586e2ec-1603344301950|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/eec462a71a1b0e48c8e3fd1f0f6c50adc586e2ec-1603344301950/eec462a71a1b0e48c8e3fd1f0f6c50adc586e2ec-1603344301950.mp4|mp4]]

Řešili jsme úlohy 4/3, 4/8, 5/1, 5/2, 5/3abc, 5/7ab, 5/8a.

Domácí příprava: 
  - rozmyslet si řešení zbývajících problémů 5/4, 5/6, 5/7d, 5/8cd
  - rozmyslet si, zda platí tvrzení, že každé dva souvislé grafy se stejným počtem vrcholů, kde všechny vrcholy mají stejný stupeň, jsou izomorfní
  - připravit se na následující cvičení

==== Cvičení 06 --  Kombinatorické algoritmy ====

29.10.2020

Prezentace: {{ :courses:b4m33pal:practices:cv06_ts.pdf |}}


Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/91cf3062aafffb40ae5c45ea695bc0c603eaf6b8-1603952701632/91cf3062aafffb40ae5c45ea695bc0c603eaf6b8-1603952701632.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=91cf3062aafffb40ae5c45ea695bc0c603eaf6b8-1603952701632|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/91cf3062aafffb40ae5c45ea695bc0c603eaf6b8-1603952701632/91cf3062aafffb40ae5c45ea695bc0c603eaf6b8-1603952701632.mp4|mp4]]

Řešili jsme úlohy 5/4, 5/7d, 5/8cd, 6/1, 6/2, 6/3, 6/4.

Domácí úkol: 
  - vyřešit úlohy 5/12, 5/6, 6/6 a 6/8 a **řešení zaslat** cvičícímu,
  - rozmyslet si řešení úloh 6/5 a 6/7,
  - připravit se na následující cvičení


==== Cvičení 07 --  Konečné automaty, nedeterminizmus. Regulární výrazy ====

5.11.2020

Prezentace: {{ :courses:b4m33pal:practices:cv07_ts.pdf |}}


Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/3fe22354ffaf45abf8a39c9b20a66b879e03f5ea-1604557501327/3fe22354ffaf45abf8a39c9b20a66b879e03f5ea-1604557501327.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=3fe22354ffaf45abf8a39c9b20a66b879e03f5ea-1604557501327|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/3fe22354ffaf45abf8a39c9b20a66b879e03f5ea-1604557501327/3fe22354ffaf45abf8a39c9b20a66b879e03f5ea-1604557501327.mp4|mp4]]

Řešili jsme úlohy 5/6, 5/12, 6/6, 6/8, 7/1a-e, 7/2a.

Domácí úkol: 
  - vyřešit úlohy 7/2b-d, 7/3a-f, 7/4, 7/5, 7/6, 7/8 a 7/11 **řešení zaslat** cvičícímu,
  - připravit se na následující cvičení


==== Cvičení 08 --  Operace nad jazyky. Přibližné vyhledávánı́ v textu pomocı́ konečných automatů ====

12.11.2020

Prezentace: {{ :courses:b4m33pal:practices:cv08_ts.pdf |}}

Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/6fbb33028373af95cbae79e9f9be5ed66259360b-1605162302058/6fbb33028373af95cbae79e9f9be5ed66259360b-1605162302058.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=6fbb33028373af95cbae79e9f9be5ed66259360b-1605162302058|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/6fbb33028373af95cbae79e9f9be5ed66259360b-1605162302058/6fbb33028373af95cbae79e9f9be5ed66259360b-1605162302058.mp4|mp4]]

Řešili jsme úlohy 7/2b-d, 7/3a-f, 7/4, 7/5, 7/6, 7/8, 7/11 a 8/0.

K příkladu 7/6: 

{{:courses:b4m33pal:practices:7_6.png?400|}}

Domácí úkol: 
  - vyřešit úlohy 8/1, 8/2, 8/3 a 8/12 a **řešení zaslat** cvičícímu,
  - připravit se na následující cvičení


==== Cvičení 09 --  Slovníkové automaty. Implementace automatů ====

19.11.2020

Prezentace: {{ :courses:b4m33pal:practices:cv09_ts.pdf |}}

Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/9fefafb97ce2288e1de395b6141610ed4ba3c791-1605767101871/9fefafb97ce2288e1de395b6141610ed4ba3c791-1605767101871.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=9fefafb97ce2288e1de395b6141610ed4ba3c791-1605767101871|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/9fefafb97ce2288e1de395b6141610ed4ba3c791-1605767101871/9fefafb97ce2288e1de395b6141610ed4ba3c791-1605767101871.mp4|mp4]]

Řešili jsme úlohy 8/1, 8/2, 8/3, 8/12, 8/6, 8/8, 8/4, 8/5, 8/9.

Domácí úkol: 
  - vyřešit úlohy 9/1a, 9/2a a **řešení zaslat** cvičícímu,
  - připravit se na následující cvičení


==== Cvičení 10 --  Náhodná čísla. Prvočísla. Modulární aritmetika. ====

26.11.2020

Prezentace: {{ :courses:b4m33pal:practices:cv10_ts.pdf |}}

Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/4da77887d85545cfec2c7d5335b2bff3a497d13b-1606371902637/4da77887d85545cfec2c7d5335b2bff3a497d13b-1606371902637.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=4da77887d85545cfec2c7d5335b2bff3a497d13b-1606371902637|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/4da77887d85545cfec2c7d5335b2bff3a497d13b-1606371902637/4da77887d85545cfec2c7d5335b2bff3a497d13b-1606371902637.mp4|mp4]]

Řešili jsme úlohy 9/1a, 9/2a, 8/13, 9/5a, 9/3a, 9/4a.

Domácí úkol: 
  - vyřešit úlohy 10/4, 10/5 a 10/6, **řešení zaslat** cvičícímu,
  - připravit se na následující cvičení


==== Cvičení 11 --  Skip list, Vyhledávací stromy: B, B+. ====

3.12.2020

Prezentace: {{ :courses:b4m33pal:practices:cv11_ts.pdf |}}


Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/c770dc198acf3ba0ad42022d903e6ce1aaea69c1-1606976701715/c770dc198acf3ba0ad42022d903e6ce1aaea69c1-1606976701715.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=c770dc198acf3ba0ad42022d903e6ce1aaea69c1-1606976701715|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/c770dc198acf3ba0ad42022d903e6ce1aaea69c1-1606976701715/c770dc198acf3ba0ad42022d903e6ce1aaea69c1-1606976701715.mp4|mp4]]

Řešili jsme úlohy 10/4, 10/5, 10/6, 10/1, (10/2), 10/3, 10/7, 10/11a, 10/12, 10/14.

Domácí úkol: 
  - vyřešit úlohy 10/2, 10/11bc, 11/1 a 11/14 a **řešení zaslat** cvičícímu,
  - připravit se na následující cvičení


==== Cvičení 12 --  Vyhledávací stromy: 2-3-4, R-B, splay. ====

10.12.2020

Prezentace: {{ :courses:b4m33pal:practices:cv12_ts.pdf |}}


Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/dfdc312b71e35109393cb5bb22ecc8915de1b331-1607581502270/dfdc312b71e35109393cb5bb22ecc8915de1b331-1607581502270.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=dfdc312b71e35109393cb5bb22ecc8915de1b331-1607581502270|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/dfdc312b71e35109393cb5bb22ecc8915de1b331-1607581502270/dfdc312b71e35109393cb5bb22ecc8915de1b331-1607581502270.mp4|mp4]]

Řešili jsme úlohy 10/2, 10/11bc, 11/1, 11/14, 11/11, 11/12abc.

Domácí úkol: 
  - vyřešit úlohy 11/12de, 12/1, 12/2 a řešení zaslat cvičícímu **do pondělí**
  - připravit se na následující cvičení


==== Cvičení 13 --  Vyhledávací stromy: (B, AVL, R-B, splay), k-d ====

17.12.2020

Prezentace: {{ :courses:b4m33pal:practices:cv13_ts.pdf |}}

Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/2227095a72600ffad69402ce54ed325863ed9e78-1608186301287/2227095a72600ffad69402ce54ed325863ed9e78-1608186301287.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=2227095a72600ffad69402ce54ed325863ed9e78-1608186301287|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/2227095a72600ffad69402ce54ed325863ed9e78-1608186301287/2227095a72600ffad69402ce54ed325863ed9e78-1608186301287.mp4|mp4]]

Řešili jsme úlohy 11/12de, 12/1, 11/16, 12/4, 12/5, 13/10. 

Domácí úkol: 
  - dořešit úlohu 13/10 (v [[https://bbb04.felk.cvut.cz//presentation/2227095a72600ffad69402ce54ed325863ed9e78-1608186301287/2227095a72600ffad69402ce54ed325863ed9e78-1608186301287.pdf|záznamu ze cvičení]] je přehled bodů v rovině, které chceme do k-d stromu vložit, a část k-d stromu, kterého se nemusíte držet - určitě přijdete sami na jiné (lepší) řešení) a vyřešit navazující 13/13; obojí zaslat cvičícímu **do pondělí** 4.1.

==== Cvičení 14 --  Trie ====

6.1.2021

Prezentace: {{ :courses:b4m33pal:practices:cv14_ts.pdf |}}

Záznam cvičení: 
[[https://bbb04.felk.cvut.cz//presentation/489ad76b674056e79c2ccab9bf98839c06268179-1610000701828/489ad76b674056e79c2ccab9bf98839c06268179-1610000701828.pdf|pdf]]
[[https://bbb04.felk.cvut.cz//playback/presentation/2.0/playback.html?meetingId=489ad76b674056e79c2ccab9bf98839c06268179-1610000701828|záznam v BBB]]
[[https://bbb04.felk.cvut.cz//presentation/489ad76b674056e79c2ccab9bf98839c06268179-1610000701828/489ad76b674056e79c2ccab9bf98839c06268179-1610000701828.mp4|mp4]]

Řešili jsme úlohy 13/10, 13/13, 14/1, 14/2, 14/3.