Clase 02

Inicio de la Segunda Clase del Curso

Repaso de la Clase Anterior

• Se inicia la clase recordando palabras clave de la sesión anterior, como "proceso", "acto", "acción", "paciente", "agente" y "algoritmo".

• Se discute la diferencia entre algoritmos determinísticos y no determinísticos, así como conceptos de especificación, precondiciones y postcondiciones.

• Se recuerda un ejemplo específico sobre tres variables enteras: A, B y C.

Especificaciones en Algoritmos

• Se menciona un predicado que restringe el espacio a una condición inicial donde A es distinto de C.

• La importancia del tiempo en computación se destaca; a diferencia de las matemáticas, donde todo es estático, en computación el tiempo afecta los valores referenciados por las variables.

• Si no se establece que ciertas variables son constantes durante la ejecución del algoritmo, pueden cambiar su valor inesperadamente.

Constantes vs. Variables

• Al definir constantes (A, B y C), se asegura que solo D puede ser modificado por el agente actuante.

• Se aclara que si se permite que A, B y C sean variables, sus valores pueden cambiar al final del algoritmo.

Precondiciones y Postcondiciones

• La discusión incluye cómo indicar que ciertos valores son constantes mediante letras mayúsculas para representar los valores iniciales antes de ejecutar el algoritmo.

• Las precondiciones deben reflejar correctamente los estados iniciales para asegurar la validez del algoritmo.

Definición de Variables y Estructuras Matemáticas

Importancia de las Estructuras Matemáticas

• Se enfatiza que no hay que temer al uso de matemáticas en computación; estas son fundamentales para soportar conceptos ingenieriles similares a otras disciplinas técnicas.

Concepto Intuitivo de Conjuntos

• El instructor pregunta sobre el concepto intuitivo de un conjunto; se define como una colección o grupo de elementos.

Conjuntos y Relaciones en Matemáticas

Definición de Conjuntos

• No hay un orden establecido entre los elementos de un conjunto; cada elemento es único y no se repite.

• Un conjunto puede definirse por extensión, donde se enumeran todos sus elementos, como en el caso del conjunto 2, 3, 6.

• Para conjuntos infinitos, se utiliza la definición por comprensión, que describe las propiedades que deben cumplir los elementos para pertenecer al conjunto.

Cardinalidad y Pares Ordenados

• La cardinalidad de un conjunto es el número total de elementos que contiene; por ejemplo, un conjunto con cuatro elementos tiene cardinalidad igual a cuatro.

• Se introducen pares ordenados y tuplas como conceptos fundamentales en matemáticas discretas.

• El producto cartesiano de dos conjuntos A y B se define como el conjunto de todos los pares ordenados (a,b), donde 'a' pertenece a A y 'b' pertenece a B.

Ejemplo del Producto Cartesiano

• Si A = 1, 2 y B = 3, 4, 5, el producto cartesiano A x B incluye todos los pares posibles: (1,3), (1,4), (1,5), (2,3), (2,4), (2,5).

• En este caso específico hay seis pares ordenados resultantes del producto cartesiano.

Introducción a Relaciones

• Una relación entre dos conjuntos A y B implica establecer asociaciones entre sus elementos.

• Se presenta un ejemplo práctico utilizando objetos cotidianos para ilustrar cómo se pueden relacionar diferentes elementos entre sí.

Modelado Matemático de Relaciones

• Las relaciones pueden representarse gráficamente mediante flechas que conectan los elementos de un conjunto con otro.

• Gráficamente, una relación puede ser vista como un subconjunto del plano cartesiano formado por puntos que representan las asociaciones establecidas.

Relaciones y Funciones en Matemáticas

Conceptos Básicos de Relaciones

• La relación "todos contra todos" se describe como un subconjunto del plano A por B, donde cada elemento está relacionado con todos los demás.

• Es fundamental entender la conexión intuitiva detrás de las estructuras matemáticas para facilitar la memoria y el aprendizaje.

Definición de Función

• Una relación R de A a B se define como un subconjunto. La diferencia clave entre una relación y una función es que en una función, cada elemento tiene una única imagen relacionada.

• Se introduce el concepto histórico de funciones al modelar la relación entre tiempo y posición en física, esencial para describir el movimiento de partículas.

Restricciones en Funciones

• Las funciones deben tener un único valor asociado a cada entrada; si hay múltiples flechas desde un mismo punto, esto indica que la partícula estaría en dos lugares simultáneamente.

• Newton estableció que todo elemento del dominio debe tener una imagen para evitar situaciones donde un objeto desaparece temporalmente.

Diferencias entre Matemáticas y Computación

• En matemáticas, se considera que las funciones son totales a menos que se especifique lo contrario; mientras que en computación, generalmente se habla de funciones parciales sin aclarar su naturaleza total.

• Este enfoque puede causar confusión; por ello, el curso adoptará la terminología matemática estándar para evitar malentendidos.

Reflexión sobre Agente y Paciente

• Se propone ver un proceso completo como una acción única que transforma el estado inicial del paciente a uno final.

• La acción puede ser vista como una función donde el dominio representa los estados posibles del paciente y el rango los estados resultantes tras la acción.

¿Cómo se define un algoritmo y su relación con el determinismo?

Conceptos de Precondición y Estado

• Se discute la importancia de restringir el universo de posibles estados del paciente mediante precondiciones para que las acciones en un algoritmo tengan efecto definido.

• Se plantea la cuestión del no determinismo, donde una acción puede llevar a diferentes estados (A o B), enfatizando que solo uno ocurre a la vez.

Relación entre Espacios de Estado

• Una acción no determinística se describe como una relación entre el espacio de estado del paciente y los dominios/rangos asociados.

• La restricción tanto del dominio como del rango es fundamental para entender cómo funcionan estas relaciones en algoritmos.

Introducción al Lenguaje GCL para Algoritmos

Estructura General de un Algoritmo

• Se presenta GCL, un lenguaje diseñado por Daist para estandarizar la escritura de algoritmos, destacando su relevancia en la computación moderna.

• El esquema general incluye declarar variables y definir listas, utilizando símbolos específicos para indicar estructuras dentro del algoritmo.

Tipos de Datos y Predicados

• Se introduce el concepto de tipo de dato como fundamental para definir algoritmos, mencionando que puede haber listas compuestas por diferentes tipos.

• La estructura conocida como tripleta (precondición, acciones, condición final) es esencial en la formulación de algoritmos.

Diferencias entre Pseudolenguaje y Lenguaje de Programación

Definición y Ejecución

• Un pseudolenguaje se refiere a descripciones teóricas sin implementación directa; cuando hay intérpretes reales, se convierte en lenguaje de programación.

• En lenguajes de programación, las "acciones" son referidas como "instrucciones", lo cual marca una diferencia clave respecto al pseudolenguaje.

Popularidad e Implementaciones

• Aunque existen intérpretes para GCL, su baja popularidad lleva a considerarlo más como pseudolenguaje debido al desconocimiento general sobre sus implementaciones.

Tipos de Datos y Algoritmos en Programación

Introducción a GCL y Python

• El presentador menciona que utilizará el poder de la matemática para definir algoritmos en un lenguaje llamado GCL, que servirá como pizarra. Los estudiantes traducirán estos algoritmos a Python en el laboratorio.

Concepto de Tipos de Datos

• Se introduce la idea de usar números enteros para representar situaciones reales, como contar papas peladas.

• Se discute la importancia de las operaciones (suma, resta, orden) sobre los conjuntos numéricos; sin ellas, los conjuntos no tienen utilidad práctica.

Definición y Ejemplos de Tipos de Datos

• Un tipo de dato se define como un conjunto con operaciones que le dan funcionalidad. Por ejemplo, al sumar dos enteros se obtiene otro entero.

• Se mencionan ejemplos específicos: enteros (Z), naturales, reales y booleanos. Las operaciones sobre ellos incluyen suma, resta y multiplicación.

Operaciones en Tipos Booleanos

• En el caso de los booleanos, se identifican operaciones como negación e implicación. Estos son fundamentales en lógica simbólica.

Caracteres y Secuencias

• Se presenta el tipo carácter como un conjunto útil para escribir mensajes al usuario. Cada carácter tiene una posición específica en el alfabeto.

• La codificación del tipo carácter puede variar según el lenguaje utilizado; esto afecta cómo se representan los caracteres.

Estructuras Matemáticas: Secuencias

• Una secuencia es definida como una estructura matemática comúnmente utilizada en programación. Las operaciones incluyen concatenación y ordenamiento.

• Al indexar elementos dentro de una secuencia, cada elemento recibe un índice que permite su identificación; por ejemplo, comenzando desde cero.

Indexación y Longitud

• Se explica cómo indexar posiciones dentro de una secuencia numérica; cada número tiene un índice correspondiente que facilita su referencia durante la programación.

¿Qué es una secuencia?

Definición y Conceptos Básicos

• Se introduce la idea de una secuencia como un objeto que puede ser representado empíricamente, utilizando flechas para indicar su indexación.

• Se define formalmente una secuencia como una función que mapea un intervalo desde cero hasta el número total de elementos en la secuencia.

• La notación utilizada para denotar el conjunto de índices es importante; se menciona que se utiliza paréntesis para intervalos abiertos y corchetes para cerrados, similar a los números reales.

• Se aclara que al referirse a enteros, se está hablando de un conjunto finito y discreto, lo cual contrasta con las nociones continuas vistas en matemáticas anteriores.

• Los computistas tienden a olvidar la definición formal y ven las secuencias simplemente como soluciones indexadas.

Operaciones y Notación

• Se explica por qué el extremo superior del intervalo es n - 1, ya que se comienza desde cero. Esto implica que el cero cuenta como una posición válida dentro de la secuencia.

• Una función puede ser vista como un conjunto de pares ordenados; esto ayuda a entender cómo se relacionan los elementos en la secuencia con sus posiciones.

• La representación de una secuencia puede simplificarse usando notación más compacta, evitando escribir todos los pares ordenados explícitamente.

• Al utilizar símbolos menores (S0, S1, S2), se hace referencia a la estructura ordenada de la secuencia sin complicar su escritura.

• La longitud o tamaño de la secuencia puede calcularse aplicando una función específica sobre ella.

Concatenación y Aplicaciones Prácticas

• Se introduce el operador de concatenación (doble barrita), permitiendo unir dos secuencias en una sola. Esto resulta en una nueva longitud igual a la suma de las longitudes originales.

• Es importante notar que esta operación no es conmutativa; cambiar el orden afecta el resultado final al listar los elementos en diferente orden.

• Conocer sobre las secuencias permite avanzar hacia tipos de datos más complejos como strings, donde cada carácter también forma parte de una secuencia.

• En futuras prácticas, se explorará cómo trabajar con caracteres y sus combinaciones dentro del contexto algorítmico.

Introducción al Operador de Concatenación en Secuencias

Definición y Sintaxis del Operador

• Se presenta el operador de concatenación, que se representa como doble barrita en algunos lenguajes. Cada lenguaje tiene su propia sintaxis para este operador.

Ejemplo de Secuencias

• Se introduce un ejemplo con dos secuencias: 2 3 1 - 1 y 4 - 2 0, para ilustrar cómo funcionan las operaciones sobre ellas.

Conceptos de Primero y Cola

• Se define "primero" como el primer elemento de una secuencia y "cola" como la secuencia que queda después de quitar el primer elemento. La cola es también una secuencia indexada desde cero.

Funciones Totales y Indexación

• Se menciona que todas las secuencias tienen un dominio comenzando desde cero, lo cual es importante para entender funciones totales. Cada elemento debe tener una imagen definida.

Elemento Neutro en Concatenación

• La secuencia vacía se denota sin elementos. Al concatenar cualquier secuencia con la vacía, se obtiene la misma secuencia, similar a cómo funciona el uno en multiplicación o el cero en suma.

Definición del Arreglo

Introducción al Concepto de Arreglo

• Se introduce el concepto de arreglo, destacando que es diferente a las secuencias. Un arreglo puede ser definido por índices que no necesariamente comienzan en cero.

Diferencia entre Arreglos y Secuencias

• A diferencia de las secuencias, donde los índices empiezan siempre en cero, los arreglos permiten definir dónde comienza la indexación (por ejemplo, desde -1).

Evolución Histórica del Concepto

• En lenguajes antiguos como Pascal o Módula, era posible definir índices arbitrarios para arreglos. Sin embargo, hoy en día casi todos los lenguajes modernos utilizan una indexación estándar comenzando desde cero.

Limitaciones Actuales

• Actualmente, la flexibilidad histórica sobre la indexación ha sido reemplazada por convenciones más rígidas donde los arreglos son tratados como secuencias iniciadas desde cero.

Notaciones Clásicas para Acceso a Elementos

• Se discute cómo referirse a elementos específicos dentro de un arreglo o una secuencia utilizando notaciones clásicas que son válidas para ambos tipos de datos.

Conceptos Básicos de Arreglos y Secuencias

Definición de Arreglos y Secuencias

• Un arreglo es un concepto más general que una secuencia; toda secuencia es un arreglo, pero no todo arreglo se considera una secuencia según la definición presentada.

Notación en Funciones

• En el contexto de funciones, se utiliza la notación con corchetes para denotar la imagen del índice i, en lugar de paréntesis, como es común en muchos lenguajes de programación.

Índices y Cardinalidad

• La posición inicial en los arreglos comienza desde cero. Se discute cómo calcular la cardinalidad (número total de elementos) usando índices negativos y positivos.

• Para determinar cuántos elementos hay entre dos índices n y m, se aplica la fórmula: cardinalidad = m - n + 1.

Estructura de Arreglos

• Los arreglos pueden ser visualizados como casilleros indexados donde cada casilla contiene un tipo específico de dato. El tipo debe ser consistente a través del arreglo.

Tipos de Datos en Arreglos

• Los valores dentro del arreglo pueden ser diversos tipos (enteros, reales, caracteres). Además, se puede tener arreglos dentro de otros arreglos, creando estructuras más complejas como matrices.

Restricciones sobre el Tipo y Tamaño

• Es importante notar que todos los elementos dentro del mismo arreglo deben ser del mismo tipo. Si se desea trabajar con tamaños variables, se debe utilizar otro tipo de datos llamado lista.

Declaraciones en GSL

Introducción a GSL

• Se menciona que antes de declarar variables en GSL (un lenguaje específico), es necesario entender los tipos de datos involucrados.

Ejemplo Práctico

• Se presenta un ejemplo donde N es declarado como una variable entera. Esto implica que sus valores pertenecen al conjunto de números enteros y permite realizar operaciones aritméticas básicas.

Declaraciones de Variables y Espacios de Estado en Algoritmos

Introducción a los Tipos de Datos

• Se discuten operaciones básicas como restar y multiplicar, enfatizando la importancia de definir tipos de datos reales.

• Se menciona la necesidad de tener una lista clara de tipos para entender mejor los elementos involucrados en el algoritmo.

Declaración y Notación

• La declaración de variables debe reflejar correctamente los tipos; se sugiere usar plural cuando hay múltiples elementos del mismo tipo.

• Se presenta una forma alternativa para declarar variables, indicando que si no se especifica nada, se asume que sigue siendo variable.

Precondiciones y Espacio de Estado

• Se establece una precondición donde la variable R es un arreglo indexado desde 3 hasta 6 con enteros como elementos.

• Las diferentes formas de escribir declaraciones son equivalentes; esto ayuda a describir el estado del "paciente" en el contexto del algoritmo.

Definición del Espacio de Estados

• El espacio de estados se define como un conjunto que representa todos los posibles estados que puede tener el paciente durante la ejecución del algoritmo.

• El símbolo ESP se utiliza para denotar este espacio, lo cual es crucial para entender cómo cambian los estados a medida que las acciones son ejecutadas.

Ejemplos Prácticos

• Al definir un estado posible dentro del algoritmo, se ejemplifica con coordenadas reales (ej. 3, -4.5), mostrando cómo cada acción puede cambiar estos valores.

• Un estado es considerado un elemento dentro del espacio definido; el paciente cambia su valor conforme avanza el algoritmo.

Funciones y Arreglos

• Se introduce la noción matemática detrás de los arreglos como funciones con dominios específicos; esto ayuda a formalizar su uso en programación.

• La notación utilizada para representar conjuntos y funciones es fundamental para comprender cómo funcionan los arreglos dentro del contexto algorítmico.

Ejemplo de Llenado de Tuplas

Conceptos Básicos sobre Arreglos

• Se presenta un ejemplo de llenado de una tupla con tres valores, destacando que el primer y último valor son reales.

• Se menciona que al colocar un arreglo particular, se describe como un conjunto de pares ordenados.

• Se discute la notación más cómoda para representar arreglos, enfatizando que cambiar un valor en el arreglo afecta a la función completa.

Cambios en Arreglos y Funciones

• Cambiar un valor dentro del arreglo implica modificar toda la función asociada; por lo tanto, es crucial entender cómo estos cambios afectan el estado general.

• La variabilidad en los valores del arreglo permite realizar cambios simples, pero siempre debe mantenerse el índice fijo.

Estado de Abortamiento en Algoritmos

Definición del Estado Abortado

• Se introduce el concepto de "abortamiento" como un estado adicional donde el algoritmo no puede continuar debido a errores o condiciones inesperadas.

• El espacio de estados se amplía para incluir este nuevo estado abortado, diferenciándolo de otros estados válidos.

Notación y Representación

• En GCL (un lenguaje específico), se permite abortar procesos cuando ocurren fallas durante la ejecución.

Precondiciones y Predicados

Comprensión de Precondiciones

• Una precondición se define como una fórmula que evalúa verdadero o falso según los valores introducidos; esto se conoce como predicado.

• Los predicados deben permitir sustituir variables por valores concretos dentro de su dominio.

Notación Funcional

• Se explica cómo las variables libres pueden ser representadas en notación funcional, facilitando su comprensión y uso práctico.

Instrucciones y Asignaciones

Significado del Símbolo de Asignación

• En GCL, el símbolo utilizado para asignaciones tiene un significado específico diferente al usado en definiciones matemáticas.

¿Cómo se define el espacio de estado en un algoritmo?

Definición del Espacio de Estado

• El valor inicial de las variables x e y se sustituye por dos valores específicos, formando pares ordenados que representan el espacio de estado del algoritmo.

• Se establece un estado inicial, por ejemplo, (-1, 2), y al ejecutar una instrucción, este estado cambia a uno nuevo.

Instrucción Swap

• La instrucción discutida es un "swap", donde el valor de x toma el valor de y y viceversa, con la modificación adicional de que y se convierte en x - 1.

Funciones y Resultados

• Se introduce la función R como la que realiza el cambio entre estados. Es importante entender qué devuelve esta función tras aplicar la instrucción.

¿Qué significa un símbolo en programación?

Interpretación de Símbolos

• Un símbolo como 'x' tiene significado solo dentro del contexto definido por su sintaxis; sin contexto, no tiene interpretación.

• En programación, cada símbolo debe tener reglas claras sobre su construcción (ortografía) y su significado semántico.

Reglas Semánticas

• La semántica o significado detrás de los símbolos es fundamental en todas las materias relacionadas con computación y estructuras matemáticas.

Determinismo vs No Determinismo en Instrucciones

Naturaleza Determinística

• La acción descrita es determinística; dado un estado inicial específico siempre producirá un resultado final predecible.

Relación e Interpretación

• Si una instrucción fuera no determinística, debería ser interpretada como una relación más que como una función. Por ello se utiliza 'R' para denotar esta relación.