1. Nombres de Fibonacci L'algorisme trivial per al càlcul dels nombres de Fibonacci repeteix molts càlculs. Podem evitar-ho desant tots els valors que calculem en una matriu i cercant-los allà quan ens calguin abans de calcular-los un altre cop (memoization). Si només ens cal obtenir un sol nombre de Fibonacci, podem construir una versió iterativa [...]

Classes de problemes – P i NP Entrades Problemes Classes de problemes (no excloents) 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 difícil trobar [...]

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 [...]

Definició i propietats Graf: Graf dirigit (digraf): Un camí de longitud és una seqüència de vèrtexs connectats (per arrestes/arcs) entre ells. Si tots els vèrtexs són diferents, el camí és simple. Un cicle és un camí simple amb la peculiaritat que comença i acaba al mateix vèrtex. El diàmetre d'un graf és el màxim de [...]

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 [...]