Závěrečná úloha
Conditions d'achèvement
Ouvert le : lundi 8 février 2021, 00:00
À remettre : vendredi 14 mai 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.