Alg Comp 3nm40 2o. departamental

Sesión 22 (lunes 14/dic/2020): especificaciones hacia el trabajo final

+ Tema visto: especificaciones hacia el trabajo final

+ Acervo: ver las notas en líneas adelante

+ Tarea: ninguna agregada.

+ Notas:

máximo 5 integrantes
tema libre (se sugiere un juego)
fecha: 22 de enero.
se toman cosas de internet citando la fuente y diferenciando claramente el código de Internet, de lo que se modifica o agrega
Para Programación Orientada a Objetos: cualquier lenguaje orientada a objetos, excepto C++.
Para Algoritmos Computacionales: cualquier lenguaje y cualquier paradigma.

¿Para qué sirve la documentación? Ejemplo con una silla.

documentación que traía: como armarla.
¿para qué guardar el documento?

 a) garantía de los primeros días

b) para saber cómo armarla en un futuro

¿Qué van a entregar?

Una portada con el nombre, correo y teléfono de los integrantes en PDF, enviada por correo.

 - hará las veces de índice con las ligas respectivas

Manual de usuario (escrito o video).

  - ¿Cómo de instala para un "usuario común"? ¿Qué funciones tiene? ¿Cómo se opera? ¿Con qué plataformas es compatible?

  - Se sugiere un video, aunque puede ser escrito

  - Se manda la documentación por correo o, en su defecto, una liga en donde visualizarlos.

Manual técnico

  a) ¿Cómo se instala (desde el punto de vista técnico)? ¿Qué requerimientos se necesitan, incluyendo dispositivos adicionales?

  b) entender el sistema para facilitar actualizaciones, mejoras y correcciones (Vg. diagrama de clases). Bitácoras y manejo de errores.

  c) esquema de base de datos o archivos (si es necesario)

  d) código fuente

  - escrito

  - se combina escrito en Word o PDF + código anexo o, en su defecto, una liga en donde visualizarlos.

Historial de construcción del sistema en archivos Word o PDF.

  a) especificación inicial (puede modificarse sobre la marcha).

  b) el diseño preliminar de las pantallas con datos reales (puede modificarse sobre la marcha).

  c) ¿qué pruebas le van a hacer al sistema?

  d) reporte de pruebas del revisor y el usuario final

e) cambios acordados a la idea inicial

Sugerencia:

1.- Tener más de un tema que les guste (al menos dos). Averiguar complejidad y viabilidad.

2.- Hacer un listado de funcionales del "sistema ideal".

3.- Limitarlo a las posibilidades de tiempo disponible.

=> Van a hacer una DEMO de unos minutos en la clase.

Sesión 20 y 21 (lunes 7/dic/2020 y viernes 11/dic/2020): cuadro de complejidad computacional

Tema visto:

   - panorama general de complejidad computacional

Acervo: ejemplos de complejidad computacional
Tarea: ninguna adicional. Preparar código para búsqueda binaria y lineal.
Hipervínculos para autoevaluación.

Sesión 19 (viernes 30/nov/2020): Introducción a búsqueda

Tema visto:

   - autoevaluación

   - introducción a búsqueda

Acervo: explicación del profesor.
Tarea: ninguna adicional. Preparar código para búsqueda binaria y lineal.
Hipervínculos para autoevaluación.

Torres de Hanoi

<a href="https://correoipn-my.sharepoint.com/:x:/g/personal/jlgoytia_ipn_mx/EW1JPMVavvRJhCeaIiXp1ycBaxzgCtj6vnTQYkMrS4u-og?e=F0Pgt7">AC 3NM40 Torres de Hanoi.xlsx</a>

Selección Directa o Burbuja

<a href="https://correoipn-my.sharepoint.com/:x:/g/personal/jlgoytia_ipn_mx/EbTLM4E8Rv5BruYh639MY_0B22uDKpJF-tDIBZyrTpjZGA?e=ji1hye">AC 3NM40 Selección Directa o Burbuja.xlsx</a>

Algoritmos Diversos

<a href="https://correoipn-my.sharepoint.com/:x:/g/personal/jlgoytia_ipn_mx/Eai-1ylMIo1HobglnqPIxW4BkROn7dMNeO0RNAv1G1fKmA?e=loWfBl">AC 3NM40 Algoritmos Diversos.xlsx</a>

+ Notas de la clase:

¿Para qué sirve un ordenamiento?

El ordenamiento por si mismo no sirve para nada.

Excepto...

a) Si se va a buscar

b) Si se quiere una clasificación

Vg. filtros de búsqueda.

Queremos buscar...

a) ¿Qué pasa si no están ordenados?

-> Buscar uno por uno: búsqueda secuencial.

b) ¿Qué sucede cuando están ordenados?

-> Buscar partiendo por mitades: búsqueda binaria.

Búsqueda binaria, que es muy eficiente. Por ejemplo: para mil millones solo se requieren 30 comparaciones. Justo el comportamiento contrario de lo que sucede en Torres de Hanoi.

¿Un Ingeniero en Informática vaa a hacer ordenamientos, búsquedas lineales y binarias?

Estefani) No creo.

Hannia) Sí

Raymundo) Sí.

Sánchez) Sí.

José Luis) Poco probable

¿Ustedes van a trabajar con bases de datos?

Estefani) Sí.

Hannia) Sí.

Raymundo) Sí.

Sánchez) Sí.

José Luis) Casi seguro.

Los índices principales de las bases de datos siempre se mantienen ordenados.

Buscar por una llave primaria es una búsqueda binaria.

Buscar por un campo que no es índice es una búsqueda lineal.

Suponga una tabla con boleta y nombre. La llave primaria es boleta.

// Esta sería una búsqueda binaria

SELECT boleta, nombre

FROM alumnos

WHERE boleta = '2020141857'

// Esta es una búsqueda lineal

SELECT boleta, nombre

FROM alumnos

WHERE nombre = 'Miguel Ángel'

Sesión 18 (viernes 27/nov/2020): Ordenamiento por árbol binario. Estrategia para enfrentar la complejidad computacional

Tema visto:

   - repaso de Quicksort.

   - introducción al ordenamiento por árbol binario balanceado

Acervo complementario: <a href="https://www.cs.usfca.edu/_{galles/visualization/AVLtree.html">https://www.cs.usfca.edu/}galles/visualization/AVLtree.html</a>
Tarea: ninguna adicional.

Sesión 18 (viernes 27/nov/2020): Ordenamiento por árbol binario. Estrategia para enfrentar la complejidad computacional

Tema visto:

   - repaso de Quicksort.

   - introducción al ordenamiento por árbol binario balanceado

Acervo complementario: <a href="https://www.cs.usfca.edu/_{galles/visualization/AVLtree.html">https://www.cs.usfca.edu/}galles/visualization/AVLtree.html</a>
Tarea: ninguna adicional.

Notas de la sesión:

¿Por qué se gana en Quicksort?

Porque es más rápido ordenar dos sublistas que una lista completa.

¿Qué es una instrucción básica?

a) un autoincremenento de una variable

b) una operación

c) una comparación

Ejemplo:

for (i=0; i<5; i++) {

  // tomar dato de un arreglo

  suma = suma + calificación

}

5 veces tomaría el dato de un arreglo

5 veces suma calificación a suma

5 veces incrementaría i

5 veces compararía el valor de i contra 5

1 vez asignaría 0 a i

21 en total

No sumar aquello no equivalente en consumo. Por ejemplo: i++ con un printf(.....

¿Qué hacer cuando descubrimos que una estrategia no va a soportar el volumen?

1.- Llorar, corroborar los cálculos y aceptar la realidad.

   Para corroborar los datos hay que validar y mejorar su precisión.

   Pruebas de estrés.

2.- Buscar cambios de estrategia:

   a) Simplificar la solución o el diseño (Arquitectura de Software)

   b) Mejorar y optimizar el algoritmo (Algoritmos Computacionales)    

   c) Reducir "cuellos de botella" (Vg. pool de conexiones)

   d) Recuperar la experiencia a nivel código y humana

   e) Automizar procesos que se llevan manualmente.

   f) Reorganizar procesos administrativos (Administración)

   g) Mejorar las herramientas utilizadas (IDE, Bases de Datos SQL y nosql, clases, etc.).

   h) Reducir la "deuda técnica" y activar recursos no empleados

   i) Simplificar el requerimiento (Ing. de Requerimientos)

   j) Dar resultados aproximados o reducir precisión (muestreo - Estadística; Heurística - AC o IA).

k) Conducirse con valores éticos y con base en el conocimiento.

Sesión 17 (lunes 23/nov/2020): cómo medir tiempos. ¿Qué es una operación básica?

Tema visto:

   - dudas acerca de cómo medir los tiempos. 

   - ¿Qué debe entenderse como una operación básica?

   - introducción a Quicksort. ¿Cómo trabaja y porqué ahorra tiempo?

Acervo complementario: video Las 4 peores cagadas que he hecho como Ingeniero de Software.
Tarea: ninguna adicional.

Sesión 16 (viernes 20/nov/2020): no hubo sesión por junta para docentes.

Sesión 15 (lunes 16/nov/2020): no hubo sesión por ser día festivo.

Sesión 14 (viernes 13/nov/2020): ¿cuánto tardaría selección directa en ordenar un millón de números?

Tema visto: se resolvió el tema de cuánto tardaría selección directa en ordenar un millón de números. Para eso se tomó el peor de los casos (que en este algoritmo es prácticamente igual al promedio e incluso al mejor).

La función de trabajo es:

a) Intercambios: n-1

b) Comparaciones: (n * n - n) / 2

Nota: en burbuja el número de intercambios es (n * n - n) / 2 para el peor de los casos.

Se tomó como referencia que una PC hace 50 millones de operaciones por segundo, tomado como moda (el dato aproximado más frecuente) directamente de pruebas de los alumnos.

Nota: a manera de verificación, en la PC del profesor se obtuvo el valor de 380,314,000 operaciones básicas / segundo. Debe entender por operación básica una comparación o el incremento de una única variable.

¿Cuántos intercambios habría? 999,999

¿Cuántas comparaciones habría? 499,999,5000,000

#operaciones = #comparaciones + #intercambios * 3 = 500,002,499,997

tiempo en segundos =  500,002,499,997 / 50,000,000 = 10,000 segundos = 166.66 minutos = 2.77 horas

Eso quiere decir que en 5 millones tardaría 69 horas.

En términos prácticos, ¿qué situaciones tienen un volumen de datos equiparable?

El número de movimientos de una nómina de cientos de empleados durante un año.
Es el número de calificaciones de alumnos activos en UPIICSA.
El número de transacciones de un banco grande en unas horas.

Se comentó que los arreglos se "caen" en determinado volumen. Nota; en la PC del profesor, en Dev C++, los arreglos llegaban hasta 518,107; en el 518,108 se "caen". Se ignora la causa.

Tarea: hacer la medición con nuevos algoritmos, según el número de boleta.

0..1 Insertion

2..3 Shell

4..5 Quick3

6..7 Heap

8..9 Merge

Sesión 13 (lunes 9/nov/2020): comparando burbuja vs. selección directa

Tema visto: se expuso el funcionamiento del algoritmo de selección directa y burbuja.

   - Burbuja

    a) mejor caso: n-1 comparaciones y 0 intercambios

    b) promedio: por analizar

    c) peor caso: (n * n - n) / 2, tanto comparaciones como intercambios

  - Selección directa:

    a) todos los casos: (n * n - n) / 2 intercambios

    b) de 0 a n-1 intercambios según el caso

  - Como conclusión: en general es mejor selección directa excepto si nos acercamos al mejor caso. Ambos son de naturaleza cuadrática.

Tarea 1: la misma que ya se había dejado pero se aclara que hay que medirlo para el caso promedio (número al azar), el mejor caso (todos ya están ordenados o casi ordenados) y peor caso (todos o casi todos en orden inverso).

Se sugiere utilizar la siguiente adecuación para reportar el número global de operaciones: 

 Operaciones = comparaciones + intercambios * 3

Tarea 2:

   A. ¿Cuánto tardaría burbuja en el peor caso en ordenar un millón de números tomando como punto de partida las siguientes afirmaciones?

   a) El tiempo consumido será proporcional al número de operaciones. Operaciones = comparaciones + intercambios * 3

   b) Un equipo de cómputo hace 10,000 operaciones por segundo.

   B. ¿Cuánto tardaría su PC personal?

   Sugerencia. Medir las operaciones por segundo con alguna estrategia como la mostrada:

   tiempo inicial

for (i=0, i<=1000000; i++)

     // no hacer nada

tiempo final

Sesión 12 (viernes 6/nov/2020): ¿cómo saber si un algoritmo es eficiente?

Tema visto: como saber si un algoritmo es eficiente. Repaso del concepto de eficiencia, función de trabajo y forma de medirla, así como notación O grande.
Acervo: 18. Cómo saber si un algoritmo es eficiente.
Tarea: medir en una tabla el número de intercambios para selección directa o burbuja. A las boletas pares les tocará selección directa y a las nones burbuja. Como siempre, habrá un revisor. Parar el tiempo cuando el algoritmo tarde más de veinte minutos. Habrá tres casos: mejor caso (en el cual los datos están casi ordenados al inicio), caso promedio (números al azar) y peor caso (en cual los datos están al revés).
Fecha de entrega de la tarea: 13 de noviembre, ya con revisión

#datos        #comparaciones    #intercambios=#c+#i * 3   #operaciones  tiempo

500

5000

50000

500000

Sesión 11 (lunes 1/nov/2020): no hubo sesión por ser día festivo

Sesión 10 (viernes 30/oct/2020): complejidad computacional

Tema visto: introducción a la complejidad computacional
Acervo:

   a) 16. Estructuras_de_datos_CC_BY-SA_3.0 introducción a la complejidad.pdf

   b) 17. C-24 eficiencia en software.pdf

Tarea: ninguna de entrega directa. Estudiar ambos documentos.

Sesión 09 (lunes 26/oct/2020): ¿qué es la función de trabajo?

Tema visto:

    - concepto de función de trabajo

Acervo:

   a) La terrible leyenda de las Torres de Hanoi (el hipervínculo del vídeo está en Megasinapsis).

   b) ¿Cuál es el juego más complicado del mundo? (el hipervínculo del vídeo está en Megasinapsis).

Tarea: ninguna de entrega directa. Conviene estudiar el tema de función de trabajo y ordenamientos.

Sesión 08 (viernes 23/oct/2020): introducción a la función de trabajo

Tema visto:

    - introducción a la complejidad computacional con Torres de Hanoi

Acervo:

   16. ¿Cuántas veces puedes doblar una hoja de papel? (liga a video)

   17. Juguemos Torres de Hanoi (liga a juego de Torres de Hanoi)

Tarea: medir el número de Torres de Hanoi a través de una variable global. Hacer una tabla con ese número de movimientos y medir el tiempo específico de los movimientos. Fecha de entrega: 9/noviembre.

Alg Comp 3nm40 2o. departamental

Attachments