Pronto Volveré

Una disculpa por dejar de subir los algoritmos y Diagramas, en mas parte los algoritmos computacionales pero he tenido muchas complicaciones escolares y familiares, no se preocupen pronto volvere, y les traeré mas, no solo algoritmos de preparatoria si no todo lo que se ve en ella.

Esperenlo a mediados del 2016

Algoritmos Computacionales (P.2)

En esta parte analizaremos como usarlos, 

ponerlos en practica y aprobar en 

los exámenes. (Siento tardar tanto en 

subirlo, 

estuve muy ocupado en la escuela)

Analisis:

Recursos De Computadores Y Complejidad

Algoritmo: Conjunto de reglas para resolver un problema. Su ejecución requiere unos recursos.

Un algoritmo es mejor cuantos menos recursos consuma, su facilidad de programarlo, corto, fácil de entender, robusto, etc.

Criterio empresarial: Maximizar la eficiencia.

Eficiencia: Relación entre los recursos consumidos y los productos conseguidos.

Recursos consumidos:

Tiempo de ejecución.

Memoria principal:

Entradas/salidas a disco.

Comunicaciones, procesadores, etc.

Lo que se consigue:

Resolver un problema de forma exacta, forma aproximada o algunos casos.

Recursos consumidos:

Ejemplo. ¿Cuántos recursos de tiempo y memoria consume el siguiente algoritmo sencillo?

i:= 0

a[n+1]:= x

repetir

i:= i + 1

hasta a[i] = x

Respuesta: Depende.

¿De qué depende? De lo que valga n y x, de lo que haya en a, de los tipos de datos, de la máquina...

En general los recursos dependen de:

Factores externos.

El ordenador donde lo ejecutemos: 286, Pentium III, Cray,...

El lenguaje de programación y el compilador usado.

La implementación que haga el programador del algoritmo. En particular, de las estructuras de datos utilizadas.

Tamaño de los datos de entrada.

Ejemplo. Calcular la media de una matriz de NxM.

Contenido de los datos de entrada.

Mejor caso. El contenido favorece una rápida ejecución.

Peor caso. La ejecución más lenta posible.

Caso promedio. Media de todos los posibles contenidos.

Los factores externos no aportan información sobre el algoritmo.

Conclusión: Estudiar la variación del tiempo y la memoria necesitada por un algoritmo respecto al tamaño de la entrada y a los posibles casos, de forma aproximada (y parametrizada).

externos no aportan información sobre el algoritmo.

Normalmente usaremos la notación T(N)=..., pero ¿qué significa T(N)?

Tiempo de ejecución en segundos. T(N) = bN + c.

Suponiendo que b y c son constantes, con los segundos que tardan las operaciones básicas correspondientes.

Instrucciones ejecutadas por el algoritmo. T(N) = 2N + 4.

¿Tardarán todas lo mismo?

Ejecuciones del bucle principal. T(N) = N+1.

¿Cuánto tiempo, cuántas instrucciones,...?

Sabemos que cada ejecución lleva un tiempo constante, luego se diferencia en una constante con los anteriores.

Asignación de tiempos, para el conteo de instrucciones. Algunas reglas básicas.

Operaciones básicas (+, -, *, :=,...): Una unidad de tiempo, o alguna constante.

Operaciones de entrada salida: Otra unidad de tiempo, o una constante diferente.

Bucles FOR: Se pueden expresar como una sumatoria, con los límites del FOR.

IF y CASE: Estudiar lo que puede ocurrir. Mejor caso y peor caso según la condición. ¿Se puede predecir cuándo se cumplirán las condiciones?

Llamadas a procedimientos: Calcular primero los procedimientos que no llaman a otros.

Bucles WHILE y REPEAT: Estudiar lo que puede ocurrir. ¿Existe una cota inferior y superior del número de ejecuciones? ¿Se puede convertir en un FOR?

El análisis de algoritmos también puede ser a posteriori: implementar el algoritmo y contar lo que tarda para distintas entradas.

Ejemplo. Programa “cifras.exe”:

N= 4, T(4)= 0.1 ms

N= 5, T(5)= 5 ms

N= 6, T(6)= 0.2 s

N= 7, T(7)= 10 s

N= 8, T(8)= 3.5 min

¿Qué conclusiones podemos extraer?

Análisis a priori: Evitamos la implementación, si el algoritmo es poco eficiente. Podemos hacer previsiones. Podemos comparar con otros algoritmos.

Medidas Asintoticas

Notación asintótica:

El tiempo de ejecución T(n) está dado en base a unas constantes que dependen de factores externos.

Nos interesa un análisis que sea independiente de esos factores.

Notaciones asintóticas: Indican como crece T, para valores suficientemente grandes (asintóticamente) sin considerar constantes.

O(T): Orden de complejidad de T.

W(T): Orden inferior de T, u omega de T.

Q(T): Orden exacto de T.

Orden de complejidad de f(n): O(f)

Dada una función f: N ® R+, llamamos orden de f al conjunto de todas las funciones de N en R+ acotadas superiormente por un múltiplo real positivo de f, para valores de n suficientemente grandes.

O(f)= { t: N ® R+ / $ c Î R+, $ n0 Î N, " n ³ n0: t(n) £ c" f(n) }

Nota:

O(f) es un conjunto de funciones, no una función.

“Valores de n sufic. Grandes...”: no nos importa lo que pase para valores pequeños.

“Funciones acotadas superiormente por un múltiplo de f...”: nos quitamos las constantes.

La definición es aplicable a cualquier función de N en R, no sólo tiempos de ejec.

Propiedades

P1. Si f Î O(g) y g Î O(h) entonces f Î O(h).

Si f Î W(g) y g Î W(h) entonces f Î W(h)

Ej. 2n+1 Î O(n), n Î O(n2) Þ 2n+1 Î O(n2)

P2. Si f Î O(g) entonces O(f) Í O(g).

¿Cómo es la relación para los W?

P3. Dadas f y g de N en R+, se cumple:

i) O(f) = O(g) Û f Î O(g) y g Î O(f)

ii) O(f) Í O(g) Û f Î O(g)

¿La relación de orden entre O(..) es completa? Dadas f y g, ¿se cumple O(f)ÍO(g) ó O(g)ÍO(f)?

P4. Dadas f y g, de N en R+, O(f+g) = O(max(f, g)).

W(f+g) = W(max(f+g))

¿Y para los Q(f+g)?

¿Es cierto que O(f - g) = O(max(f, -g))?

P5. Dadas f y g de N en R+, se cumple:

i) limn¥® f(n) Î R+ Þ O(f)=O(g), W(f)=W(g), Q(f)=Q(g)

g(n)

ii) limn¥® f(n) = 0 Þ O(f) Í O(g), W(g) Í W(f)

g(n)

P5. Ej. ¿Qué relación hay entre O(log2 n) y O(log10 n)?

P6. Dadas f y g de N en R+, O(f)=O(g) Û Q(f)=Q(g) Û f Î Q(g) Û W(f)=W(g)

P7. Dadas f y g de N en R+, se cumple:

i) limn¥® f(n) Î R+ Þ O(f) = O(g)

g(n)

ii) limn¥® f(n) = 0 Þ O(f) Ì O(g)

g(n)

iii) limn¥® f(n) = +¥ Þ O(f) É O(g)

g(n)

Notación con varios parámetros:

En general, el tiempo y la memoria consumidos pueden depender de muchos parámetros.

f: Nm ® R+ (f: Nx...m..xN ® R+)

Ej. Memoria en una tabla hash. M(B,n, l, k) = kB+l+n+2kn

Orden de complejidad de f(n1, n2, ..., nm): O(f)

Dada una función f: Nm ® R+, llamamos orden de f al conjunto de todas las funciones de Nm en R+ acotadas superiormente por un múltiplo real positivo de f, para valores de (n1, ..., nm) suficientemente grandes.

O(f)= { t: Nm ® R+ / $ c Î R+, $ n1, n2, .., nm Î N, " k1 ³ n1 ,

k2 ³ n2 ,..," km ³ nm : t(k1, k2, ..., km) £ c" f(k1, k2, ..., km) }

De la misma forma, podemos extender los conceptos de W(f) y Q(f), para funciones con varios parámetros.

Las propiedades se siguen cumpliendo ® Demostrarlo.

Ejemplo. T(N) = T(N, a, b) = a" N + b

El tiempo depende del tamaño del problema N, y del tiempo de inicialización b y de ejecución de un paso a.

Podemos suponerlos constantes T(N), o variables T(N,a,b).

¿Qué relación hay entre los siguientes órdenes?

O(n+m), O(nm) O(n2), O(n+2m)

Notaciones condicionales:

En algunos casos interesa estudiar el tiempo sólo para ciertos tamaños de entrada.

Ejemplo. Algoritmo de búsquedaBINARIA: Si N es potencia de 2 el estudio se simplifica.

Orden condicionado de f(n): O(f | P)

Dada una función f: N ® R+, y P: N ® B, llamamos orden de f según P (o condicionado a P) al conjunto:

O(f | P)= { t: N ® R+ / $ c Î R+, $ n0 Î N, " n ³ n0:

P(n) Þ t(n) £ c" f(n) }

De igual forma, tenemos W(f | P) y Q(f | P).

O(f) = O(f | true). Para cualquier f y g, f Î O(g | false).

¿O(f) « O(f | P)?

Ordenes De Complejidad

Uso de los órdenes de complejidad:

Dado un tiempo t(n), encontrar la función f más simple tal que t Î O(f), y que más se aproxime asintóticamente.

Ejemplo. t(n) = 2n2/5 + 3p/2; t(n) Î O(n2).

•

•Relación de orden entre O(..) = Relación de inclusión entre conjuntos.

-O(f) £ O(g) Û O(f) Í O(g) Û Para toda t Î O(f), t Î O(g)

•Se cumple que:

O(c) = O(d), siendo c y d constantes positivas.

O(c) Ì O(n)

O(cn + b) = O(dn + e)

O(p) = O(q), si p y q son polinomios del mismo grado.

O(p) Ì O(q), si p es un polinomio de menor grado que q.

Orden inferior u omega de f(n): W(f):

Dada una función f: N ® R+, llamamos omega de f al conjunto de todas las funciones de N en R+ acotadas inferiormente por un múltiplo real positivo de f, para valores de n suficientemente grandes.

W(f)= { t: N ® R+ / $ c Î R+, $ n0 Î N, " n ³ n0: t(n) ³ c" f(n) }

La notación omega se usa para establecer cotas inferiores del tiempo de ejecución.

Relación de orden: igual que antes.

Orden exacto de f(n): Q(f):

Dada una función f: N ® R+, llamamos orden exacto de f al conjunto de todas las funciones de N en R+ que crecen igual que f, asintóticamente y salvo constantes.

Q(f) = O(f) Ç W(f) =

= { t: N ® R+ / $ c, d Î R+, $ n0 Î N, " n ³ n0: c" f(n) ³ t(n) ³ d" f(n) }

Notación o pequeña de f(n): o(f):

Dada una función f: N ® R+, llamamos o pequeña de f al conjunto de todas las funciones de N en R+ que crecen igual que f asintóticamente:

o(f)= { t: N ® R+ / lim t(n)/f(n) = 1}n¥®

Esta notación conserva las constantes multiplicativas para el término de mayor orden.

Ejemplo. t(n) = amnm + am-1nm-1 + ... +a1n + a0

t(n) Î o(amnm) ¹ o(nm)

¿o(amnm) Í O(amnm)? ¿o(t) Í O(t)?

Costa de complejidad con frecuencia

Algunas relaciones entre órdenes frecuentes:

O(1) Ì O(log n) Ì O(n) Ì O(n" log n) Ì O(n" (log n)2) Ì O(n1.001...) Ì O(n2) Ì O(n3) Ì ... Ì O(2n) Ì O(n!) Ì O(nn)

¿Qué pasa con las omegas? ¿Y con los órdenes exactos?

El orden de un polinomio anxn+...+a1x+a0 es O(xn).

n n n

å1 = n Î O(n); åi = n(n+1)/2 Î O(n2); åim Î O(nm+1)

i=1 i=1 i=1

Si hacemos una operación para n, otra para n/2, n/4, ..., aparecerá un orden logarítmico O(log2 n). Los logaritmos son del mismo orden, independientemente de la base.

Algoritmos Computacionales (P.1)

Antes que nada quiero que sepan que este tema es muy largo y complicado asi que lo voy a dividir en partes para que sea menos complicado

Tips para Algoritmos Computacionales

El programador de computadoras es ante que nada una persona que resuelve problemas, por lo que para llegar a ser un programador eficaz se necesita aprender a resolver problemas de un modo riguroso y sistemático. A la metodología necesaria para resolver problemas mediante programas se denomina Metodología de la Programación. El eje central de esta metodología es el concepto, ya tratado, de algoritmo.

Un algoritmo es un método para resolver un problema. Aunque la popularización del término ha llegado con el advenimiento de la era informática, algoritmo proviene de Mohammed al-Khowarizmi, matemático persa que vivió durante el siglo IX y alcanzo gran reputación por el enunciado de las reglas para sumar, restar, multiplicar y dividir números decimales; La traducción al latín del apellido de la palabra algorismus derivo posteriormente en algoritmo. Euclides, el gran matemático griego (del siglo IV antes de Cristo) que invento un método para encontrar el máximo común divisor de dos números, se considera con Al-Khowarizmi el otro gran padre de la algoritmia (ciencia que trata de los algoritmos).

El profesor Niklaus Wirth, inventor de Pascal, Modula-2 y Oberon, titulo uno de sus más famosos libros, Algoritmos + Estructuras de Datos = Programas, significándonos que solo se puede llegar a realizar un buen programa con el diseño de un algoritmo y una correcta estructura de datos. Esta ecuación será de una de las hipótesis fundamentales consideradas en esta obra.

La resolución de un problema exige el diseño de un algoritmo que resuelva el problema propuesto.

Los pasos para la resolución de un problema son:

Diseño de algoritmo, que describe la secuencia ordenada de pasos que conducen a la solución de un problema dado. (Análisis del problema y desarrollo del algoritmo).

Expresar el algoritmo como un programa de lenguaje de programación adecuado. (Fase de codificación.)

Ejecución y validación del programa por la computadora.

Para llegar a la realización de un programa es necesario el diseño previo de algoritmo, de modo que sin algoritmo no puede existir un programa.

Los algoritmos son independientes tanto del lenguaje de programación en que se expresan como de la computadora que lo ejecuta. En cada problema el algoritmo se puede expresar en un lenguaje diferente de programación y ejecutarse en una computadora distinta; sin embargo, el algoritmo será siempre el mismo. Así, por ejemplo, en una analogía con la vida diaria, una receta de un plato de cocina se puede expresar en español, ingles o francés, pero cualquiera que sea el lenguaje, los pasos para la elaboración del plato se realizaran sin importar el idioma del cocinero.

En la ciencia de la computación y en la programación, los algoritmos son más importantes que los lenguajes de programación o las computadoras. Un lenguaje de programación es tan solo un medio para expresar un algoritmo y una computadora es solo un procesador para ejecutarlo. Tanto el lenguaje de programación como la computadora son los medios para obtener un fin: conseguir que el algoritmo se ejecute y se efectúe el proceso correspondiente.

Dada la importancia del algoritmo en la ciencia de la computación, un aspecto muy importante será el diseño de algoritmos. El diseño de la mayoría de los algoritmos requiere creatividad y conocimientos profundos de la técnica de la programación. En esencia, la solución de un problema se puede expresar mediante un algoritmo.

Características de los Algoritmos:

Las características fundamentales que debe cumplir todo algoritmo son:

ð Un algoritmo debe ser preciso e indicar el orden de realización de cada paso.

ð Un algoritmo debe estar definido. Si se sigue un algoritmo dos veces, se debe obtener el mismo resultado cada vez.

ð Un algoritmo debe ser finito. Si se sigue un algoritmo se debe terminar en algún momento; o sea, debe tener un numero finito de pasos.

La definición de un algoritmo debe definir tres partes: Entrada, Proceso y Salida. En el algoritmo de receta de cocina citado anteriormente se tendrá:

Entrada: ingrediente y utensilios empleados.

Proceso: elaboración de la receta en la cocina.

Salida: terminación del plato (por ejemplo, cordero).

Ejemplo de Algoritmo:

Un cliente ejecuta un pedido a una fábrica. Esta examina en su banco de datos la ficha del cliente; si el cliente es solvente entonces la empresa acepta el pedido; en caso contrario rechazara el pedido. Redactar el algoritmo correspondiente.

Los pasos del algoritmo son:

inicio

leer el pedido

examinar la ficha del cliente

si el cliente es solvente aceptar pedido; en caso contrario, rechazar pedido

fin

Diseño del Algoritmo:

En la etapa de análisis del proceso de programación se determina que hace el programa. En la etapa de diseño se determina como hace el programa la tarea solicitada. Los métodos mas eficaces para el proceso de diseño se basan en el conocido por Divide y Vencerás, es decir, la resolución de un problema complejo se realiza dividiendo el problema en sub- problemas y a continuación dividir estos sub problemas en otros de nivel mas bajo, hasta que pueda ser implementada una solución en la computadora. Este método se conoce técnicamente como diseño descendente (Top Down) o modular. El proceso de romper el problema en cada etapa y expresar cada paso en forma más detallada se denomina refinamiento sucesivo.

Cada sub programa es resuelto mediante un modulo (sub programa) que tiene un solo punto de entrada y un solo punto de salida.

Cualquier programa bien diseñado consta de un programa principal (el modulo de nivel mas alto) que llama a sub programas (módulos de nivel mas bajo) que a su vez pueden llamar a otros sub programas. Los programas estructurados de esta forma se dice que tienen un diseño modular y el método de romper el programa en módulos más pequeño se llama Programación Modular. Los módulos pueden ser planeados, codificados, comprobados y depurados independientemente (incluso por diferentes programadores) y a continuación combinarlos entre si. El proceso implica la ejecución de los siguientes pasos hasta que el programa se termina:

ð programar modulo.

ð Comprobar el modulo.

ð Si es necesario, depurar el modulo.

ð Combinar el modulo con los módulos anteriores.

El proceso que convierte los resultados del análisis del problema en un diseño modular con refinamiento sucesivo que permitan una posterior traducción al lenguaje se denomina diseño de algoritmo.

El diseño del algoritmo es independiente del lenguaje de programación en el que se vaya a codificar posteriormente.

Internet (Navegadores)

(Antes que nada quiero que sepan que puse los navegadores por que es lo que estamos viendo en mi escuela, y quería compartir este trabajo)



Navegador web:

 Es un programa que permite ver la información que contiene una pagina web (Ya se encuentra está alojada en un servidor dentro de la World wid o web en un servidor local).

Funcionabilidad: La comunicación entre el servidor web y el navegador se realiza mediante el protocolo HTTP, aunque la mayoría de los ojeadores soportan otros protocolos como FTP, Gopher, y HTTPS (una versión cifrada de HTTP basada en Secure Socket Layer o Capa de Conexión Segura (SSL)).La comunicación entre el servidor web y el navegador se realiza mediante el protocolo HTTP, aunque la mayoría de los ojeadores soportan otros protocolos como FTP, Gopher, y HTTPS (una versión cifrada de HTTP basada en Secure Socket Layer o Capa de Conexión Segura (SSL).

Caracteristicas: 

*Velocidad   

Se puede decir que un navegador es rápido cuando su inicio desde el escritorio y la carga de los elementos que hay dentro de los sitios Web es instantánea. Estos elementos pueden ser textos, imágenes, videos, contenido interactivo y gráficos avanzados. 

*Seguridad   

¡La protección de tu equipo y tus datos es importante! Un navegador seguro permite identificar, mediante filtros, si un sitio web es fraudulento, si contiene software malintencionado o ha sido simulado para cometer suplantación de identidad, conocido como ‘phishing’ en inglés. Este te brindará alertas antes de descargar archivos contagiados con algún virus informático.

*Privacidad   

Los navegadores deben brindar elementos para que navegues de forma incógnita y así no ser rastreado por los sitios o las páginas web que visitas. Los anunciantes utilizan ‘Cookies’,códigos que recogen la información mientras navegas, y que permiten personalizar los anuncios según tus preferencias de navegación. Muchas páginas web, incluso navegadores, almacenan los datos de navegación como contraseñas, fecha y hora de ingreso a una página (historial),  las descargas que realizas y la información que compartes por la Web.

*Funciones

Aunque algunas funciones vienen predeterminadas en los navegadores, como la función de autocompletar texto que es útil a la hora de realizar una búsqueda o escribir una dirección web, existen unos componentes que enriquecen la experiencia de los navegadores llamados complementos. Con ellos puedes integrar información a la interfaz del navegador según tus necesidades. Por ejemplo, recibir información del tráfico, integrar Twitter sin abrirlo en una nueva ventana o instalar diccionarios y paquetes de idiomas.

*Compatibilidad 

Esta característica es la más técnica de todas pero aún así es importante mencionarla. La compatibilidad está determinada por estándares web y por nuevas tecnologías que son desarrolladas para el mejoramiento de la Internet. Entre estas están la reproducción de vídeos con diferentes codificaciones como la H.264, reproductores de vídeo con tecnología HTML5, entornos gráficos 3D desarrollados por medio de WebGL y sincronización y fidelidad con los dispositivos móviles.

Los Navegadores Web mas usados

Google Chrome: es de los principales navegadores el más joven y el más popular actualmente.

• Navegador minimalista, es decir posee las funciones esenciales y básicas por lo que es ideal para personas con poco dominio en la navegación web.

• Es el navegador más favorecido a la hora de hacer una búsqueda web, solo es necesario escribir la palabra o termino de búsqueda en la barra de direcciones que es multiuso.

•Ofrece similar a Internet Explorer la opción de navegar en forma de Incognito, las páginas a las que se accedan no quedarán registradas en el historial del navegador ni en el historial de búsquedas, y tampoco dejarán otros rastros en el equipo (como cookies).

Internet Explorer:El navegador más utilizado tradicionalmente en internet. Es un complemento indispensable y por defecto del sistema operativo Windows, gracias al cual ha logrado su alto nivel de uso.

• Brinda un elevado nivel de seguridad, que a veces llega a ser desesperante pero muy efectivo, posee distintos niveles de seguridad dividido en zonas cada una con sus limitaciones.

• Compatible con paginas HTA, formato de páginas web que permiten interactuar con programas y archivos del equipo donde se ejecuten.

─ No muestra la página web hasta que no finalice de cargar todos sus elementos.

─ Imposibilidad de acceder a mucho contenido multimedia en la red por exceso de seguridad.

Mozilla Firefox: Indiscutiblemente, es el navegador más popular de la red.

Mozilla Firefox, o simplemente Firefox es un navegador web libre y de código abierto desarrollado por Mozilla, una comunidad global que trabaja junta para mantener una Web Abierta, pública y accesible. 

Firefox ha revolucionado la forma de pensar y mantenido la innovación en la web, para llevar a sus usuarios una mejor experiencia.

Entre sus méritos está el de ser uno de los proyectos de Software Libre más importantes del mundo y poseer el récord Guinness al software más descargado en 24 horas, con 8 millones de descargas (17-06-2008). 

Safari: Es el complemento indispensable para los usuarios de Mac OS X, para donde fue ideado inicialmente que iba a ejecutarse y donde están la gran mayoría de usuarios que lo utilizan dentro de alrededor del 4% de usuarios en el mundo. Es un navegador que se ha distinguido por su desempeño, velocidad y soporte de los estándares. Aunque Safari no es tan reconocido para usuarios de otros sistemas operativos diferentes a Mac OS, se ha vuelto una opción interesante desde que salió su versión para Windows.

Es el navegador predeterminado de todos los iDevice (iPhone, iTouch y iPad), pero es usado también en varios teléfonos y otros dispositivos portables que no son de Apple, por lo que es actualmente el navegador más utilizado en los móviles.

Opera:Es reconocido por su velocidad, seguridad, soporte de estándares (especialmente CSS), tamaño reducido y constante innovación. 

Implementó ya desde sus primeras versiones la navegación por pestañas, el Speed Dial, los movimientos del ratón en la navegación, personalización por sitio, y la vista en miniatura por pestaña, tiene su versión para móviles y tabletas.

Las últimas versiones de Opera usa el motor WebKit, el mismo que Chrome y Safari.

Usa un nuevo diseño, bastante más limpio.

Gracias por la atención