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ă!

Şablonul "return 0; ELSE return 1" (mot-à-mot din Pascal în C)

Pascal | Pascal versus C
2008 dec

Manualul vizează în paralel limbajul Pascal şi limbajul C/C++ (plus… pseudocodul excesiv). Ideea de a viza împreună mai multe limbaje de programare este excelentă, dar "realizarea" ei în acest manual este… "în paralel": programele redate în C/C++ nu sunt altceva în acest manual, decât traduceri mot-à-mot ale programelor Pascal.

Limbajul Pascal nu are o instrucţiune return. Ca urmare, traducerea mot-à-mot a funcţiilor recursive din Pascal în C duce la formulări principial greşite: if(...) return 0; else return 1;


Prev
Next
ALL (396 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

/fromlichess

(R) Computer Art | Decoraţiuni

Aplicaţii şcolare (javaScript)

Sinteze: