Resumen Final Teórico AED Perez Álvaro 1k5
1
FICHA 13-ALGORITMOS DE ORDENAMIENTOS-------------------------
Ordenamiento de un arreglo unidimensional (Algoritmo: Selección Directa)
Si se desea ordenar el arreglo de menor a mayor usando selección directa, la idea central es la adaptación y
repetición sistemática del simple algoritmo que mostramos a continuación:
Un rápido análisis muestra que el algoritmo anterior recorre el
arreglo buscando el valor menor del mismo, y al terminar lo deja
en la casilla indicada por la variable i (que en este caso vale
cero). Se comienza asumiendo que el menor está en la casilla
cuyo índice es i = 0, y se recorre el resto del arreglo con j
comenzando desde el valor i+1. Cada valor en la casilla j se
compara con el valor en la casilla i. Si el valor en v[i] resulta
mayor que v[j] entonces los valores se intercambian, y así se
prosigue hasta que el ciclo controlado por j termina. Para que se
ordene todo el arreglo y no encuentro solo el menor, hacer que
la variable i modifique su valor con otro ciclo, comenzando desde
cero y terminando antes de llegar a la última casilla (para evitar que j comience valiendo un índice fuera de
rango).
Búsqueda secuencial.
Sirve para los problemas que requieren la busqueda de cierto valor x está contenido o no en un arreglo v de n
componentes. El arreglo está desordenado, o no se sabe nada acerca de su estado, la única forma inmediata de
buscar un valor en él consiste en hacer una búsqueda secuencial: con un ciclo for se comienza con el primer
elemento del arreglo. Si allí se encuentra el valor buscado, se detiene el proceso y se retorna el índice del
componente que contenía al valor. Si se llega al final del arreglo sin encontrar el valor buscado, lo cual ocurrirá
cuando i (la variable de control del ciclo) sea igual al tamaño del arreglo, la función de búsqueda retorna el
valor –1, a modo de indicador para avisar que la búsqueda falló.
Resumen Final Teórico AED Perez Álvaro 1k5
2
Búsqueda binaria.
Se aplica SOLO SI está ordenado el vector, la
eficiencia del método se basa en que se toma
sólo uno de los dos intervalos para buscar al
valor, y el otro se desecha por completo. En la
primera partición, la mitad de los elementos
del arreglo se desechan, en la segunda se
desecha la cuarta parte (o sea, la mitad de la
mitad), y así sucesivamente.
Se aplica usando dos índices izq. y der cuya función es la de marcar dentro del arreglo los límites del intervalo
en donde se buscará el valor, originalmente izq. comienza valiendo 0 y der comienza valiendo n-1 (siendo n la
cantidad de componentes del arreglo). Dentro del intervalo marcado por izq. y der, se toma el elemento
central, cuyo índice c es el promedio de los valores de izq y der, después se verifica si el valor contenido en v[c]
coincide o no con el número buscado. Si coincide, se termina la búsqueda, y se retorna el valor de c para
indicar la posición del número dentro del arreglo. Si no coincide, es entonces cuando se aprovecha que el
arreglo está ordenado de menor a mayor: si el valor buscado x es menor que v[c], entonces si x está en el
arreglo debe estar a la izquierda de v[c] y por lo tanto, el nuevo intervalo de búsqueda debe ir desde el valor
de izq hasta el valor de c-1. Entonces, se ajusta der para que valga el valor c-1, y se repite el proceso descripto.
Si el valor x es mayor que v[c], entonces la situación es la misma pero simétrica hacia la derecha, y debe
ajustarse izq para valer c+1. El proceso continúa hasta que se encuentre el valor (en cuyo caso se retorna el
último valor c calculado), o hasta que el valor de izq se haga mayor que el de der (es decir, hasta que los
índices se crucen), lo cual indicará que ya no quedan intervalos en los que buscar, y por lo tanto el valor x no
estaba en el arreglo (y en este caso, la función que hace la búsqueda retornará el valor –1).
FICHA 16-MATRICES----------------------------------------------------------
Básicamente, un arreglo bidimensional o matriz es un arreglo cuyos elementos están dispuestos en forma de
tabla, con varias filas y columnas. Aquí llamamos filas a las disposiciones horizontales del arreglo, y columnas a
las disposiciones verticales. Para crear una matriz se aplica una expresión de comprensión lo cual es aún más
compacto y eficiente, aunque posiblemente menos claro.
matriz = [[None] * COLUMNAS for f in range(FILAS)]
Notaremos que el ciclo for realiza una iteración de n giros, y en cada uno de esos giros crea una lista de m
elementos None. En este caso no se requiere indicar en qué casillero se asigna la lista de tamaño m que se está
creando: solo se crean n listas de tamaño m, y cada una de ellas se inserta en la lista representada por los
corchetes externos. Cada una llevará un índice desde 0 en adelante, por orden de llegada.
TOTALIZACION POR FIALES Y COLUMNAS.
Se usa para obtener los totales acumulados de cada una de sus filas y/o de cada una de sus columnas.
A medida que se recorre la fila, se recorren los elementos de cada columna en esa misma fila, por ejemplo si
analiza la fila 1, va mostrar los elementos del vendedor #1 y los elementos que serían c11 c12 c13,etc, en este
caso representa la cantidad vendida de cada objeto(de c/columna). Se puede hacer de la misma forma
intercambiando las filas por las columnas como se ve a continuacion.
Resumen Final Teórico AED Perez Álvaro 1k5
3
MATRICES DE CONTEO Y/O ACUMULACION.
Se aplica una matriz para que cada casilla actúe como un contador o como un acumulador (usándolo entonces
como un vector de conteo o un vector de acumulación), también es posible que en ciertas ocasiones se deba
emplear una matriz de contadores o de acumuladores. En algunos problemas se necesita seleccionar un
contador entre muchos posibles, pero esa selección debe hacerse en base a dos variables que actúan como
índices.
Una matriz de conteos es análoga a un vector de conteos, con la diferencia que en la matriz de conteos se
requieren dos índices para seleccionar el casillero que hará las veces de contador.
Cada fila representa un destino de viaje y cada columna
representa una forma de pago. En este programa, la
matriz conteo se crea en la función
count(), y luego para
cada cliente se toma su destino de viaje (del primer
arreglo) y la forma de pago que usó (del segundo
arreglo). Ambos valores se usan como índices para
acceder en forma directa al casillero correspondiente en
la matriz, y se procede a contar en ese casillero
La función display_count() muestra los resultados obtenidos, considerando sólo aquellos casilleros que hayan
quedado con valor diferente de cero.
DIAGONALIZACION DE MATRICES CUADRADAS
La función diagonal() tiene el objetivo de recorrer esa diagonal y contar cada
uno de los casilleros que contenga un cero. Sólo es necesario un ciclo, y
repetir
el índice en los dos pares de corchetes
al acceder a la matriz.
El ciclo para recorrer las filas comenzará colocando la variable f en
cero, y continuará mientras f se mantenga menor que n-1. Y por
otra parte, notemos que en la fila 0 el primer elemento del
triángulo superior está en la columna 1. En la fila 2 el primero está en
la columna 3... Puede verse fácilmente que en cada fila f el primer elemento del triángulo superior se encuentra
en la columna f+1. Por eso, el ciclo que recorra las columnas (con variable de
control c) no debe comenzar desde 0, sino desde f+1, y llegar en todos los
casos hasta la última columna. Si los ciclos se ajustan de esta forma, solo se
recorrerán los elementos que pertenecen al triángulo superior. En la fila 2 el
primero está en la columna 3... Puede verse fácilmente que en cada fila f el
primer elemento del triángulo superior se encuentra en la columna f+1.
La visualización por pantalla de la matriz completa, pero de forma que cada fila
aparezca a renglón seguido de la fila anterior.
Resumen Final Teórico AED Perez Álvaro 1k5
4
Ahora, todas las filas tienen elementos del triángulo inferior,
salvo la primera. El ciclo para barrido de filas debe comenzar
entonces con la variable de control f valiendo 1. Por otra
parte, en la fila 1 el último elemento del triángulo inferior está
en la columna 0. En la fila 2 el último está en la columna 1, y
así sucesivamente: el ciclo que recorra las columnas (con
variable de control c), debe comenzar entonces en 1 y
proseguir mientras c se mantenga menor a f.
FICHA 17-ORDENAMIENTO-------------------------------------------------
ALGORITMOS SIMPLES/DIRECTOS.
Intercambio directo.
La idea esencial del algoritmo es que cada elemento en cada casilla v[i] se compara con el elemento en v[i+1]. Si
este último es menor, se intercambian los contenidos. Se usan dos ciclos anidados para conseguir que incluso
los elementos pequeños ubicados muy atrás, puedan en algún momento llegar a sus posiciones al frente del
arreglo.
Si el arreglo original hubiese sido [2 – 3 – 7 – 5], entonces en la primera pasada el 7 cambiaría con el 5 y dejaría
al arreglo ordenado. Para detectar ese tipo de situaciones, en el algoritmo se agrega una variable a modo de
bandera de corte: si se detecta que en una pasada no hubo ningún intercambio, el ciclo que controla la
cantidad de pasadas se interrumpe antes de llegar a la pasada n-1 y el ordenamiento se da por concluido
Inserción directa.
Se comienza suponiendo que el valor en la casilla v[0] conforma un subconjunto. Y como tiene un solo
elemento, está ordenado. A ese subconjunto lo llamamos un grupo ordenado dentro del arreglo. Se toma v[1] y
se trata de insertar su valor en el grupo ordenado. Si es menor que v[0] se intercambian, y si no, se dejan como
estaban. n ambos casos, el grupo tiene ahora dos elementos y sigue ordenado. Se toma v[2] y se procede igual,
comenzando la comparación contra v[1] (que es el mayor del grupo). Así, también hacen falta n-1 pasadas, de
forma que en cada pasada se inserta un nuevo valor al grupo.
Resumen Final Teórico AED Perez Álvaro 1k5
5
Shellsort.
La idea es lanzar un proceso de ordenamiento por inserción, pero en lugar de hacer que cada valor que entra al
grupo se compare con su vecino inmediato a la izquierda, se comience haciendo primero un reacomodamiento
de forma que cada elemento del arreglo se compare contra elementos ubicados más lejos, a distancias mayores
que uno, y se intercambien elementos a esas distancias. Luego, en pasadas sucesivas, las distancias de
comparación se van acortando y repitiendo el proceso con elementos cada vez más cercanos unos a otros. De
esta forma, se van armando grupos ordenados pero no a distancia uno, sino a distancia h tal que h > 1.
No es simple elegir los valores de los
incrementos decrecientes, y de esa elección
depende muy fuertemente el rendimiento del
algoritmo. En general, digamos que no es
necesario que esos incrementos sean
demasiados: suele bastar con una cantidad de
distancias igual o menor al 10% del tamaño del
arreglo, pero debe asegurarse siempre que la
última sea igual uno, pues de lo contrario no
hay garantía que el arreglo quede ordenado.
Resumen Final Teórico AED Perez Álvaro 1k5
6
Heapsort.
Usando una estructura de datos conocida como grupo de ordenamiento (que no es otra cosa que una cola de
prioridades, pero optimizada en velocidad: los elementos se insertan rápidamente, ordenados de alguna forma,
pero cuando se extrae alguno, se extrae el menor [o el mayor, según las necesidades]) Igual que antes, al
seleccionar el menor (o el mayor) se lo lleva a su lugar final del arreglo. Luego se extrae el siguiente menor (o
mayor), se lo reubica, y así se prosigue hasta terminar de ordenar. Un grupo de ordenamiento es un árbol
binario casi completo (todos los nodos hasta el anteúltimo nivel tienen dos hijos, a excepción de los nodos más
a la derecha en ese nivel que podrían no tener los dos hijos) en el cual el valor de cada nodo es mayor que el
valor de sus dos hijos. La idea es comenzar con todos los elementos del arreglo, y formar un árbol de este tipo,
pero dentro del mismo arreglo, primero se ubica la raíz en el casillero v[0], y luego se hace que para nodo en el
casillero v[i], su hijo izquierdo vaya en v[2*i + 1] y su hijo derecho v[2*i + 2]. Así, el algoritmo Heapsort primero
lanza una fase de armado del grupo, en la cual los elementos del arreglo se reubican para simular el árbol.
Resumen Final Teórico AED Perez Álvaro 1k5
7
Una vez armado el grupo inicial, comienza la segunda fase del algoritmo: Se toma la raíz del árbol (que es el
mayor del grupo), y se lleva al último casillero del arreglo (donde quedará ya ordenado). El valor que estaba en
el último casillero se reinserta en el árbol (que ahora tiene un elemento menos), y se repite este mecanismo,
llevando el nuevo mayor al anteúltimo casillero. Así se continúa, hasta que el árbol quede con sólo un
elemento, que ya estará ordenado en su posición correcta del arreglo.
FICHA 19-PILAS Y COLAS-----------------------------------------------------
Las clases agrupan objetos con propiedades y características en común, por ejemplo (Perros)
Instancia significa crear un objeto a partir de una clase.
Los atributos y métodos son elementos que almacenan datos (diferenciando los objetos dentro de la
misma clase) utilizando variables de instancia.
Estructuras de datos nativas: son tipos de estructuras de datos que el lenguaje aplicado ya dispone para usar,
las estructuras de datos subindicadas, mutables o inmutables, como las tuplas, los rangos, las cadenas y las
listas son ejemplos de estructuras de datos nativas en Python. Las estructuras de datos que el programador
requiere pero el lenguaje no provee se las denominan como estructuras o tipos abstractos. Los registros sí son
estructuras nativas en Python, pero las clases definidas por los programadores son, en cambio, de tipo
abstractos. El proceso llevado a cabo para crear una estructura de tipo abstracto se conoce como
implementación, el paso inicial es designado como mecanismo de abstracción, es el proceso mediando el cual
Resumen Final Teórico AED Perez Álvaro 1k5
8
se intenta captar y aislar la información y el comportamiento esencial de una entidad, elemento u objeto del
dominio de un problema. La información que se usa es una selección simplificada de datos de la realidad, ese
conjunto de datos se considera relevante para el problema estudiado. Una abstracción es también una
simplificación de la realidad. A su vez, el mecanismo de abstracción se descompone en dos aspectos: captar y
aislar los datos relevantes de una entidad del dominio se conoce como abstracción de datos, mientras que el
mecanismo de identificar procesos relevantes se designa como abstracción funcional. Cuando aquí se habla de
datos relevantes y de procesos relevantes se quiere expresar que el programador debe hacer un análisis
detallado de cuáles son los datos que realmente necesita en su programa para representar a una entidad del
enunciado o dominio del problema, y cuales son los procesos o algoritmos que realmente necesita implementar
en su programa para procesar esos datos.
La abstracción de datos se realiza mediante la combinación de estructuras de datos nativas(un registros
agrupando distintos campos) y la abstracción funcional se realiza mediante funciones que luego tomen como
parámetro a variables de los nuevos tipos, o bien mediante funciones que creen y retornen variables de esos
tipos.
PILAS.
Una pila es una estructura lineal (cada elemento tiene un único sucesor y un único antecesor) en la cual los
elementos se organizan de forma tal que uno de ellos se ubica al principio (o al frente o en el tope) de la pila y
los demás se enciman o apilan uno sobre el otro1 a partir del primero en ser insertado (y este queda ubicado al
fondo de la pila). Si un elemento se inserta en una pila, lo hace de forma tal que queda ubicado como el
elemento del frente. El único elemento que puede retirarse directamente con una sola operación, es el
elemento del frente. Las funciones se designan como push() y pop(). Entonces, el último en ser insertado es el
primero en ser retirado, y por lo tanto el primero en ser procesado. Esta forma de procesamiento con
inversión de entradas se conoce como LIFO (iniciales de last in – first out: último en entrar – primero en salir), y
por ello mismo las pilas suelen designarse como estructuras tipo LIFO.
Se ve el segmento de memoria que se conoce como stack segment se comporta como una pila de bloques de
memoria para soportar el esquema de llamadas de funciones que pudiera disparar un programa. La forma más
Resumen Final Teórico AED Perez Álvaro 1k5
9
simple de implementar una pila en un programa, es usar un arreglo unidimensional como soporte. La idea es
que los elementos de la pila se guarden en los casilleros de un arreglo, comenzando desde la posición cero. Los
arreglos unidimensionales en Python son de naturaleza dinámica y pueden aumentar o disminuir su tamaño en
forma directa, mediante una llamada a append() para aumentarlo o al operador del para disminuirlo [2] [3]. Si
el programador decidiera que el frente de la pila estuviese en la casilla 0 en lugar de en la última, entonces
puede agregar un nuevo elemento con un corte de índices(pila[0:0]) en vez de append().
COLAS.
Una cola es una estructura lineal (cada elemento tiene un único antecesor y un único sucesor) en la cual los
elementos se organizan uno detrás del otro. Para insertar un elemento (operación
add()) se hace de forma tal
que el nuevo componente queda último en la cola. Para eliminar un elemento (operación
remove()) sólo puede
eliminarse aquél que está primero. Entonces, como cada elemento que se inserta queda último en la fila y por
ese motivo será también el último en ser retirado, las colas suelen designarse también genéricamente como
estructuras tipo FIFO (por First In – First Out: primero en entrar, primero en salir)
La idea es exactamente la misma que hemos sugerido para las pilas, pero ahora simplemente cambiando la
forma de trabajo de la función de inserción de un elemento para que lo haga en el extremo opuesto al que se
use para retirar un elemento: lo común es que las inserciones se hagan a partir de la última casilla de la derecha
(usando append()) y las eliminaciones se hagan a partir de la primera casilla de la izquierda (usando del).
Resumen Final Teórico AED Perez Álvaro 1k5
10
FICHA 20-ANÁLISIS DE ALGORTIMOS-------------------------------------
Parámetros de eficiencia (factores de medición): son el tiempo de ejecución y el espacio de
memoria usado. Después en las próximas fichas entra el tema de la complejidad aparente del código fuente. El
más usado es el tiempo de ejecución, porque se supone que el espacio de memoria será aproximadamente el
mismo en todos los algoritmos diseñados para ese problema, o que las diferencias serán apenas relevantes.
El análisis comparativo suele centrarse en dos situaciones:
- Caso promedio: cuando se presenta la configuración de datos más común.
-
Peor caso: cuando se presenta la configuración de datos más desfavorable.
Lo que se busca es comparar los rendimientos relativos entre diferentes algoritmos y no medir numérica y
minuciosamente el rendimiento de cada uno.
Notación Big O
El análisis procede (en la medida de lo posible) intentando deducir alguna fórmula o expresión matemática que
permita modelar formalmente el comportamiento del algoritmo en cuanto al tiempo o el espacio empleado.
Para la deducción de esas fórmulas, se parte del tamaño o volumen natural del problema, que suele venir dado
por el número de datos que se deben procesar. Big O es una expresión que nos muestra una cota superior para
el tiempo de ejecución. Esta forma de expresar el rendimiento de un algoritmo se puede aplicar para expresar
el tiempo de ejecución, espacio, o el parámetro que se use.
Describe la complejidad del algoritmo en términos del tamaño de la entrada de datos (n)
independientemente del hardware.
Busca comparar los rendimientos relativos entre los diferentes algoritmos y no tanto poder medir el
tiempo.
Busca deducir alguna fórmula o expresión matemática que permita modelar el comportamiento del
algoritmo en base al parámetro de eficiencia elegido.
Existen fórmulas que ya están definidas que nos permiten describir el comportamiento del algoritmo.
• O(1): Un algoritmo con tiempo de ejecución en el orden de uno (o proporcional a 1), tiene un tiempo de
ejecución constante, sin importar el número de datos n. Esto es claramente lo ideal al diseñar un algoritmo,
pues no importa lo que crezca n, el tiempo de ejecución será siempre el mismo. Un ejemplo claro de una
operación que es O(1) en la práctica, es el acceso directo a un componente de un arreglo: no importa cuántos
elementos tenga el arreglo (o sea, no importa el valor de n), el tiempo para acceder en forma directa a un
componente es siempre el mismo.
Resumen Final Teórico AED Perez Álvaro 1k5
11
• O(log(n)): Un algoritmo cuyo tiempo de ejecución sea del orden del logaritmo de n, será ligeramente más
lento a medida que n sea mayor. Es un orden muy satisfactorio en la práctica, si puede lograrse. Los algoritmos
que generalmente tienen tiempos de orden logarítmico son los que resuelven un problema de gran tamaño
procediendo a transformarlo en uno más pequeño, dividiéndolo por alguna fracción constante. Por ejemplo, el
algoritmo de búsqueda binaria en un arreglo ordenado tiene O(log(n)) en el peor caso.
• O(n): Un algoritmo cuyo tiempo de ejecución es del orden de n (también se dice que su tiempo de ejecución
es lineal), es aquél que para cada elemento de entrada realiza una pequeña cantidad de procesos iguales. Un
caso típico de un algoritmo cuyo orden es lineal, es el de la búsqueda secuencial en un arreglo.
• O(n*log(n)): Se da en algoritmos que resuelven un problema dividiéndolo en pequeños subproblemas,
resolviéndolos en forma independiente y combinando después las soluciones. Esta estrategia se conoce como
divide y vencerás, y será analizada con detalle en lo que resta del curso. El algoritmo de ordenamiento
Quicksort (en el caso promedio) tiene este rendimiento y está basado en la estrategia divide y vencerás.
• O(n2): Un algoritmo con tiempo de ejecución de orden cuadrático, sólo tiene utilidad práctica en problemas
relativamente pequeños (o sea, con n pequeño). El tiempo de ejecución del orden de n2 suele aparecer en
algoritmos que procesan pares de elementos de datos, y la forma típica de estos algoritmos incluye un par de
ciclos anidados. Se mencionó ya que todos los métodos de ordenamiento directos tienen ese tiempo de
ejecución en el peor caso.
• O(n3): Un algoritmo de tiempo de ejecución de orden cúbico tampoco es muy práctico, salvo en casos de
problemas muy pequeños. La forma típica de estos algoritmos incluye tres ciclos anidados. A modo de ejemplo,
es de orden cúbico el tiempo de ejecución del popular algoritmo que permite multiplicar dos matrices entre sí.
• O(2n): Los algoritmos con orden de ejecución exponencial son muy poco útiles en la práctica. Sin embargo,
aparecen con frecuencia en casos de algoritmos del tipo de fuerza bruta, en los que todas las soluciones
posibles son investigadas una por una. Suelen aparecer tiempos de este orden en problemas de optimización
de soluciones, y en esos casos se considera todo un éxito el poder replantear un algoritmo de modo de lograr
tiempos cuadráticos o cúbicos.
Para todo n grande o muy grande, se tiene que: O(1) < O(log(n)) < O(n) < O(n*log(n)) < O(n2) < O(n3) < O(2n)
Resumen Final Teórico AED Perez Álvaro 1k5
12
FICHA 21-Formalización del análisis de algoritmos--------------------
Formalización de la notación Big O.
La notación Big O se usa para indicar un límite superior para el comportamiento esperado de un algoritmo en
cuanto al tiempo de ejecución o el espacio ocupado o algún otro parámetro.
Se intenta determinar la forma de variación de la función f de acuerdo a la variación de otra función g ya
conocida. A partir de cierto punto concreto siempre f será ≤ a la función de la forma c*g(n) (Cuando n tiende a
infinito tienden ser menores o iguales a alguna función de la forma c*g(n)).
La expresión O(g(n)) en realidad está implicando una familia de funciones cuyo comportamiento es
caracterizado por el comportamiento de g.
Lo que importa es lo que pasará para valores grandes o muy grandes de n, que es lo que se conoce como el
comportamiento asintótico de la función.
En ese sentido, la expresión O(g(n)) es lo que se conoce como un orden de complejidad: un conjunto o familia
de funciones que se comportan asintóticamente de la misma forma.
Al expresar una relación de orden en notación Big O, se está indicando una cota superior para el comportamiento de
una función f en términos del comportamiento de la familia de funciones O(g), pero en general el analista buscará la
menor cota superior para f.
Reglas de orden básicas.
En la notación Big O:
• Se puede prescindir de las constantes y quedarse solo con el término o función dominante.
• Cualquier función polinómica en n de grado k, es orden nk.
Análisis Asintótico
No diga que un algoritmo es: O(n³ + n²) en este caso bastará con decir O(n³)
• Las constantes en los exponentes pueden obviarse.
Sea f(n) = 2n+10 y g(n) = 2n → 2n+10 = O(2n)
• la base de los logaritmos puede obviarse, ya que la función logb(n) es O(log2(n)) para cualquier base b > 1.
logb(n) = O(log(n)) [con b > 1]
Consideraciones prácticas.
1. Dado el algoritmo que debe analizar, tenga en claro cuál será el factor de eficiencia que quiere analizar.
2. En ese algoritmo determine con exactitud el tamaño del problema (o volumen de datos a procesar).
3. En el algoritmo analizado, determine claramente cuál es la instrucción crítica que ese algoritmo lleva a
cabo. La instrucción crítica es la instrucción o bloque de instrucciones que se ejecuta más veces a lo
largo de toda la corrida.
4. No es lo mismo realizar un conteo exhaustivo y riguroso de operaciones críticas, que hacer un análisis
asintótico.
Conteo exhaustivo: Trata de expresar una fórmula con toda rigurosidad y detalle de constantes, términos no
dominantes y términos independientes que indique cuántas operaciones críticas se ejecutan exactamente para
un valor dado de n.
Análisis Asintótico: Si ya tiene una expresión de conteo exhaustiva identifique el término dominante en ella, y
limítese a ese término.
- Si la operación crítica (es, por ejemplo, una comparación) y está contenida dentro de dos ciclos
anidados de n iteraciones cada uno, entonces su algoritmo es O(n2).
- Si su algoritmo consta de varios bloques de instrucciones independientes entre sí: su algoritmo tendrá
un tiempo de ejecución en el orden del que corresponda al bloque con mayor tiempo.
- Si todo el algoritmo está compuesto sólo por un bloque de instrucciones de tiempo constante sin ciclos
ni procesos ocultos dentro de una función, entonces todo el algoritmo se ejecuta en tiempo constante
t(n) = O(1)
Resumen Final Teórico AED Perez Álvaro 1k5
13
- Si su algoritmo se basa en tomar un bloque de n datos, dividirlo por 2, aplicar una operación de tiempo
constante y luego procesar sólo una de las mitades de forma de volver a dividirla y continuar así hasta
no poder hacer otra división, entonces su algoritmo ejecuta en tiempo
t(n) = O(log2(n)) que es lo mismo a:
t(n) = O(log(n)) sin importar la base del logaritmo.
FICHA 22-ARCHIVOS----------------------------------------------------------
Archivo: conjunto de datos persistentes (no volátiles), un archivo es una estructura de datos que, en lugar de
almacenarse en memoria principal, se almacena en dispositivos de almacenamiento externo.
Archivo de texto: los bytes del archivo se interpretan como caracteres (ASCII). Si un archivo es de texto también
contiene bytes, pero **se asume** que todos esos bytes representan caracteres que pueden ser visualizados
en pantalla.
Archivos binarios: los bloques de bytes representan cualquier tipo de información, sin importar el formato y
**no se asume** que cada byte representa un carácter.
Quede claro: todos los archivos contienen información representada en binario, y por lo tanto y en ese sentido,
todos los archivos son binarios
m = open (“datos.dat”,”wb”)
m = open ("c:\\documents\\datos.dat", "w")
Modos de apertura:
Resumen Final Teórico AED Perez Álvaro 1k5
14
La función open () es la encargada de abrir el canal de comunicación entre el dispositivo que contiene al archivo
y la memoria principal. Por ese motivo, ese objeto se suele designar como el manejador del archivo. Así como
es necesario abrir un archivo para poder acceder a su contenido, también es necesario cerrarlo, luego de
invocar a close(), la variable u objeto que representaba al archivo (el manejador del archivo) queda indefinida.
Modulo Pickle: aplicado para la serialización y deserialización dump() y load(). La serialización es un proceso
por el cual el contenido de una variable normalmente de estructura compleja se convierte automáticamente en
una secuencia de bytes listos para ser almacenados en un archivo, pero de tal forma que luego esa secuencia de
bytes puede recuperarse desde el archivo y volver a crear con ella la estructura de datos original
import pickle
1. pickle.dump(objeto,via de comunicacion) —> pickle.dump(vec[i],m)
2. #lo cargo al archivo por el canal de comunicacion
3. registro = pickle.load(via de comunicacion) —> reg = pickle.load(m)
4. #lo guardo en variable y lo muestro
5. ------------------------------------------------------------------------
6. def grabar(vec, a, fd): #busca registros que tengan el mismo nombre que a y guarda
7. m = open(fd, "wb")
8. ban = False
9. for i in range(len(vec)):
10. if vec[i].nombre == a:
11. pickle.dump(vec[i], m)
12. ban = True
13. if not ban:
14. print("We couldnt load anything with this author,sorry.")
15. m.close()
16.
17.
18. def mostrarArchivo(fd):
19. if not os.path.exists(fd):
20. print("this file doesnt exists")
21. return
22. m = open(fd, "rb")
23. size = os.path.getsize(fd)
24. c = 0
25. head = "{:<5} | {:<25} | {:<15}"
26. print(head.format("CODIGO", "TITULO", "AUTOR"))
27. while m.tell() < size:
28. reg = pickle.load(m)
29. c += 1
30. print(to_string(reg))
31. m.close()
32. print("Amount of Articles in file:", c)
33. -------------------------------------------------------------------------
34. t = os.path.getsize('libros.dat') print(t)
35. #os.path.getsize() toma como parámetro el nombre físico del archivo
36. #(que aquí suponemos que se llama 'libros.dat', y simplemente retorna su tamaño en bytes
La función pickle.dump() tiene dos parámetros, la primera es la variable cuyos datos se desean grabar, y la
segunda es la variable manejadora del archivo(creada previamente con open()) en el cual se desea grabar el
valor de la variable que entra como primer parámetro. Y la función pickle.load() solo toma un solo parámetro, la
variable manejadora del archivo que se quiere leer, es decir, reconstruye la estructura leída ya sea simple o
compleja y la retorna.
Recorrido secuencial y acceso directo-Archivos binarios.
El sistema operativo es el responsable
de recordar en qué lugar termina un
archivo. Ese punto se conoce como el
final del archivo o end of file. Es
importante notar que los bytes que
siguen al final del archivo no
pertenecen al archivo, pero aun así
están numerados correlativamente. Para obtener el tamaño en bytes del archivo se aplica la función getsize()
del módulo os.path.
t = os.path.getsize('libros.dat')
Resumen Final Teórico AED Perez Álvaro 1k5
15
La función os.path.getsize() toma como parámetro el nombre físico del archivo (que aquí suponemos que se
llama 'libros.dat', y simplemente retorna su tamaño en bytes. Note que no es necesario que el archivo esté
abierto con open() para poder usar esta función.
FILE POINTER: especie de cursor o indicador o marcador interno, se utiliza para un mejor manejo de datos a la
hora de grabar y leer el archivo, sin esta herramienta, el archivo siempre será accedido y recorrido en forma
estrictamente secuencial, comenzando desde el primer byte y avanzado sobre el resto sin saltearse ninguno. El
file pointer es una variable de tipo entero que contiene el número de byte en el cual se realizara la próxima
operación de lectura/grabación. Todo tipo de operación va dejar siempre el file pointer en una ubicación la cual
indica que ahí fue donde terminó de trabajar la misma. El acceso y recorrido en forma secuencial es común y
simple de implementar. Muchos procesos requieren justamente tomar todos los datos de un archivo, uno por
uno en el orden en que aparecen, y procesarlos en ese orden. En ese sentido, los objetos tipo file object
creados con open() contienen un método tell() que retorna el valor del file pointer en forma de un número
entero, y también un método seek() que permite cambiar el valor del mismo (y por lo tanto, seek() permite
elegir cuál será el próximo byte que será leído o grabado). La función tell() es muy útil cuando por algún motivo
se requiere saber en qué byte está posicionado un archivo en un momento dado. Una forma de resolver el
problema, consiste en chequear en cada vuelta del ciclo y antes de invocar a pickle.load() si el valor del file
pointer es menor que el tamaño del archivo. Si el file pointer en un momento dado está apuntando a un byte
cuyo número es menor que el tamaño, entonces el file pointer está posicionado en un byte que pertenece al
archivo y la lectura sería en ese caso válida. Se usa el método tell() para controlar si el valor del file pointer del
archivo gestionado con m es menor que el tamaño en bytes del archivo.
METODO seek(offset,from_what)
En general recibe dos parámetros, offset indica cuantos bytes debe moverse el file pointer, y el segundo indica
desde donde se hace ese salto.
Se no se indica el segundo parámetro al invocar a seek(), se asume por defecto que, si valor es 0, y en ese caso
el reposicionamiento se hará desde el incio del archivo.
Sin importar donde este ubicado el file pointer en este momento, suponga que queremos cambiar su
valor para que pase a valer 10 m.seek(10, io.SEEK_SET)
Sin importar donde esté ubicado el file pointer en este momento, suponga que queremos cambiar su
valor para que salte al final del archivo m.seek(0, io.SEEK_END)
Suponga que el file pointer en este momento está apuntando al byte 7 del archivo (el valor del file
pointer es 7), y suponga que queremos cambiar su valor para que pase a apuntar al byte 4 m.seek(-
3,io.SEEK_CUR)
Importante: Si el segundo parámetro es SEEK_CUR (o sea, 1), se debe asumir que el file pointer
está ubicado en su posición actual (o sea, su valor sería el byte 7 que ya tenía), a ese valor
sumarle el -3 que se pasó como primer parámetro, y asignar el resultado en el file pointer. Como
7 + (-3) = 4, el file pointer pasará a valer 4. Está claro que el ejemplo anterior también podría
haber sido resuelto con
m.seek(4, io.SEEK_SET)
Este documento contiene más páginas...
Descargar Completo
RESUMEN FINAL TEORICO AED 2022.pdf
Estamos procesando este archivo...
Lamentablemente la previsualización de este archivo no está disponible. De todas maneras puedes descargarlo y ver si te es útil.
Descargar
Estamos procesando este archivo...
Lamentablemente la previsualización de este archivo no está disponible. De todas maneras puedes descargarlo y ver si te es útil.