Combinatorical and Algebraic Structures Seminar
Session details
Date: | 6.10.2009 |
Speaker: | Ľubomíra Balková, FJFI, České vysoké učení technické v Praze |
Title: | Násobíme chytře? |
Abstract: | Máme-li úkol vynásobit dvě přirozená čísla a k dispozici tužku a papír, většina z nás použije algoritmus, který jsme se učili už na základní škole. Přesto ale algoritmů pro násobení existuje velké množství. Na semináři si ukážeme jak algoritmy pro násobení na papíře či z hlavy: přehledné indické násobení, egyptské a ruské násobení založené na binárním rozvoji násobitele, Cauchyovo komplementární násobení využívající zápis čísel pomocí záporných cifer, tak i algoritmy, které zefektivnily počítačové násobení a jeho časovou náročnost snížily z $\mathcal{O}(n^2)$ až na $\mathcal{O}(n(\log n)(\log\log n))$. Tuto moderní éru v násobení velkých čísel odstartovaly zejména Karacubův algoritmus a modulární násobení. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož