momente şi schiţe de informatică şi matematică
To attain knowledge, write. To attain wisdom, rewrite.

Integrarea algoritmului lui Dijkstra

Array | Dijkstra | JSON | graphviz | javaScript | modelare obiectuală | perl
2009 may

De regulă, Algoritmul lui Dijkstra este formulat cu "tablouri paralele": d[] pentru distanţe şi p[] pentru predecesori; acestea trebuie prevăzute în cadrul programului apelant (la nivel global) - fiind folosite inclusiv pentru constituirea rezultatelor finale. Unele limbaje permit însă extinderea obiectelor pe parcursul execuţiei (în sensul adăugării de noi proprietăţi) - ceea ce permite integrarea rezultatelor în structura de date transferată algoritmului de către programul apelant.

Implementarea, de la minimal la eficient

Prim | arbore parțial minimal | javaScript
2009 apr

Manuale versus programator (implementarea unui algoritm de teoria grafurilor)
Povestea arborelui parţial minimal
Implementarea clasică (apoi, folosind o structură priority_queue<double>) a algoritmului lui Prim
Compromisuri între stil şi eficienţă; biblioteci şi interfeţe

Saltul recursiv şi alergarea iterativă

iterativ | javaScript | knight | recursiv
2009 mar

Revenim asupra unor construcţii javaScript din Ambiţiile Cavalerului; vizam drumuri hamiltoniene pe graful săriturii calului - dar poate fi mulţumit Sir Knight? …cavalerii ăştia erau în stare să susţină o cauză până-n pânzele albe.

Cursivitatea recursivităţii (reformulare "tail recursion")
de la 'too much recursion' la formula iterativă

Ambiţiile Cavalerului

Warnsdorff | backtracking | drum hamiltonian | graf | javaScript | knight
2009 feb

demersurile aplicaţiei Knight
      modelarea "problemei calului" (ca graf şi ca obiect de memorie), folosind javaScript
      reprezentarea vizuală a grafului în fereastra browserului
      modelarea căutării unui drum hamiltonian (backtracking)
      backtracking compus cu un algoritm euristic

principiul lui Warnsdorff (1823): continuă pe acel drum din care vei avea cât mai puţine ramificaţii - altfel spus, iterează recomandarea evidentă: dacă ai de ales între a face un ultim pas până la destinaţie şi respectiv a ocoli, atunci încearcă mai întâi prima variantă!

Experimente cu factoriale in javaScript

factorial | javaScript
2008 dec

Câte cifre are n! şi care sunt cifrele iniţiale? Câte cifre zecimale are 22009 şi care sunt primele câteva cifre?
Există n încât n! să aibă n cifre zecimale? Există n încât n! să aibă n cifre hexazecimale?

Modelarea comparativă a calculului factorialelor în bazele 10, 106, 216 (în javaScript).

Cel mai mare număr natural care are Z cifre zecimale este 10Z - 1; cel mai mare număr natural care are T cifre în baza 256 este 256T - 1. Rezultă că Z = T * lg(256) ≈ T * 2.40824, adică:
reprezentarea în baza 256 necesită de minimum 2.4 ori mai puţine "locaţii" decât cea în baza 10, iar operarea bazată pe reprezentarea în baza 256 necesită de 2.4 ori mai puţine operaţii "cifră cu cifră" decât cea bazată pe reprezentarea zecimală obişnuită.


Prev
Next
ALL (386 titluri)

vezi Cărţile mele (de programare)

despre acesta ~ Home
(sau https://vlad.bazon.net/

Factoriale | Graficul funcţiilor

PGN browser | chess JS engine

Load

in /slightchess

/slightchess

626 partide analizate cu Crafty

(R) Computer Art | Decoraţiuni

Aplicaţii şcolare (javaScript)

Sinteze: