Závěrečná úloha
Požadavky na absolvování
Otevřené: pondělí, 8. února 2021, 00.00
Termín: pátek, 14. května 2021, 23.59
Vyřešte alespoň jednu z následujících úloh a odevzdejte:
1. Matice: Máte matici NxN s kladnými a zápornými čísli. Najděte pod-matici mxm, která má největší součet. Viz prříklad:
| 3 | -10 | -6 |
| -1 | 1 | 1 |
| 2 | 5 | 8 |
Součet celé matice je 3. Avšak součet pravého dolního rohu je 15. Jakou má vaše řešení obtížnost časovou a prostorovou?
2. Text V dlouhém textu zkuste najít pro libovolná dvě slova jejich nejmenší vzdálenost na počet slov (např. v 'Ahoj Krabe, řekla ryba' je 'Ahoj' a 'ryba' vzdaleno 2 slova. Dokážete to i napsat, aby to bylo casove narocne O(1)?
3. Graf Navrhněte a napište v čistém Pythonu nový typ - vyvážený binární strom.
Závěrečný termín je jen motivační, lze odevzdávat i potom. Po úloze následuje rozmluva s přednášejícím.