ADS2 Jiří Kalvoda: Cvičení 8

Also available as: PDF Markdown

Informace k cv. jsou na https://kam.mff.cuni.cz/~jirikalvoda/vyuka/25z/ads2.

Příští týden se sice přednáška nekoná (Den otevřených dveří), ale cvičení ano!

Fourierova transformace

Fourierův obraz vektoru $x$ je vektor $y$ , kde $y_j = \sum_{k=0}^{n-1} x_k \omega^{jk}$ .

Kde $\omega$ je primitivní $n$ -tá odmocnina z $1$ (v komplexních číslech nebo případně v konečném tělese).

Alternativně lze zobrazení vyjádřit jako násobení maticí, tedy $y=\Omega x$ , kde matice $\Omega_{j,k} = \omega^{j,k}$ (indexujeme-li od 0).

Na přednášce zazněl algoritmus FFT počítající DFT (Diskrétní Fourierovu transformaci) v čase $\O(n \log n)$ pomocí rekurzivního podrozdělování. A také aplikace v podobě násobení polynomů, protože po Fourierově transformaci místo konvoluce stačí sečíst vektory po složkách.

Úloha 1 (Vlastnosti): O jakých vlastnostech vektoru vypovídá nultý a $(n/2)$ -tý koeficient jeho Fourierova obrazu?

Úloha 2 (Obraz kanonické báze): Jak vypadá Fourierův obraz jednotkového vektoru $e_i$ , tedy vektoru, který má jedničku na pozici $i$ a jinde 0?

Úloha 3 (Inverze kanonické báze): Pro každé $i$ najděte vektor, jehož Fourierovým obrazem je $e_i$ . Jak z toho sestrojit inverzní Fourierův obraz?

Úloha 4 (Rotace): Mějme vektor $y$ , který vznikl rotací vektoru $x$ o $k$ pozic, tedy $y_j = x_{(j + k) \bmod n}$ Jak spolu souvisí Fourierovy obrazy $x$ a $y$ ?

Úloha 5 (Odmocniny z jedničky): Kolik existuje $n$ -tých odmocnin jedničky a jak vypadají? Proč jiná čísla nejsou $n$ -tou odmocninou z jedničky? Které z $n$ -tých odmocnin jedničky jsou primitivní?

Úloha 6 (Permutace): Ve Fourierově transformaci máme volnost v tom, jakou primitivní odmocninu $\omega$ si vybereme. Ukažte, že Fourierovy obrazy pro různé volby $\omega$ se liší pouze pořadím složek.

Úloha 7 (Bonus pro milovníky komplexních čísel): Spočítejte druhou mocninu polynomu $x^3 - x^2 - 2x + 2$ pomocí DFT, tedy $(x^3 - x^2 - 2x + 2)^2$ .

Hradlové sítě

Úloha 8 (Enumerace): Jak vypadají všechny booleovské funkce dvou proměnných s jedním bitem výstupu?

Úloha 9 (Úplnost): Dokažte, že každou booleovskou funkci dvou proměnných lze vyjádřit pomocí hradel and, or a not. Proto lze každý booleovský obvod s nejvýše dvouvstupovými hradly upravit tak, aby používal pouze tyto tři typy hradel. Jeho hloubka přitom vzroste pouze konstanta-krát.

Úloha 10 (Minimalismus): A co pomocí nějaké dvojice z hradel and, or a not? Nebo dokonce jen pomocí jednoho z nich? Rozeberte všechny podmnožiny těchto tří hradel a určete (konstrukce nebo důkaz neexistence), jestli pomocí ní lze vyjádřit všechny funkce. Pokud s žádnou jednoprvkovou podmnožinou neuspějete, jde použít nějaké jiné hradlo?