Introducció a l'anàlisi i disseny d'algorismes

No és possible construir programes informàtics d'una manera correcta i eficient sense estudiar prèviament els algorismes. Aquest llibre, de caràcter introductori, ens acosta, amb un llenguatge clar, a l'anàlisi i el disseny dels algorismes i, alhora, estableix les bases teòriques perquè l'estudiant puga endinsar-se en altres matèries, tant des del punt de vista teòric com pràctic. L'abundant presència d'algorismes "clàssics" respon a la voluntat dels autors perquè aquests algorismes passen a formar part de la "cultura" i els coneixements "de fonts" de l'estudiant i perquè aquest es plantege els problemes reals corresponents i interioritze el tipus d'anàlisi que condueix a la derivació d'aquests algorismes.

Índex
Pròleg
Símbols utilitzats
Capítol 1. Introducció
1.1 Resolució de problemes en programació
1.1.1 Algorismes i programes
1.1.2 L’estudi dels algorismes i abast d’aquest manual
1.2 Expressió d’algorismes mitjançant pseudocodi
1.2.1 Estructura general
1.2.2 Tipus de dades
1.2.3 Conjunt d’instruccions
1.2.4 Mòduls, paràmetres i recursió
1.2.5 Seguiment de l’execució dels algorismes
1.3 Exercicis
Capítol 2. L’eficiència dels algorismes
2.1 Mesura de la complexitat
2.1.1 Cost temporal i espacial
2.1.2 Concepte de talla d’un problema
2.1.3 Anàlisi mitjançant comptatge de passos
2.2 Anàlisi per casos
2.2.1 Cas millor, pitjor i mitjà
2.2.2 El cost com a variable aleatòria†
2.2.3 Utilització d’una instrucció crítica
2.3 Anàlisi asimptòtica
2.3.1 Definicións
2.3.2 Propietats de les notacions asimptòtiques.
2.3.3 Operacions entre notacions asimptòtiques
2.3.4 Jerarquia de complexitats
2.4 Fites asimptòtiques més usuals
2.5 Exercicis
Capítol 3. Anàlisi d’algorismes recursius
3.1 Introducció.
3.2 Algorismes recursius.
3.2.1 Implementació de la recursió
3.2.2 Tipus de procediments recursius
3.3 L’eficiència dels algorismes recursius. Resolució de recurrències
3.3.1 Desplegament de recurrències.
3.3.2 Mètode de l’equació característica
3.3.3 Transformació de relacions de recurrència
3.3.4 Mètode de la recurrència secundària†
3.3.5 Demostració d’una solució mitjançant inducció
3.4 Complexitat espacial dels algorismes recursius
3.4.1 Arbre de recursió
3.4.2 Estimació del cost espacial
3.5 Exemples
3.6 Exercicis
Capítol 4. Plantejament recursiu de problemes en programació
4.1 Introducció.
4.2 La recursió com a ajut a l’anàlisi.
4.3 Relació entre recursió i inducció
4.3.1 Correcció d’algorismes recursius
4.3.2 Verificació de bucles mitjançant inducció†
4.4 La recursió com a eina de disseny
4.4.1 Introducció a la programació amb esquemes
4.4.2 Un esquema general recursiu
4.4.3 Un exemple conegut: divideix i venceràs (DV)
4.5 Exercicis
Capítol 5. Algorismes d’ordenació
5.1 Introducció
5.2 L’ordenació com a problema algorísmic
5.3 Algorismes directes
5.3.1 Inserció directa
5.3.2 Selecció directa
5.3.3 Intercanvi directe
5.3.4 Millores dels algorismes directes
5.4 Algorismes ràpids
5.4.1 Ordenació per mescla
5.4.2 Ordenació per partició (quicksort)
5.4.3 Anàlisi de l’ordenació per partició
5.4.4 Ordenació basada en monticles.
5.4.5 Comparació dels diferents algorismes ràpids
5.5 Complexitat intrínseca del problema de l’ordenació†
5.5.1 Arbres de decisió
5.5.2 Fites inferiors per al cost
5.5.3 Ordenació en menys de n lg n
5.6 La mediana i altres estadístics d’ordre†
5.7 Comentaris sobre l’ordenació externa
5.8 Exercicis
Capítol 6. Algorismes golafres
6.1 Introducció.
6.2 Esquema general
6.3 L’algorisme de Prim
6.3.1 Construcció incremental de l’arbre d’extensió
6.3.2 Correcció de l’algorisme
6.3.3 Implementacions eficients
6.4 L’algorisme de Kruskal
6.4.1 Plantejament
6.4.2 Correcció de l’algorisme
6.4.3 Implementacions i anàlisi
6.5 L’algorisme de Dijkstra
6.6 Exercicis
Capítol 7. Algorismes de retrocés i exploració
7.1 Introducció.
7.2 Algorismes de retrocés
7.2.1 Esquema general.
7.2.2 Exploració total de l’arbre
7.2.3 Poda de l’arbre de retrocés
7.3 Tècniques d’exploració selectiva†
7.3.1 Recorregut de grafs
7.3.2 Exploració informada
7.3.3 Ramificació i poda
7.4 Exercicis
Capítol 8. Programació dinàmica
8.1 Introducció
8.2 Esquema general
8.3 El principi d’optimalitat
8.4 El problema dels camins mínims
8.5 Exercicis
Bibliografia
Apèndix A. Conceptes matemàtics i notació utilitzada
A.1 Logaritmes
A.2 Funcions terra i sostre
A.3 Sumes i successions.
A.4 Aproximació de sumatoris mitjançant integrals
Apèndix B. Principis d’inducció matemàtica
B.1 Inducció feble
B.2 Principi d’inducció general
Apèndix C. Arbres i grafs
C.1 Definicions bàsiques
C.2 Representació de grafs
C.3 Representació d’arbres
Apèndix D. Tipus de recurrències interessants
D.1 Solucions per a recurrències de tipus divisiu
D.2 Solució per a recurrències de tipus substractiu
Índex de figures
Índex de taules
Índex d’algorismes
Índex analític