courses:b4m33pal

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

====== Pokročilá algoritmizace ======

===== Zkouška leden 2025 =====
==== Teoretická část ====
=== 13.1. ===
== Automaty ==

  - Máme jazyk aa*bb*cc* kolik existuje slov délky n 
  - Navrhněte automat bez epsilon přechodu, který přijímá slova s levenshtein vzdálenosti 1, formou grafu 
  - Upravte automat z B), aby mohl vyhledávat v textu, forma tabulky, důvod jestli je deterministický nebo ne

== SCC ==

  - Definujte pojem silně souvislá komponenta grafu G 
  - Rozhodněte, jestli platí: Všechny dvojice SCC v grafu jsou disjunktní (nesdílí hranu, ani vrchol)
  - Navrhněte efektivní algoritmus a určete jeho asymptotickou složitost, který najde všechny dvojice izolovaných SCC (není mezi nimi žádná hrana)

== Generátory ==

  - Mějme LCG, kde je modul roven 10, byl tam jeho výstup, kde byla perioda 4, určete všechny ostatní parametry LCG
  - LCG, M = 36, 1 <= A, C < 36, kolik máme možnosti všech dvojic A,C, aby byla perioda 36 
  - uveďte hodnoty parametrů LCG z B), aby měl periodu 1 a A,C>4 
  - Lehmer generátor, kde byl příklad jeho výstupu zase s nějakou periodou a M=9, určete ostatní parametry

== Grafy ==

  - 2 kružnice, obě o 10 vrcholech, do obou přidejte 2 hrany, aby nebyly izomorfní, odůvodněte proč nejsou izomorfní
  - graf na obrazku neni spravny. hrany jdou z ruznych vrcholu. na druhem obrazku hrany jdou ze stejneho vrcholu.
  - to stejné, ale aby byly izomorfní a kolik izomorfismu existuje
  - Navrhněte algo, který dostane na vstupu 2 kružnice délky n, kde se vložily 2 hrany do každé, a určí, jestli jsou izomorfní 

...Chybí jedna otázka

=== 16.1. ===
== Binomiální haldy == 
  - Vytvořit 2^n-1 haldu a odstranit nejmenší prvek v největším stromě
  - Potom odvození kolik porovnání musíme udělat když máme p stromů
== Automaty ==
  - automat produkuje n krát písmeno c, a druhý má jazyk takový že hammingova vzdálenost od prvního jazyka je max 3, abeceda byla {a,b,c}
== Kruskal, Boruvka, Prim == 
  - na příkladu s kružnicí vysvětlit asymptotické složitosti
== Izomorfismy == 
  - udělat certifikát, udělat dva neizomorfní stromy, a teoretická otázka že pokud v úplném grafu odstraníme 2 hrany, které nesdílí vrchol, a u druhého úplného grafu uděláme to stejný, tak jestli existuje izomorfismus z jednoho do druhého nebo ho tím porušíme.

==== Implementační část ====
{{:courses:13.1.25_impl.webp?direct&400|}}{{:courses:16.1.25-impl1.jpg?direct&400|}}{{:courses:16.1.25-impl2.jpg?direct&400|}}

Trace: • b4b01jag • exams • b4b39iur • b4b33rpz • b0b36dbs • b4m01tal • exams • b0b33opt • b4m35ko • b4m36esw

Search

Navigation

Print/export

Tools

QR Code