1. The Role of Algorithms in Computing

1.1 Algorithms

Un algoritmo es proceso computacional bien definido que toma algun-algunos valores como ingreso y produce algun valor o serie de valores como una salida en un tiempo especifico Tambien cuenta como una herramienta para resolver un problema comutacional especifico

Problema de ordenado Es fundamental para las ciencias de la computacion existen un gran numero de algoritmos, el mejor algoritmo depende del caso y de el numero de objetos a ordenar, el si ya tienen algo de orden, restricciones del valor la arquitectura del pc, y el almacenamiento que usa

Un algoritmo correcto resuelve el problema y uno incorrecto puede no resolver todo o puede dar valores incorrectos Los incorrectos pueden llegar a ser utiles si puedes controlar el ratio de errores

Que tipo de problema resuelven los algoritmos

Determinar la secuencia de aproximadamente 3 mil millones de pares de bases. Gestión de grandes volúmenes de información en Internet Se emplean métodos para asegurar la privacidad y garantizar autenticidad de la información. Optimización de recursos en empresas Cálculo de rutas óptimas en redes o mapas Compresión de archivos grandes entre otros No todo problema resuelto por algotitmos fue facilmente identiuficado de una serie de soluciones

Estructura de datos

Almacenar y organizar datos en orden para facil acceso y modificacion

Problemas NP-complete

No existe ni se ha identificado un algoritmo eficiente para estos, mucho de estos problemas son similares por lo que si se encuentra la solucion eficiente para uno se encontrara una solucion eficiente para todos

Si demuestras que es un problema NP puedes gastar menos tiempo codificando y centrarte en producir una solucion buena pero no necesariamente la mejor solucion

Modelos alternos de computo

Multicore, un tipo de computacion paralela, "Task-Paralel" la cual toma la ventaja de varios nucleos

Algoritmos que reciben los datos con el tiempo se llaman algoritmo en línea o online algorithms en inles

Ordenar: Clasificar productos en una tienda online por precio.

Distancia más corta: Un robot en una fábrica buscando el trayecto más rápido entre dos máquinas.

1.1-1

Ordenar: Clasificar productos en una tienda online por precio

Distancia mas corta: Buscar la ruta mas rapida entre casa y la universidad 1.1-2

Consumo de batería y Uso del internet

1.1-3

Pilas Colas Listas Enlazadas Árboles y Grafos Ventajas: Ideal para deshacer acciones Desventajas: Solo permite acceso al ultimo elemento

1.1-4

Similitudes: Ambos requieren evaluar rutas y costos Diferencias: El camino mas corto es entre 2 puntos. El TSP visita todos y vuelve al inicio

1.1-5

La mejor: Cirugia asistida por computadora: se requiere precision total. Aproximada basta: Ruta de viaje turístico con lugares opcionales.

1.1-6

Entrega de paquetes. A veces ya se conoce toda la ruta, otras veces, se reciben nuevas direcciones durante el recorrido.

1.2 Algorithms as a technology

Se tiene que hacer algoritmos con Las buenas prácticas de desarrollo de software y utilizar algoritmos que utilicen tiempo y espacio eficientemente

El rendimiento depende tanto del hardware tanto del software

Los algoritmos son el nucleo de mucha de las tecnologias computacionales utilizadas actualmente

Machine learning es utilizado para algoritmos que nosotros como humanos no comprendemos cual seria el algoritmo correcto

1.2-1

Google Maps

Google Maps utiliza varios algoritmos, entre ellos el de Dijkstra, A*, y Pigeon, para calcular rutas, mejorar la relevancia de búsquedas, y estimar el tiempo de viaje

1.2-2

8n² < 64n log₂n

Insertion sort es más rápido para valores de n ≤ 43 aproximadamente.

1.2-3 100n² < 2ⁿ

La solución más pequeña es n = 15.