Archivo de la etiqueta: estructuras de datos

Fundamentos de Algoritmos: Complejidad, Estructuras y Estrategias de Resolución

Ingeniería de organización de las tecnologías de la información y la comunicación, , , , ,

Complejidad Algorítmica

El orden típico de complejidad, de menor a mayor, es: Θ(1) < Θ(log n) < Θ(n) < Θ(n log n) < Θ(n²) < Θ(n³) < Θ(2ⁿ) < Θ(n!).

  • Θ(n): Recorrer un vector una vez.
  • Θ(n²): Bucles anidados.
  • Θ(log n): Dividir entre 2 repetidamente.

Estrategias de Diseño

Divide y Vencerás

Divide el problema en varios subproblemas, los resuelve recursivamente y combina las soluciones. Se aplica en algoritmos como MergeSort o Quicksort. Su forma típica es T(n) = aT(n/ Seguir leyendo “Fundamentos de Algoritmos: Complejidad, Estructuras y Estrategias de Resolución” »

Estructuras de Datos y Algoritmos: Árboles, Grafos y Hashing

Ingeniería informática, , ,

Árboles Generales y Estructuras de Búsqueda

Representación mediante Lista de Hijos

¿Hay alguna operación claramente ineficiente en la representación de árboles generales mediante lista de hijos?
Sí, en la representación de lista de hijos, la operación de búsqueda de un nodo hermano específico puede ser ineficiente porque requiere recorrer secuencialmente toda la lista de hijos del nodo padre, lo que tiene un coste $O(n)$ en el peor caso.

Vector de Posiciones Relativas

¿En qué situaciones Seguir leyendo “Estructuras de Datos y Algoritmos: Árboles, Grafos y Hashing” »

Estructuras de Datos y Algoritmos Fundamentales en Java

Informática, , , , ,

Estructuras de Datos: Pilas y Colas

En este primer bloque, se presenta la implementación de dos estructuras fundamentales: la Pila (Stack) y la Cola (Queue). Se demuestra el funcionamiento de los principios LIFO (Last In, First Out) y FIFO (First In, First Out).

import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;

public class Pilas {
    public static void main(String[] args) {
        
        // Creamos la Pila (LIFO/FILO)
        Stack<String> pila = new Stack< Seguir leyendo “Estructuras de Datos y Algoritmos Fundamentales en Java” »

Algoritmos y Estructuras de Datos Fundamentales en Pseudocódigo

Matemáticas, , , ,

Algoritmos de Ordenación

Ordenación por Inserción (Insertion Sort)

Procedimiento Ins


procedimiento Ins (var T[1..n])
    para i := 2 hasta n hacer
        x := T[i];
        j := i - 1;
        mientras j > 0 y T[j] > x hacer
            T[j+1] := T[j];
            j := j - 1
        fin mientras;
        T[j+1] := x;
    fin para
fin procedimiento

Ordenación por Selección (Selection Sort)

Procedimiento Sel


procedimiento Sel (var T[1..n])
    para i := 1 hasta n-1 hacer
        minj := i; Seguir leyendo “Algoritmos y Estructuras de Datos Fundamentales en Pseudocódigo” »

Optimización de Búsqueda Binaria y Funciones Hash en Estructuras de Datos

Ingeniería informática, , ,

Búsqueda Binaria

Código: binaria(int A[], int clave, int inf, int sup) {

%IMAGE_1%

Al ser recursivo, hemos de actualizar límites. If (inf > sup) Return -1; Medio = (inf + sup) / 2; If (clave < A[medio]) Return binaria(A, clave, medio + 1, sup); Return medio;

Ejemplo: %IMAGE_2%

Busca el %IMAGE_3% y el %IMAGE_4%. El orden de llamada es: binaria(A, 25, 0, 8), binaria(A, 25, 5, 8). La función devuelve 6.

El orden de llamada es binaria(A, 7, 0, 8), binaria(A, 7, 0, 3), binaria(A, 7, 2, 3), binaria( Seguir leyendo “Optimización de Búsqueda Binaria y Funciones Hash en Estructuras de Datos” »

Fundamentos de la Programación y Estructuras de Datos

Ingeniería en sistemas de información, , , , , , ,

Ordenador: Herramienta capaz de llevar a cabo una tarea, siguiendo un algoritmo que le indique, con la mayor precisión posible, lo que debe hacer.

Programas: Secuencia de instrucciones entendibles por los ordenadores que permiten la realización de las acciones para las que han sido creadas. Para escribir un programa se utilizan distintos lenguajes, llamados lenguajes de programación. Se escriben en código fuente: Instrucciones que deben ser ejecutadas a fin de realizar las acciones para las que Seguir leyendo “Fundamentos de la Programación y Estructuras de Datos” »

Fundamentos de la Programación: Datos, Operadores y Estructuras

Informática, , , , ,

Dato: Es toda información característica, susceptible de tratamiento informático. La forma en que se clasifican establece la estructura y forma de los datos así como su representación en el lenguaje de programación.

Sistemas y Códigos de Numeración

El hombre se expresa alfabéticamente con el idioma y decimalmente en vista numérica. El ordenador realiza ambas acciones en binario.

Sistemas de Numeración

Conjunto de símbolos y reglas que se utilizan para representar datos numéricos. Se caracterizan Seguir leyendo “Fundamentos de la Programación: Datos, Operadores y Estructuras” »

Estructuras de Datos y TAD: Diferencias, Encapsulamiento y Calidad del Software

Ingeniería informática, , , , , ,

Diferencias entre Estructuras de Datos y Tipos Abstractos de Datos (TAD)

Estructuras de Datos

Una estructura de datos es un método de almacenamiento de datos en la memoria de un ordenador. Ejemplos incluyen enteros, matrices y pilas. En definitiva, es cualquier forma de almacenar información en la memoria del ordenador.

Los programas que usan estructuras de datos, sin la abstracción de los TAD, pueden ser complejos.

Tipo Abstracto de Datos (TAD)

Un Tipo Abstracto de Datos (TAD) es una colección Seguir leyendo “Estructuras de Datos y TAD: Diferencias, Encapsulamiento y Calidad del Software” »

Explorando Autómatas, Listas, Recursividad, Pilas y Colas en Programación

Ingeniería informática, , , , , , ,

Autómatas y Control Lógico Programable

El término PLC, de amplia difusión, significa Controlador Lógico Programable. Originalmente se denominaban PCs (Programmable Controllers), pero, con la llegada de las IBM PCs, para evitar confusión, se emplearon definitivamente las siglas PLC.

La definición más apropiada es: Sistema Industrial de Control Automático que trabaja bajo una secuencia almacenada en memoria, de instrucciones lógicas.

Es una máquina electrónica programable capaz de ejecutar Seguir leyendo “Explorando Autómatas, Listas, Recursividad, Pilas y Colas en Programación” »

Implementación Eficiente de TDA Cola: Optimización de Procedimientos y Almacenamiento

Ingeniería informática, servicios y aplicaciones, , , ,

TDA Cola

Implementación de TDA Cola que prioriza velocidad de procedimiento

CONST
max = 10

TIPO
t_cola = registro
contenedor = array[1…max] de tipo_dato
e, s = entero
fin_registro

VAR
cola = t_cola

e: posición en la que debe ingresar el nuevo elemento
s (frente): posición de la cual se debe extraer un elemento

Proc. inicializar_cola (var cola: t_cola)
INICIO
cola.e = 1
cola.s = 1
FIN

Función cola_vacia (cola: t_cola): lógico
INICIO
cola_vacia = (cola.s = cola.e)
FIN

Proc. agregar_cola (var cola: t_cola, nuevo: Seguir leyendo “Implementación Eficiente de TDA Cola: Optimización de Procedimientos y Almacenamiento” »