pintant…

Em va sorprendre força el dia que, mentre llegia el estudiava/llegia el llibre “Fundamentals of Algorithmics” (Gilles Brassard, Paul Bratley) vaig llegir sobre els “Catalans Numbers”. Sí, hi ha uns nombres que es diuen “Catalans”.

Es diuen catalans gràcies a que Eugène Charles Catalan va descobrir que els nombres catalans estaven connectats amb la parentetització d’expressions i les torrnes de Hanoi. Els nombres catalans en sí ja ja havien estat descoberts per Leonhard Euler al segle XVIII. Sí, Leonhard Euler és el del número “e”!

Al llibre apareixen per l’aplicació de com es poden agrupar varis parèntesis (mantenint la coherència dels parèntesis) si tenim N números. Ho calculen per fer veure al lector que no és viable fer una optimització de forma directe (vaja, que si tenim 15 matrius hi ha 2.674.440 maneres d’agrupar els parèntesis aplicant la propietat associativa, i comptar quin dels 2.6 milions de maneres és millor per fer la multiplicació de matrius és més costòs que no fer altres sistemes que ells descriuen a continuació (compte que no està massa ben explicat aquí).
Al llibre també hi ha un exemple/exercici de quantes maneres es pot connectar pe
r dins un polígon convex (hi ha més informació a l’article de la Wikipedia).

Em va fer força gràcia que hi hagués uns números que siguin “Catalans”. Es pot veure la molt complet article de la Wikipedia que tenen força aplicacions (combinatòria i altres aplicacions pràctiques).

Aquesta entrada fou publicada el dissabte, 10/03/2007 (10:52) i està arxivada dins Carles. Per a seguir els comentaris subscriu-te al fil RSS 2.0. Pots deixar un comentari o fer un retroenllaç des del teu web.