Posts Tagged ‘fib’

Apunts d’Estructures de Dades i Algorismes: Les classes de problemes P i NP

Classes de problemes – P i NP Entrades Problemes Classes de problemes (no excloents) [latex]x[/latex] [latex]\pi[/latex] P Coneixem algorismes amb temps pitjor polinomial (o millor) per a decidir el problema. NP Coneixem algorismes en temps polinòmic indeterminista per a verificar si una solució és correcta. Exemples de problemes que estan en NP: HAM – és […]

Apunts d’Estructures de Dades i Algorismes: Cerca exhaustiva

Cerca exhaustiva La cerca exhaustiva és un mètode de disseny d'algorismes que consisteix en mirar-se sistemàtica i intel·ligentment totes les possibles solucions a un problema donat. Generalment els problemes que es resolen mitjançant aquesta tècnica són problemes d'optimització o combinatoris. La tècnica consisteix en generar implícitament un arbre representant totes les possibles solucions i explorar-lo […]

Apunts d’Estructures de Dades i Algorismes: Grafs

Definició i propietats Graf: [latex]\begin{array}{lll}G: & \small V\grave{e}rtexs/Nodes & V = \{1, 2, 3, 4\} \\ & \small Arestes & E = \left\{\{1, 2\}, \{1, 3\}, \{2, 3\}, \{3, 4\}\right\}\end{array}[/latex] Graf dirigit (digraf): [latex]\begin{array}{lll}G': & \small V\grave{e}rtexs/Nodes & V = \{1, 2, 3, 4\} \\ & \small Arcs & E \subset VxV\ \small (un\ arc\ […]

Apunts d’Estructures de Dades i Algorismes: Diccionaris

Introducció Són un tipus abstracte de dades (TAD), és a dir, un conjunt d'elements i un conjunt d'operacions sobre ells. Un diccionari és un conjunt d'elements amb una clau associada (treta d'un conjunt amb un ordre total definit) amb les operacions de cercar, inserir i esborrar un element. Una estructura de dades és una estructura […]

Apunts d’Estructures de Dades i Algorismes: Dividir i Vèncer

Introducció L'esquema de programació de dividir i vèncer és una tècnica per a resoldre problemes que consisteix en dividir el problema original en subproblemes (més petits), resoldre els subproblemes i finalment combinar les solucions en una sola que resolgui el problema original. Mitjançant aquest tècnica sovint obtenim una solució recursiva. Exemples Cerca dicotòmica: [latex]T(n) = […]

 
Skip to toolbar