Complejidad Computacional

Tecnológico Nacional de México
Instituto Tecnológico de Ensenada
Asignatura: Inteligencia Artificial
Docente: Eddie Helbert Clemente Torres
Actividad: Complejidad computacional
Nombre del estudiante: Andrade Perez Judith Adilene
Matrícula: 19760544
Grupo: 8SE
Fecha de entrega: 06 febrero 2024

INDICE
INTRODUCCION..................................................................................................... 3
DESARROLLO DE LA ACTIVIDAD........................................................................4
CONCLUSIONES.................................................................................................... 7
REFERENCIAS BIBLIOGRAFICAS........................................................................8
INTRODUCCION
La resolución de problemas complejos y la optimización de sistemas son desafíos

comunes en diversas áreas, desde la informática hasta la ingeniería y la toma de
decisiones estratégicas y para abordar estos desafíos, se emplean enfoques
específicos que permiten encontrar soluciones efectivas en un tiempo razonable
en estos enfoques se encuentran las heurísticas y las metaheurísticas,
herramientas poderosas que facilitan la búsqueda de soluciones en espacios de
búsqueda extensos o en situaciones donde encontrar la solución óptima es
impracticable es la heurística actúa como un atajo práctico, ofreciendo soluciones
aproximadas, mientras que las metaheurísticas proporcionan estrategias
generales para explorar y explotar eficientemente el espacio de soluciones es
largo de esta introducción, exploraremos ejemplos de heurísticas y
metaheurísticas que ilustran su aplicación en la resolución de problemas
complejos.
DESARROLLO DE LA ACTIVIDAD
La teoría de la complejidad computacional o teoría de la complejidad

informática es una rama de la teoría de la computación que se centra en la
clasificación de los problemas computacionales de acuerdo con su dificultad
inherente, y en la relación entre dichas clases de complejidad.
Un problema se cataloga como "inherentemente " si su solución requiere de una

cantidad significativa de recursos computacionales, sin importar el algoritmo
utilizado. La teoría de la complejidad computacional formaliza dicha aseveración,
introduciendo modelos de computación matemáticos para el estudio de estos
problemas y la cuantificación de la cantidad de recursos necesarios para
resolverlos, como tiempo y memoria.
Una de las metas de la teoría de la complejidad computacional es determinar los

límites prácticos de qué es lo que se puede hacer en una computadora y qué no.
Otros campos relacionados con la teoría de la complejidad computacional son
el análisis de algoritmos y la teoría de la computabilidad. Una diferencia
significativa entre el análisis de algoritmos y la teoría de la complejidad
computacional, es que el primero se dedica a determinar la cantidad de recursos
requeridos por un algoritmo en particular para resolver un problema, mientras que
la segunda, analiza todos los posibles algoritmos que pudieran ser usados para
resolver el mismo problema.
1. Problema tipo P (Polinomial):
 Ejemplo: Suma de subconjuntos (Subset Sum). Dado un conjunto

de números enteros y un número objetivo, el problema consiste en
determinar si existe un subconjunto cuya suma sea igual al número
objetivo. Se puede resolver eficientemente mediante programación
dinámica en tiempo polinómico.
2. Problema tipo NP (No determinista polinómico):
 Ejemplo: Problema del viajante de comercio (TSP - Traveling

Salesman Problem). Dado un conjunto de ciudades y las distancias
entre ellas, el objetivo es encontrar la ruta más corta que visite cada
ciudad exactamente una vez y regrese al punto de partida. No se
conoce un algoritmo que resuelva este problema en tiempo
polinómico, pero si se proporciona una solución, es fácil verificar en
tiempo polinómico si cumple con los requisitos.
3. Problema tipo NP-Completo:
 Ejemplo: Problema de la mochila (Knapsack Problem). Dado un

conjunto de objetos, cada uno con un peso y un valor, y una
capacidad máxima de la mochila, el problema consiste en
seleccionar un subconjunto de objetos que quepan en la mochila y
maximicen el valor total. El problema de la mochila es NP-Completo,
lo que significa que no se conoce un algoritmo polinómico para
resolver todos los casos, pero si se tiene una solución, se puede
verificar en tiempo polinómico.
4. Problema tipo NP-Difícil:
 Ejemplo: Problema de la parada (Halting Problem). Enunciado

anteriormente, el problema de la parada es un ejemplo de problema
NP-Difícil. Determinar si un programa
específico se detendrá para cualquier entrada dada es un problema
no decidible. La NP-dificultad
del problema de la parada se basa en su relación con problemas no

decidibles, como el problema de la detención de la máquina de
Turing.
Una heurística es una técnica o método que proporciona soluciones prácticas y

aproximadas a problemas complejos, especialmente cuando se enfrenta a
situaciones en las que encontrar la solución óptima es difícil o impracticable en un
tiempo razonable. Las heurísticas son reglas generales o atajos que simplifican el
proceso de toma de decisiones. No garantizan la solución óptima, pero son
eficientes y suelen ofrecer resultados aceptables en un tiempo más corto.
Ejemplo de heurística:
 Heurística del vecino más cercano: En el problema del viajante de

comercio, donde se busca encontrar la ruta más corta que visite todos los
puntos, la heurística del vecino más cercano consiste en seleccionar en
cada paso el punto más cercano al actual. Aunque no garantiza la solución
más óptima, es una estrategia rápida y sencilla.
Por otro lado, una metaheurística es un enfoque general para resolver problemas
de optimización que guía y supervisa el proceso de búsqueda de soluciones en el
espacio de posibles soluciones. A diferencia de las heurísticas específicas, las
metaheurísticas son algoritmos más generales que pueden aplicarse a una amplia
variedad de problemas de optimización.
Ejemplo de metaheurística:
 Algoritmo genético: Es una metaheurística inspirada en la evolución

biológica. Utiliza conceptos como selección natural, cruces y mutaciones
para buscar soluciones óptimas en un espacio de
búsqueda. Los algoritmos genéticos son utilizados en problemas de
optimización combinatoria, como el problema del viajante de comercio o la
programación de horarios.
CONCLUSIONES
En las heurísticas y las metaheurísticas representan herramientas fundamentales

en la caja de herramientas de la resolución de problemas y la optimización y es la
heurísticas, al ofrecer soluciones aproximadas, permiten abordar problemas de
manera rápida y eficiente, incluso en entornos donde la solución exacta es difícil
de alcanzar. Por otro lado, las metaheurísticas, como los algoritmos genéticos o
las estrategias de búsqueda basadas en poblaciones, proporcionan enfoques
generales y flexibles para la exploración de soluciones en espacios de búsqueda
complejos. Estas técnicas son esenciales en situaciones donde la complejidad
computacional limita la búsqueda exhaustiva de soluciones. Al adoptar y adaptar
estas herramientas, los profesionales pueden enfrentarse con éxito a desafíos
variados, llevando a cabo procesos de optimización y toma de decisiones de
manera eficaz en diversas disciplinas.
REFERENCIAS BIBLIOGRAFICAS
https://www.redalyc.org/journal/414/41449298008/html/#:~:text=Mientras%20que
%20la%20heur%C3%ADstica%20%E2%80%93un,la%20b%C3%BAsqueda
%20de%20su%20soluci%C3%B3n.
https://www.youtube.com/watch?v=JBm5OXbReQE&embeds_referring_euri=https
%3A%2F%2Fclassroom.google.com%2F
https://www.youtube.com/watch?v=UR2oDYZ-Sao&embeds_referring_euri=https
%3A%2F%2Fclassroom.google.com%2F
chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://uvadoc.uva.es/
bitstream/handle/10324/19054/TFG-G1789.pdf?sequence=1#:~:text=La%20Teor
%C3%ADa%20de%20la%20Complejidad%20Computacional%20es
%20precisamen%2D%20te%20la,los%20problemas%20seg%C3%BAn%20su
%20dificultad.

Complejidad Computacional

Cargado por

Copyright:

Formatos disponibles

Complejidad Computacional

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Complejidad Computacional

Cargado por

Copyright:

Formatos disponibles

Tecnológico Nacional de México

Instituto Tecnológico de Ensenada

Asignatura: Inteligencia Artificial

Docente: Eddie Helbert Clemente Torres

Actividad: Complejidad computacional

Nombre del estudiante: Andrade Perez Judith Adilene

Fecha de entrega: 06 febrero 2024

La resolución de problemas complejos y la optimización de sistemas son desafíos

La teoría de la complejidad computacional o teoría de la complejidad

Un problema se cataloga como "inherentemente " si su solución requiere de una

Una de las metas de la teoría de la complejidad computacional es determinar los

 Ejemplo: Suma de subconjuntos (Subset Sum). Dado un conjunto

2. Problema tipo NP (No determinista polinómico):

 Ejemplo: Problema del viajante de comercio (TSP - Traveling

3. Problema tipo NP-Completo:

 Ejemplo: Problema de la mochila (Knapsack Problem). Dado un

4. Problema tipo NP-Difícil:

 Ejemplo: Problema de la parada (Halting Problem). Enunciado

del problema de la parada se basa en su relación con problemas no

Una heurística es una técnica o método que proporciona soluciones prácticas y

 Heurística del vecino más cercano: En el problema del viajante de

 Algoritmo genético: Es una metaheurística inspirada en la evolución

En las heurísticas y las metaheurísticas representan herramientas fundamentales

También podría gustarte