bueno, esto es un recopilatorio digital y extendido de las notas que fui tomando en las clases de una materia, estructuras discretas. creo que hasta el momento es mi materia favorita, influyendo en eso lo interesante en si de la materia y lo crack que fue el profe en toda la cursada. hecho por mi para mis compañeros (bañense que el curso huele a tuco).
originalmente tomé nota en un cuaderno haciendo diagramas y ahora voy a dar lo mejor de mi para traducirlo en palabras.
cuando tenemos que desarrollar un sistema informatico, en la gran mayoría de los casos la primer tarea que debemos concretar es la de interpretar las necesidades de nuestro cliente (o jefe) y adaptarlas a funcionalidades que formaran parte del sistema a desarrollar. el lenguaje humano está plagado de ambigüedades y cuestiones no dichas explícitamente, por lo que usarlo para interpretar estas necesidades se vuelve una tarea tediosa. además, usar un lenguaje inexacto y ambigüo va en dirección contraria a lo que debemos proveerle a la computadora, por lo que el lenguaje que necesitamos para tipificar y crear estas funcionalidades debe ser uno que tenga reglas de escritura precisas (sintaxis) y significados fijos (semántica).
los lenguajes que cumplen con esas características son los llamados "lenguajes formales". son estructurados, precisos y libres de ambivalencias, ideales para describir de manera formal los requisitos de nuestro sistema.
los lenguajes formales son absolutamente necesarios para programar. de hecho, todos los lenguajes de programación son lenguajes formales. para que una computadora resuelva un problema, debemos darle una serie de instrucciones detalladas, libres de ambigüedades que le indiquen cómo encarar el problema. al conjunto de instrucciones se le llama "programa" y al acto de crearlos se conoce como "programar".
la matemática suele asociarse solamente con los números. sin embargo, los números son solo una aplicación de un campo particular de la matemática. en la realidad, la matemática es el estudio de estructuras ideales, formales y regulares.
ideales, en el sentido de que están desvinculadas de la realidad. por ejemplo, los matemáticos del área de la geonetría han estudiado círculos perfectos por más de dos mil años, aunque estos no existan en la realidad.
formales, porque tienen un significado bien definido y se pueden analizar de forma inequívoca. si logramos deducir y demostrar que dos círculos se intersectan, esto no puede ser refutado.
regulares, porque pueden describirse de manera compacta. en el caso del círculo, lo podemos definir por un punto (su centro) y una distancia (su radio).
hasta este momento uno puede pensar que las estas estructuras son inútiles fuera de algunas áreas específicas de la matemática. pero todo cobra sentido con el concepto de la abstracción.
la abstracción es el acto de quitar los detalles irrelevantes de un objeto o situación. imaginemos que nos contratan para comprobar si una camioneta puede pasar por todas las tranqueras de un campo. se nos permite tomar las medidas de la camioneta pero tenemos prohibido pasar la camioneta físicamente por las tranqueras. además, tenemos que justificar la situación. una manera en la que podríamos hacerlo sería modelando la camioneta con millones de puntos y probando múltiples ángulos para ver si pasa por las tranqueras.
sin embargo, una solución más inteligente y "pro" sería verificar físicamente si la camioneta cabe dentro de una caja imaginaria de, por ejemplo, dos metros de ancho por dos de alto. Si logramos demostrar con lápiz y papel que todas las tranqueras tienen al menos tres metros de ancho, entonces ya está: por pura lógica, la camioneta pasa.
lo potente de esto es que usamos una caja (un objeto mucho más simple) en lugar de la camioneta real para razonar. eso es la abstracción: quedarnos con lo esencial para poder operar sin volvernos locos con los detalles.
la matemática es gigante, pero en computación no usamos todo. nos centramos en las estructuras discretas. a diferencia de lo que podés ver en Análisis I (donde todo es continuo y suave), acá trabajamos con objetos que varían en "grandes pasos". son elementos separados, bien definidos y, sobre todo, contables. pensalo como la diferencia entre un reloj de agujas (continuo) y uno digital (discreto).
algunos ejemplos de lo que vamos a ver son:
básicamente, estas estructuras nos permiten modelar los objetos artificiales con los que trabajamos: microprocesadores, circuitos digitales y programas. matemática y computación: ¿para qué sirve todo esto?
el profe siempre hace hincapié en que esto no es solo teoría; tiene aplicaciones directas en nuestro laburo como ingenieros:
usar matemática para documentar estos requisitos (especificar formalmente) nos da una precisión que el castellano no tiene, evitando errores que pueden salir carísimos después.
programar es creativo pero también propenso a errores. en la materia usamos haskell, un lenguaje declarativo/funcionañ. en lugar de darle órdenes paso a paso a la compu, definimos propiedades y ecuaciones. es un estilo mucho más cercano a la matemática y, por lo tanto, más fácil de razonar y entender.
dijkstra, un genio de la informática, decía que "las pruebas muestran la presencia de errores, pero no su ausencia". no podés probar un programa con infinitas entradas.
lo que hacemos acá es como lo que hace un ingeniero civil con un puente: no pone 50 autos arriba para ver si se cae; usa las leyes de la física para demostrar que no se va a caer bajo ninguna carga. nosotros usamos la lógica para demostrar que un programa cumple con su especificación sin necesidad de ejecutarlo mil veces.
si tenés que representar el mapa del subte de Buenos Aires o las reglas de un juego de ajedrez, necesitás estructuras de datos complejas. los matemáticos ya estudiaron estas cosas hace años (como la teoría de grafos para el subte). al usar esas definiciones, no solo programamos más rápido, sino que podemos optimizar nuestro código usando propiedades que ya fueron demostradas.
bueno, acá te sigo pasando el limpio de lo que sigue en la guía, manteniendo el estilo de notas de clase y todo en minúsculas como me pediste:
empezamos con lo que ya conocemos de toda la vida: los números. pero el enfoque acá es mirarlos como un sistema formal. esto significa que vamos a hacer explícitas un montón de reglas que antes usábamos sin pensar.
el sistema tiene dos partes clave:
sintaxis: define qué símbolos valen y cómo se combinan para armar expresiones. acá entran las constantes (números), las variables (letras como x, y) y los operadores (+, -, *, /, potencia)
semántica: se ocupa de qué significan esas expresiones. lo importante es distinguir el símbolo (el dibujo del "7") del valor real que representa. por ejemplo, "5+2" y "8-1" son símbolos distintos pero representan el mismo valor: siete
con los números solos no hacemos mucho, así que agregamos relaciones (=, <, ⩽, etc.). cuando juntamos dos expresiones con una relación, armamos una fórmula.
lo loco acá es el cambio de "tipo": mientras que una expresión aritmética te devuelve un número, una fórmula te devuelve un valor booleano (verdadero o falso).
este concepto es clave para entender cómo razona la compu sobre lo que escribimos:
acá es donde la teoría se vuelve código. haskell nos sirve para experimentar con estas ideas matemáticas de forma práctica.
algunos puntos importantes del lenguaje:
tipos de datos: haskell es muy estricto con esto. tenemos int para enteros, float o double para reales (ojo que estos son aproximaciones por el tema del punto flotante), char para caracteres sueltos y string para cadenas.
lenguaje declarativo: a diferencia de otros lenguajes, en haskell un programa es básicamente un conjunto de ecuaciones verdaderas que describen propiedades.
en este paradigma, las funciones son programas. se definen usando tipado funcional, donde especificamos qué entra y qué sale usando la flechita -> (ejemplo: cuadrado :: int -> int)
una función es recursiva cuando se llama a sí misma para resolver un problema. la lógica es siempre la misma:
para que esto funcione, usamos pattern matching (coincidencia de patrones). la compu se fija si lo que le pasamos coincide con la "forma" de alguna de nuestras ecuaciones y ejecuta esa. por ejemplo, para listas, solemos tener un caso para la lista vacía [] y otro para una lista con elementos (x:xs)