La Familia 27000 y sus amigos

Es un conjunto de normas aplicables a todas las organizaciones sin importar su tamaño o rubro. Ademas de enfocarse en la privacidad, la confidencialidad o los problemas técnicos de seguridad de los sistemas IT, va dirigida a evaluar los riesgos de seguridad de la información, con el fin de implementar medidas y controles adecuados según las necesidades, directrices y sugerencias de cada empresa.

Las normas de la familia ISO/IEC 27000 proporcionan orientación sobre determinados aspectos de diseño, implementación y operación de un Sistema de Gestión de seguridad de la Información (SGSI), además ofrece recomendaciones de mejores prácticas, manejo de riesgos y los controles aplicables al SGSI, de forma análoga a los sistemas de gestión para el aseguramiento de la calidad (ISO 9000) y del protección del medio ambiente ( Serie ISO14000).

Dada la naturaleza dinámica de la seguridad de la información, el concepto de SGSI incorpora actividades de retroalimentación y mejora continua, los cuales se resumen en el modelo Deming "Planificar-hacer-verificar-actuar", enfoque, que tratan de abordar los cambios en las amenazas, vulnerabilidades e impacto de los incidentes de seguridad de la información.

Seguridad de la información

Este término surgió a partir de prácticas y procedimientos seguidos para salvaguardar los sistemas de seguridad informática. Se define como la protección, uso, procesamiento, divulgación, alteración, modificación, lectura, inspección, registro o destrucción, almacenamiento y transmisión de información o de datos en los sistemas de una organización.

La gestión de la Seguridad de la información se ha convertido en garantía de que las organizaciones utilizan sistemas de gestión de riesgos, Si bien se centra predominantemente en la información en forma digital, también abarca la forma analógica o física.

Este es un enfoque interdisciplinario que se basa en varios campos, incluyendo la contabilidad, criptografía, ciencias forenses, Sistemas de gestión, ciencias de la computación, ingeniería de seguridad,  la criminología, además de la informática.

Apéndice de Normalización

Las normas son el producto de la norma ISO/IEC JTC1 (Comité Técnico Conjunto 1) SC27 (Sub-comité 27), un organismo internacional que se reúne en persona dos veces al año.

Organismos Internacionales
ISO         Organización Internacional de Normalización
IEC         Comisión Electrotécnica Internacional
CEN        Comité Europeo de Normalización

ÖNORM  Instituto Austriaco de Normas
DIN        Instituto Alemán de Normalización
BSI         British Standards Institution
AFNOR    Asociación Francesa de Normalización
ANSI       American National Standards Institute

Como funcionan la aprobación y publicación  de una norma:

http://www.iso.org/iso/iso_technical_committee?commid=45306

En la actualidad, once de las normas de la serie están publicados y disponibles, mientras que varios más están todavía en desarrollo. Los originales de normas ISO / IEC son vendidos directamente por la norma ISO, mientras que los puntos de venta asociados con diversos organismos nacionales de normalización también venden varias versiones, incluyendo traducciones locales.

IS 27000   Bases y Vocabulario del SGSI

IS 27001   Requerimientos del SGSI

IS 27002   Código de buenas prácticas para la gestión de seguridad de la información

IS 27003   Guía de implementación del SGSI

IS 27004   Medidas de gestión de la seguridad de la información

IS 27005   Gestión de riesgos en seguridad de la información

IS 27006  Requerimientos para los organismos que proveen Auditorias y certificaciones SGSI

IS 27007   Guías de referencia para auditar un SGSI, No publicado aún,

IS 27011   SGSI para organizaciones que prestan servicios de telecomunicaciones

Si tienes información adicional sobre este tema, tus comentarios o links de referencia son bienvenidos.

ISO/IEC 27001 Requisitos para mejorar los Sistemas de Gestión de la seguridad de la Información (SGSI)

ISO/IEC 27001 es una normativa internacional válida desde octubre del 2005 y se deriva de la norma BS 7799-2 del grupo BSI (British Standards Institution). Esta norma  especifica formalmente todo el proceso requerido para implementar y aplicar un sistema de gestión de seguridad de la información (SGSI). Ser una especificación formal significa que se deben reunir ciertos requisitos específicos en busca de una certificación.


La gerencia de la organización determina el alcance del SGSI y delimitación  de la certificación a una sola unidad de negocio, por lo tanto La norma ISO/IEC 27001 no significa necesariamente que el resto de la organización, fuera del área de ámbito, tiene un enfoque adecuado para la gestión de seguridad de la información.

Modelo Deming de aseguramiento de calidad

Enfoque orientado a procesos de ISO/IEC 27001 

Examina sistemáticamente los riesgos de la organización de seguridad de información, teniendo en cuenta las amenazas, vulnerabilidades e impactos.

Diseña e implementar un conjunto coherente y exhaustivo de los controles de seguridad de la información y/u otras formas de tratamiento de riesgos (por ejemplo, la cobertura de riesgos o de transferencia de riesgo), es especial para hacer frente a esos riesgos que se consideran inaceptables.

Adoptar un proceso de gestión global sobre una base de realimentación continua para asegurar que los controles de seguridad de la información siguen satisfaciendo las necesidades de la organización.

Las organizaciones que afirman haber adoptado la norma ISO/IEC 27001, deben ser formalmente auditado y certificado conforme a la normativa.

• Responsabilidad de la administración
• Auditorías internas del SGSI
• examen de la gestión de ISMS
• Control de Documentos
 
Declaración de aplicabilidad:
• Los objetivos de control y controles seleccionados
• Los objetivos de control y controles aplicados 
• Los objetivos de control y los controles no seleccionados,  justificación

Comparación de ISHB y SGSI

Certificación

la certificación SGSI se aplica a empresas, no a productos o servicios, una empresa certificada garantizar a sus clientes y socios, que cumple con las normas de seguridad, por lo tanto es fiable y maneja criterios de calidad.


En algunos países, los organismos que verifican la conformidad de los sistemas de gestión a las normas especificadas son llamados "organismos de certificación", mientras que en otros se refieren comúnmente como "organismos de certificación".

Los requisitos de la entidades acreditadoras son:

• imparcialidad
• neutralidad
• Repetibilidad
• objetividad
• independencia financiera

En Austria: La acreditación se hace por medio del BMWFJ y CIS (Certified Information Security Services) 

La norma ISO/IEC 27001 al igual que otras certificaciones ISO de sistemas de gestión, por lo general implica un proceso de auditoría en tres etapas:

Etapa 1 Es un examen preliminar e informal del SGSI, comprobando la existencia y la integridad de la documentación clave, como las políticas de seguridad de la información dentro de la organización, la Declaración de Aplicabilidad (SOA) y Plan de Tratamiento del Riesgo (RTP). Esta etapa sirve para familiarizar a los auditores de la organización y viceversa.

Etapa 2 Es una auditoría de cumplimiento más detallada y formal. Los auditores buscan pruebas para confirmar que el sistema de gestión ha sido correctamente diseñado e implementado, por ejemplo: Confirmar que un comité de seguridad o cuerpo similar de administración se reúne periódicamente para supervisar la operación del SGSI.

Etapa 3 Seguimiento de revisiones o auditorías para confirmar que la organización siga cumpliendo con la norma. El Mantenimiento de la certificación requiere de evaluaciones periódicas para confirmar que el SGSI sigue funcionando según lo especificado y previsto. Estos deben ocurrir al menos una vez al año, pero a menudo se realizan con más frecuencia, en particular, mientras que el SGSI todavía está madurando.

Duración del proceso de certificación

3 años con auditorias de vigilancia cada 6 meses, después es necesaria una re-certificación

Fuentes: www.bitkom.org

Si tienes información adicional sobre este tema, tus comentarios o links de referencia son bienvenidos. 

Criterios comunes para probar y evaluar la Seguridad en las Tecnologías de la Información

Tambien conocida como "Common Criteria" o CC, es una norma de certificación reconocida internacionalmente para certificar los procesos de implementación, especificación, desarrollo y evaluación en productos de seguridad informática.

Los fabricantes y vendedores de productos de seguridad IT como Controladores de seguridad, tarjetas inteligentes(Smart Cards), etc, afirman reunir ciertas características de seguridad, sin embargo la seguridad y la confianza van de la mano, por lo tanto deben medirse de manera rigurosa y estandarizada para garantizar la funcionalidad ofrecida.

Versión 3.1R3 (2007): Vigente actualmente (Febrero 2012), al unificar las Norma internacionales ISO/IEC 15408, ITSEC (Europa), TCSEC, FC (EE.UU) y CTCPEC (Canadá), está reconocida oficialmente por 26 naciones.

Beneficios 

• Los usuarios de sistemas IT pueden especificar sus requisitos funcionales de seguridad, disponibilidad  y garantía.
• Los proveedores pueden garantizar y asegurar el cumplimiento de los atributos de seguridad que ofrecen sus productos.
• Los investigadores y desarrolladores pueden evaluar los productos IT para determinar si, efectivamente, cumplen los beneficios ofrecidos.  

 

Contenido

Parte 1: Introducción y modelo general
Parte 2: Componentes de seguridad funcionales
Parte 3: Componentes de Aseguramiento de seguridad

 

Objeto de Evaluación (TOE Target of Evaluation) 

Es el producto o sistema de información que requiere una evaluación para validar sus  características de seguridad y su funcionamiento.

 
 

Perfiles de Protección (PP)

Son Documentos creados por un usuario o comunidad de usuarios que identifican los requisitos y especificaciones de seguridad que debe cumplir una familia de productos IT o sistemas de información, así Los clientes que buscan cierto producto pueden centrarse en los certificados PP que cumplan sus necesidades.

Un PP especifica los criterios generales de evaluación de seguridad para que los clientes puedan justificar con motivos tangibles la reclamación a los vendedores el producto. Los desarrolladores pueden optar por diseñar productos que cumplan con uno o más PP que han sido parte de los procesos de evaluación.

Ejemplos de PP

Tarjeta Inteligente usada como dispositivo de creación de Firma digital con los Perfiles de protección de acuerdo con los Criterios Comunes certificados por BSI

Tipo 1: Generación de claves seguras de firmas digitales>EAL 4 + BSI-PP-0004-2002T

Tipo 2: Almacenamiento de la clave y producción de firmas> EAL 4 + BSI-PP-0005-2002T

Tipo 3: Combinación de 1 y 2 en un dispositivo> EAL 4 + BSI-PP-0006-2002T

 

Objetivo de Seguridad (ST - Security Target) 

Documento proporcionado por el desarrollador del producto, que especifica los criterios de seguridad que se pueden evaluar en el TOE y utiliza uno o más PPs como puntos de referencia.

Esto permite a los proveedores adaptar  con precisión su producto para que coincida con los campos de aplicación. Por ejemplo un firewall de red no tiene que cumplir los mismos requisitos funcionales que un sistema de gestión de bases de datos (DBMS). El ST se suele publicar para que los clientes potenciales pueden determinar las características específicas de seguridad que han sido certificadas por los entes de evaluación.

Los autores del ST pueden aseguran el cumplimiento de uno o mas requisitos de seguridad delineados por la plantilla del PP, Así reúnen una descripción completa y rigurosa de los posibles problemas de seguridad de un TOE, incluyendo  las amenazas, los supuestos, los requisitos funcionales de seguridad (SFR) y requisitos de aseguramiento de seguridad (SARs). 

Requisitos funcionales de seguridad (SFR)

CC posee un catálogo estándar de funciones que definen las características individuales de seguridad que posee un producto. Por ejemplo: El control de acceso y autenticación de un usuario que posee un determinado rol, tecnologías adicionales como encripción, protocolos de comunicaciones, auditoría, etc.

La lista de SFR puede variar de una evaluación a la siguiente, incluso si dos objetivos son el mismo tipo de producto. A pesar de que el Common Criteria no requiere que algún SFR sea  incluidos en el ST, identifica las dependencias de la correcta operación de una función, como Limitar el acceso de usuarios de acuerdo a roles, sea dependiente de otra función como la capacidad de identificar roles individualmente.

Evaluación

El proceso de evaluación trata de establecer el nivel de confianza que puede ser asignado a las características de seguridad del producto mediante de procesos de garantía de calidad. Las instituciones evaluadoras hacen tres posibles tipos de Pruebas y evaluación para comprobar que los productos de seguridad informática y sistemas de Información realmente reúnen las características que afirman.

• Criterios para probar y evaluar los perfiles de protección (PP).
• Requisitos de seguridad basados en los criterios para probar y evaluar los objetivos de seguridad(ST) por medio de los objetos de seguridad (TOE)
• Pruebas y evaluación de un TOE basados en los criterios ya evaluados de los ST o PP

Requisitos de Aseguramiento de seguridad (SAR)

Los requisitos para un objetivo particular o tipos de productos están documentados en el ST y el PP, respectivamente, Sin embargo SAR describe las medidas para asegurar la calidad y el cumplimiento de las funciones de seguridad adoptadas durante el desarrollo, las pruebas y evaluación del producto.

Una evaluación puede requerir que todo el código fuente se mantenga en un sistema de gestión de cambios, que se realice una prueba funcional completa, el uso de métodos formales o semiformales para analizar el código fuente y garantizar la calidad de las herramientas de desarrollo (compilador, lenguaje de programación, plataformas, infraestructura, etc...)

Niveles de Integridad o Nivel de Aseguramiento de evaluación ( EAL- Evaluation Assurance Level)

PP también especifica el EAL en el rango de 1 al 7, lo que indica la profundidad y el rigor de la evaluación de la seguridad, por lo general en forma de documentación de apoyo y pruebas, que un producto cumple con los requisitos de seguridad especificados en el PP. 

EAL1: Pruebas funcionales, sin la cooperación de los desarrolladores, el TOC trabaja de acuerdo con la documentación
EAL2: Pruebas estructurales, los sistemas existentes, donde no hay documentación completa disponible para el Desarrollo
EAL3: Metódicamente probado y comprobado, seguridad media
EAL4: Metódicamente desarrollado, probados y revisados, Seguridad media y alta, es el nivel mínimo mas aceptado.
EAL5: Semi-formalmente diseñado y probado, lenguaje con sintaxis restringido, Seguridad alta.
EAL6: Diseño semi-formal, verificado y probado, Se usa en tecnologías de alta seguridad en un entorno de desarrollo con controles estrictos
EAL7: Diseño formalmente verificada y probada. TOG adecuado para su uso en situaciones con riesgos extremadamente alto; un análisis formal y amplio de las funcionalidades de seguridad requerida.

Niveles de jerarquía de los requerimientos de seguridad 

1. Clases de seguridad: Objetivos generales de seguridad contra diferentes amenazas

Certificación

Esquema del Sistema de certificación: Son documentados públicamente accesibles, los cuales resumen todos los principios, normas y procedimientos que se llevan a cabo para evaluar y emitir certificados.

Principio de separación de poderes :

• Cliente:  (patrocinador): responsable de la TOE
• Auditor: (Entidad de valoración) responsable de las pruebas, Requisitos EN 45001
• Certificación: (Entidad certificadora): Hace seguimiento de la evaluación y las pruebas de las certificados, Requisito EN 45011
• Acreditación: vigila el cumplimiento de las normas, acreditando la certificación y la auditoría.

Acuerdo de Reconocimiento según los Criterios comunes (CCRA)

Acuerdo CC firmado en el 2000 por los países como Australia, Alemania, Finlandia, Francia, Grecia, Reino Unido Italia Canadá Países Bajos Nueva Zelanda Noruega Gran Bretaña, Italia, Canadá, Nueva Zelanda, Países Bajos, Noruega, España, Estados Unidos.

Más tarde en el 2002 se unieron países como: Dinamarca, India, Israel, Japón, Corea del Sur, Malasia, Austria, Pakistán, Singapur, Suecia, República Checa, Turquía y Hungría.

Los  certificados de seguridad TI deben tener reconocimiento global y se basan en CC incluyendo el nivel de aseguramiento EAL4.


SOGIS-MRA

Acuerdo de Reconocimiento Mutuo de Evaluación en Certificación de la seguridad en tecnologías de la Información. (SOGIS Mutual Recognition Agreement of Information Technology Security Evaluation Certificates)

Es el grupo oficial Senior para certificar en temas de Seguridad de la Información con reconocimiento europeo de los certificados ITSEC/CC, Reconoce los certificados bajo las condiciones  EAL7.

Firmado en 1998 por países como Alemania, Finlandia, Francia, Grecia, Gran Bretaña, Italia, Países Bajos, Noruega, Portugal, Suecia, Suiza y España, por ejemplo, Alemania: recibió el reconocimiento de su certificación por Francia y  Gran Bretaña.


Fuente CC:http://www.commoncriteriaportal.org/cc/

Si tienes información adicional sobre este tema, tus comentarios o links de referencia serán bienvenidos.

Clasificación de aplicaciones y sistemas BCP

Objetivos

• Asegurar la disponibilidad de las principales aplicaciones y sistemas TI dentro de un período definido.
• Control de daños en caso de desastre.

 

Definición (BS25999)

Plan de Continuidad de operaciones de Negocio (Business continuity planning) es la 

Capacidad estratégica y técnica de una organización para planificar y responder a incidentes propios del negocios, de tal manera que se pueda guarantizar la ocntinuidad de las operaciones en un nivel míimo aceptable previamente.

Ejemplo de Clasificación BCP 

Categoría 1> No es crítico si no hay suministro: La falla por un período indefinido no afectara significativamente la ejecución de tareas.

Categoría 2> Aseguramiento Off-line: Las medidas actuales de seguridad, la localización externa, Reinicio de la aplicación después de la reparación de los daños del sistema original.
 
Categoría 3> Infraestructura redundante: En el caso de fallo de un componente, continúan sus operaciones sin interrupción.
 
categoría 4> Ubicación redundante: Construcción redundante de infraestructura,  sistemas y aplicaciones en el caso de fallo.

Si tienes información adicional sobre este tema, tus comentarios o links de referencia serán bienvenidos.

Fundamentos y objetivos de SIHB (Security Information Hand Book)

Objetivos

• Estandariza los procedimientos del Sistema de gestión de seguridad
• Recopila las normas y medidas de seguridad as para los requisitos de protección medio

Punto de partida

• IT Manual de referencia de Protección del BSI (BSI IT Baseline Protection)
• ISO / IEC TR 13335
• ISO / IEC 27001

Requisitos  

• Compatible con los estándares enfoque unificado
• Las leyes austríacas y las normas
• Hace parte del ciclo de vida de todo el sistema 

Proceso de Gestión de seguridad SIHB 

Nivel 1> Desarrollo  de las Políticas  de Seguridad de la Información

Este documento es la base sobre como administrar la seguridad de la información. Determina las objetivos, estrategias, Responsabilidades y métodos a largo plazo relacionados con la seguridad.  Adicionalmente incluye las directrices de aplicación, para ser adoptado oficialmente. Es necesario que todos los empleados de la organización lo conozcan.

Contenido:

• Objetivos y estrategias para la seguridad de la información ¿Qué queremos lograr? ¿Cómo lograr los objetivos fijados?
• Responsabilidades y Organización en la seguridad de la información  ¿Quién hace qué?  Definición del personal técnico y roles específicos dentro de la organización, derechos obligaciones y generación de informes.
• Estrategia de Análisis de riesgos ¿Como se identifican los riesgos en general? ¿Cómo los manejamos?, Identificación y evaluación de riesgos, su aceptación y minimización.
• Clasificación de datos ( El manejo de información clasificada, confidencialidad, protección de datos)¿Cómo se clasifica la información? ¿Quién los clasifica?, Confidencialidad,  Privacidad e Integridad.
• Clasificación de las aplicaciones y sistemas BCP ¿Cuáles son los requisitos de disponibilidad? Planeamientos que garanticen la continuidad del negocio.
• Actividades de seguimiento ¿Cómo se puede mantener la seguridad se a largo plazo? 

Nivel 2> Análisis de Riesgos  ISO/IEC 27005

Riesgo: Posibilidad de que una amenaza determinada explote las vulnerabilidades de un activo o grupo de activos para causar daño a una organización. Es una medida que combina la probabilidad de que ocurra un suceso y las  consecuencias que generaría. 

Amenaza:  Causa potencial  de un incidente que pueda causar daño al sistema u organización

Vulnerabilidad: Debilidad de un activo o grupo de activos que puede ser explotada por una o más amenazas.

Gestión de Riesgos

El análisis de Riesgos integra la Identificación y Evaluación de Riesgos.

Identificación y Evaluación de Riesgos

El riesgo se mide en función del valor de los activos, Amenazas, Vulnerabilidades,   probabilidad de que un incidente de seguridad cause daños en el sistema, y ademas de la evaluación del impacto y las consecuencias que se generan después de dicho incidente. [http://www.enisa.europa.eu/act/rm]

  Nivel 3>Generación del Concepto de Seguridad

Catalogos con  medidas de seguridad

Manual de Protección de Línea base (BSI): Gran herramienta de Apoyo con mas de alrededor de 1200 medidas de seguridad genéricas y para productos específicos.
Asignación de medidas como "bloques de construcción"

Manual Austriaco de Seguridad de la información: Österreichisches Informationssicherheitshandbuch.Los capítulos 5 al 15 poseen aproximadamente 300 medidas, Específico para Austria y no posee medidas específicas para productos.

ISO/IEC 27002 (antes ISO/IEC 17799): Posee 133 medidas genéricas de seguridad, Es básicamente una lista de verificación que se centra en los puntos débiles de una organización.

Para hablar de aceptación de riesgos es necesario aclarar que ningún sistema es completamente infalible, así se posean sistemas de gestión de seguridad que minimicen los daños de un incidente de seguridad. 

El riesgos residual es esa porción inminente de riesgo,  que permanece desconocida hasta que algún trastorno en el sistema la hace visible. A pesar de que los sistemas sean redundantes existen factores de riesgo fortuitos que se pueden predecir para  minimiza los efectos que se presenten. Estos riesgos deben cuantificarse y evaluarse, así tomar la decisión del nivel de aceptación de los riesgos residuales.

Normas de seguridad

• Requisitos básicos y las directrices para la seguridad en un sistema de IT
• Detalles de las medidas de seguridad seleccionadas
  Razones para la selección

Plan de Seguridad

• Como se aplican las medidas de seguridad elegidas
• Prioridades y planificación de los recursos
• Cronogramas
• Responsabilidades
• Medidas de formación y sensibilización
• Pruebas e inspección (proceso, citas)
• Evaluación del riesgo residual

  Nivel 4> Implementación del plan de seguridad

La documentación  estar Actualizada, completa, con alto nivel de detalle, ademas debe ser confiable y contar con control de versiones e integridad

Concientización y capacitación

• Información sobre todos las políticas y medidas de seguridad , ademas de las acciones necesarias a seguir en caso de eventos relacionados con la seguridad.
• Acontecimientos regulares y publicaciones
• Capacitación, cambios significativos y mejoras
• Herramienta de apoyo y multimedia son útiles para entrenar  a los empleados sobre las funciones específicas que deben seguir para proteger la información.

Acreditación: Liberación del sistema TI para operar en un ambiente especial
Objetivo: garantizar la seguridad del sistema de información

• En un entorno operativo específico
• Bajo ciertas condiciones
• Para el periodo de tiempo determinado

Técnicas:

• Comprobación del Cumplimiento de las medidas de seguridad
• Pruebas
• Evaluación y Certificación

  Nivel 5> Operación del proceso de seguridad de la Información

Gestión de Cambios

• Identificación de nuevas necesidades de seguridad como resultado de los cambios que se han generado en el sistema
• Respuestas adecuada a todos los cambios relevantes relacionados con la seguridad
• Documentación escrita de todos los cambios y las razones por las que se tomaron las decisiones
• Posiblemente se requiere un nuevo análisis de riesgo renovado 
  
• Necesidad de un sistema de gestión de calidad

Si tienes información adicional sobre este tema, tus comentarios o enlaces de referencia serán bienvenidos.

Skip List I -Busqueda

Estructura de búsqueda dinámica, aleatoria, simple y eficiente para almacenar listas organizadas de objetos. Para entender como funciona vamos a considerar una simple lista enlazada, que conecta todos los nodos ordenadamente, este es el Nivel 0 (N0). El primer cuandro donde está el nombre del nivel lo llamaremos cabecera.


Ahora agregaremos el nivel 1, que es otra lista enlazada pero los nodos son un subconjunto del nivel 0



El siguiente nivel 2 es ahora un subconjunto del nivel 1. Como te darás cuenta, cada vez que subimos de nivel tenemos menos nodos conectados.

Las skip lists o listas de saltos, tienen 3 operaciones básicas, buscar, insertar o eliminar.

Buscar  

Para encontrar el nodo 12, empezamos desde la cabecera del nivel mas arriba N2, buscamos el nodo de la lista mas cercano, que tambien es 12, comparamos ¿12 > 12? Falso, por lo que contamos un paso a la derecha, ¿12 = 12? Verdadero. Terminamos y solo necesitamos un paso para encontrarlo


Ahora busquemos el nodo7, este requiere mas pasos:

1. Iniciamos en la cabecera de N2 (nivel 2). Buscamos el nodo mas cercano a la cabecera que es 12 Comparamos ¿7 > 12? Falso, entonces bajamos a la cabecera N1, dibujamos una flecha y contamos un paso.
2. En la cabecera N1 Buscamos el nodo mas cercano que es 4, comparamos ¿7 > 4? Verdadero, entonces avanzamos un paso a la derecha ¿7=4? Falso, Continua el algoritmo
3. Buscamos el siguiente nodo, que es 12, ¿7>12? Falso, permanecemos en 4, bajamos un al nivel N0 y contamos otro paso.
4. En 4 de N0 Buscamos el siguiente nodo que es 7,comparamos ¿7>7? Falso, ¿7=7? Verdadero, Lo encontramos

Si quisiéramos buscar al nodo 8 que no está en la lista, el procedimiento sería el mismo, pero agregamos un paso de comparación 7<8<12, sin embargo pertenecemos en 7.

Otro ejemplo:

Buscar 78 requiere de 7 pasos



Buscar 12 requiere de 4 pasos


Buscar 63 requiere de 8 pasos, donde el último paso es de verificación sin avance ya la búsqueda se termina en el nodo 56

Heap

Heap se traduce como montículo, pero antes de hablar de estructuras de datos quiero definir que es un montículo, la verdad cuando yo leí la definición por primera vez no fui capaz de entender el concepto, así que lo quiero aclarar por si tu tuviste mi mismo problema:

Un montículo es una agrupación de cosas una sobre otras, en Colombia decimos de forma muy castiza “montonsito” o un bonche” de cosas. Asi que podemos hablar de montículos de frutas, monedas, arena, nueces, o cualquier cosa que se te ocurra.

Ahora si entrando en materia un Montículo es una estructura de datos en forma de árbol binario completo, el cual posee un algoritmo que organiza los nodos según su valor, ya sea en orden ascendente o descendente.

Recordemos que los árboles binarios poseen nodos que tienen máximo 2 nodos hijos, Un árbol binario es completo cuando los nodos de ambas ramas (izquierda y derecha) están balanceadas y ademas todos sus niveles están llenos excepto el último nivel, donde todos los nodos están hacia un mismo lado.

Maxheap: La cima contiene el elemento mayor y todos los hijos son menores que su padre (hijo<= padre), se observa como los números disminuyen a medida que descendemos en el montículo 

MinHeap: La cima contiene el elemento menor, todos los padres son menores que sus hijos (padre <=hijo) se observa como los números aumentan a medida que descendemos en el montículo

Si tienes información adicional sobre este tema, tus comentarios, dudas o enlaces de referencia serán bienvenidos.

6 ejemplos de Arboles AVL

Los arboles AVL son árboles binario con una propiedad adicional: se balancean automáticamente teniendo en cuenta el factor de balance (FB) y el valor de cada nodo que insertamos o eliminamos. En el  enlace Estructura de Datos: Arboles puedes conocer mas sobre la  terminología que usamos en este artículo.

El factor de balance (FB) de un nodo es la diferencia de alturas entre la rama izquierda menos la derecha, para que el árbol esté balanceado este valor solo pueden ser -1, 0 ó 1.

FB= altura(arbol.izq)-altura(arbol.der)

Para lograr el balance adecuado, debemos ubicar al nodo hijo en la posición correcta antes de hacer cualquier rotación. 

Cuando la rotación se hace con nodos externos hablamos de rotación sencilla, mientras que si se trata de nodos internos o que requieran un cambio de dirección del nodo, se refiere a una rotación doble.

Ejemplos de Auto-balanceo

1.  En este ejemplo iniciamos con un árbol balanceado, pero en el paso 2 vamos a insertar el nodo 16 en el nodo hoja número 17, esta inserción des-balancea el árbol especialmente al nodo 13, por lo tanto con este nodo es que haremos una  rotación  doble izquierda-derecha.

 

2. Ahora queremos insertar 2 en el nodo hoja 3,  esto des-balancea el árbol en el nodo interno 4, por lo tanto hacemos una rotación sencilla a la derecha y  finalmente logramos balancear el árbol 

 

3.Insertamos 3 en el nodo hoja 2, el nodo de des-balance es 4, así que hacemos una rotación doble derecha-izquierda

4. Insertamos 7 en el nodo hoja 8, el nodo de des-balance es 6, así que hacemos una rotación doble derecha (7-8)-izquierda.

5. Insertamos 9 en el nodo hoja 8, el des.balance se genera en el nodo interno 5, desplazamos el nodo 7 hacia arriba, esta es una rotación simple a la izquierda (solo interactuan los nodos 4, 5 y 7 en la rotación) , el nodo hoja 6 ahora depende de 5.

6. Este era el punto del examen :) así que tiene truco,  Esta es una rotación doble izquierda-derecha usando  los nodos 6 en la raiz, 9 y 7. 

Si tienes información adicional sobre este tema, tus comentarios, dudas  o enlaces de referencia serán bienvenidos, .

Formas de recorrer un arbol

Recorrido:Es la forma de visitar todos los nodos de un árbol siguiendo un orden específico

Pre-orden: Procesa primero el nodo y después cada hijo es procesado recursivamente de izquierda a derecha

Pos-orden: Procesa primero cada nodo hijo recursivamente y después procesa al nodo

Siguiente: Árboles Binarios

Si tienes información adicional sobre este tema, tus comentarios o links de referencia serán bienvenidos.

Estructura de Datos: Arboles

Un árbol es una estructura de datos no lineal y jerárquicamente organizada, cuyos elementos son nodos conectados por bordes que no forman ciclos. Todo árbol tiene un nodo raíz de donde descienden mas nodos, existe solo un camino para acceder a cada nodo desde la raíz.

Algunos ejemplos de arboles son: la tabla de contenido de un libro o el sistema de archivos de cualquier sistema operativo ya sea Unix, DOS o Windows.

 

Datos importantes y terminología

• Un árbol con n nodos tiene n-1 bordes o conectores
• La raíz es un nodo sin padres o ancestros
• las hojas son los nodos mas externos sin hijos o descendientes
• hermanos son nodos con el mismo padre

Longitud de un camino: el el número de bordes que se pueden seguir desde un nodo hasta alcanzar otro nodo

Profundidad: Número de bordes desde la raíz a el nodo, la profundidad del nodo raíz siempre es 0

Altura: Longitud del camino mas largo desde la raíz al a la hoja mas profunda que se pueda alcanzar.

Tamaño del nodo: Es la suma de todos los nodos descendientes mas uno, que equivale al nodo que estamos midiendo, el tamaño de la raíz determina el tamaño del árbol.

Estructuras para implementar árboles

Con una lista enlazada

Con una matriz si sabemos el número máximo de hijos que poseen los nodos

Siguiente:Formas de recorrer un árbol

Si tienes información adicional sobre este tema, tus comentarios o enlaces de referencia serán bienvenidos.