NotasAA

Notas de An´alisis de algoritmos
y Estructura de datos
Recopilaci´on
2015-1

´Indice general
I

An´
alisis de Algoritmos

3

1. Introducci´
on
1.1. An´
alisis de algoritmos . . . . . . . . . . . . . . . . . . . . . .
1.1.1. Complejidad Lineal . . . . . . . . . . . . . . . . . . . .
1.1.2. Complejidad cuadr´atica . . . . . . . . . . . . . . . . .
1.1.3. Reglas para calcular el n´
umero deOperaciones Elementales . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.4. Principios . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Tasa de crecimiento u orden de magnitud . . . . . . . . . . .
1.2.1. Cotas de complejidad . . . . . . . . . . . . . . . . . .
1.3. Complejidad recursiva . . . . . . . . . . . . . . . . . . . . . .
1.3.1. Recurrencia homog´enea . . . . . . . . . . . . . . .. .

2

6
. 16
. 20
. 21
.
.
.
.
.
.

25
27
28
30
35
42

Parte I

An´
alisis de Algoritmos

3

Contenido del curso de
An´
alisis de Algoritmos
1 An´
alisis de eficiencia de los algoritmos
a) Cotas Superiores e inferiores.
b) Complejidad promedio.
c) Notaci´
on “O grand”.
2 Algoritmos aritm´eticos y algebraicos
a) Complejidad en tiempo y en espaci´o.
b) Problemas P, NP y NP-completos.
3Algoritmos de b´
usqueda y ordenamiento
a) B´
usqueda lineal y binaria.
b) Ordenamiento directo:selecci´
on e inserci´
on directas.
c) Ordenamiento eficiente:shellsort y quicksort.
4 Algoritmos de gr´
aficas
a) Representaci´on en computadora
b) Obtenci´
on de n´
umero crom´atico
´
c) Arbol generador
d ) N´
umero de Independencia
5 T´ecnicas de dise˜
no de algoritmos
a) Divide y vencer´
as
b)T´ecnicas”glotonas“
4

5
c) Genera y prueba
d ) Vuelta atr´as autom´atica (backtracking)
e) Montecarlo
Material de consulta:
Aho, A., Hopcroft, A. and Ulmann, J. The design and analysis of algorithms. Reading, Mass., Adisson Wesley, 1974.
Baase, S. and Gelder, A. Algoritmos computacionales: introducci´on al
an´
alisis y dise˜
no, Pearson Educaci´on, 2001.
Brassard, G. y Bratley, P. Algor´ıtmica: Concepci´
on yAn´
alisis. Masson
1990.
Manber, U. Introduction to Algorithms – A Creative Approach. Addison
Wesley 1989.
Mark Allen Weiss, Estructuras de Datos y Algoritmos. Addison Wesley
1995.
Sedgewick, R., Flajolet and Gordon P. An Introduction to the Analysis
of Algorithms, Adisson-Wesley, 1996.

Cap´ıtulo 1

Introducci´
on
Definici´
on 1.1 (An´
alisis de algoritmos) Es el estudio te´
orico de losresultados del programa de ordenador y el uso de sus
recursos. Un enfoque particular del rendimiento que estudia como
hacer las cosas r´
apidas.
¿Qu´
e es m´
as importante que el rendimiento?
1. Simplicidad
2. Mantenimiento
3. Costo en la programaci´on
4. Tiempo de programador
5. Estabilidad
6. Robustez
7. Funcionalidad
8. Modularidad
9. La seguridad
10. Escalabilidad relacionada (rendimiento)
¿Por qu´
eestudiamos algoritmos y rendimiento?
Es que a menudo el rendimiento mide la l´ınea entre lo factible y lo inviable. Cuando hay requisitos de tiempo real si no es lo suficientemente r´apido,
simplemente no es funcional. Los algoritmos dan un idioma para hablar sobre
el comportamiento de los programas y es un lenguaje generalizado por las
ciencias de la computaci´
on, es un lenguaje te´orico que seadapta para todos
los practicantes y que forma una idea clara del pensamiento de las cosas.
6

7

Complejidad computacional
“Tan pronto como una m´aquina an´
alitica exista, ser´a necesario guiar el
curso futuro de la ciencia. Siempre que cualquier resultado sea logrado con
su ayuda, tendr´
a lugar la pregunta - ¿De qu´e forma podemos hacer que la
m´aquina obtenga los resultados en el menortiempo posible?”
Charles Babbage, 1864

¿Qu´
e es un algoritmo?
Es un conjunto claramente especificado de instrucciones que deben realizarse para resolver un problema.
Es un procedimiento bien definido que toma un conjunto de valores de
entrada y produce otro como salida. Una serie de pasos que transforma
la entrada dada en la salida.
Es una especificaci´on no ambigua de una secuencia de pasos que...