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

==== 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: • b0b36dbs • b0b36prp • b4m01tal • b4b39iur • b4b33rpz • playground

Search

Navigation

Print/export

Tools

QR Code