Simulatoare
Descoperă algoritmii prin simulări interactive, ușor de urmărit. Rulează fiecare algoritm pas cu pas și vezi, în același timp, desenul actualizat, linia de cod executată și explicația fiecărei acțiuni. Poți avansa în ritmul tău sau te poți întoarce oricând la pasul anterior. Primul capitol nu e despre algoritmi, ci despre calculatorul însuși: trei jocuri în care îl asamblezi piesă cu piesă, îl repari după semnele pe care le dă și alegi piese care se potrivesc între ele. Toate sunt gratuite și pot fi folosite fără cont.
Calculatorul
Cum arată calculatorul pe dinăuntru: ce piesă ce face, de ce se montează în ordinea asta, ce se strică fără ea și ce piese merg împreună.
Asamblarea calculatorului
Montezi piesele, legi cablurile și pornești. Dacă lipsește ceva, afli chiar de la calculator.
Începe jocul →Detectivul IT: repară calculatorul
Un calculator cu o defecțiune ascunsă: citești semnele, cauți vinovatul și îl repari.
Începe jocul →Alege piesele care se potrivesc
Cumperi piesele unui calculator. Toate sunt bune — dar nu toate merg împreună.
Începe jocul →Sortare, căutare și interclasare
Ce se face cu un tablou unidimensional: ordonarea lui, căutarea unei valori în el și interclasarea a două tablouri deja ordonate.
Algoritmi de sortare
Metoda bulelor, inserția, selecția și numărarea, rulate pe același tablou, cu tabloul după fiecare parcurgere.
Deschide simulatorul →Algoritmi de căutare
Căutarea secvențială și căutarea binară, pe aceeași valoare aleasă de tine, cu codul în C++ și în Python.
Deschide simulatorul →Interclasarea tablourilor
Doi vectori ordonați, interclasați cu doi indici, cu elementele rămase copiate fără comparații.
Deschide simulatorul →Grafuri
Parcurgeri, conexitate, drumuri de cost minim și cicluri speciale.
Parcurgerea grafului (BFS / DFS)
Cele două parcurgeri, în lățime și în adâncime, comparate pe același graf.
Deschide simulatorul →Componente conexe, ciclu și arbore
Cum se determină componentele conexe și cum se recunoaște un ciclu.
Deschide simulatorul →Tare conexitatea grafului
Componentele tare conexe ale unui graf orientat.
Deschide simulatorul →Matricea drumurilor (Roy-Warshall)
Cum se construiește matricea drumurilor, pas cu pas.
Deschide simulatorul →Algoritmul Dijkstra
Drumuri de cost minim dintr-un nod sursă, într-un graf ponderat.
Deschide simulatorul →Algoritmul Roy-Floyd
Drumuri de cost minim între toate perechile de noduri.
Deschide simulatorul →Ciclul hamiltonian
Căutare prin backtracking, cu revenirile din fundături arătate explicit.
Deschide simulatorul →Ciclul eulerian
Condiția de existență și construirea ciclului care trece prin toate muchiile.
Deschide simulatorul →Arbori
Structuri arborescente, de la arborele genealogic la arborii de cost minim.
Arbore cu rădăcină
Tată, fii, nivel și înălțime, pe exemplul arborelui genealogic.
Deschide simulatorul →Arbore binar de căutare
Cum se inserează și cum se caută o valoare într-un arbore binar de căutare.
Deschide simulatorul →Parcurgeri de arbore binar
Preordine, inordine și postordine, comparate pe același arbore.
Deschide simulatorul →Ansamblul (heap)
Cum se reface proprietatea de heap după inserare și după extragere.
Deschide simulatorul →Kruskal — arbore parțial de cost minim
Muchiile luate în ordinea costului, cu evitarea ciclurilor.
Deschide simulatorul →Prim — arbore parțial de cost minim
Arborele crescut dintr-un nod de start, muchie cu muchie.
Deschide simulatorul →Subprograme recursive
Ce se depune pe segmentul de stivă la fiecare apel: parametrii, variabilele locale și adresa de revenire, pe cinci subprograme recursive.
Metode de programare
Backtracking și greedy, pe problemele clasice din programă.
Elemente combinatoriale
Generarea permutărilor, aranjamentelor și combinărilor prin backtracking.
Deschide simulatorul →Problema reginelor
Backtracking clasic: așezarea reginelor care nu se atacă între ele.
Deschide simulatorul →Explorarea labirintului
Cum se caută ieșirea și cum se revine din drumurile înfundate.
Deschide simulatorul →Problema comis-voiajorului
Toate traseele posibile, explorate prin backtracking.
Deschide simulatorul →Problema rucsacului (continuă)
Metoda greedy: obiectele luate în ordinea raportului valoare / greutate.
Deschide simulatorul →Problema spectacolelor
Metoda greedy: cele mai multe spectacole care încap fără suprapunere.
Deschide simulatorul →Programare dinamică și divide et impera
Tehnici de pe programa de liceu, cu tabelul completat pas cu pas.
Căutare binară recursivă
Divide et impera, cu arborele de recursivitate desenat.
Deschide simulatorul →Subșir comun maximal (LCS)
Programare dinamică, cu tabelul completat celulă cu celulă.
Deschide simulatorul →Subșir crescător maximal (LIS)
Programare dinamică, pe cea mai lungă subsecvență crescătoare.
Deschide simulatorul →