martes, 21 de diciembre de 2010

CCNA 4 v4 chapter 2‏ exam

Puntaje: 97.8










También te podrían interesar los siguientes enlaces:
CCNA4 v4 - Módulo 1 - Exámen Capítulo 7
Configuración de servidor Radius en Debian
CCNA 4 v4 - Caso de estudios 2
CCNA4 v4 - Reto de Integración Capítulo 10

domingo, 21 de noviembre de 2010

Algoritmo de QuickHull para la cerradura convexa

Pues en este post describiré lo relacionado con el algoritmo de QuickHull para encontrar la envolvente convexa de una conjunto de puntos. Evidentemente el esquema será el mismo que se ha venido mostrando a lo largo de todos mis post relacionados con la geometría computacional. Primero que nada, debemos comprender de qué trata este algoritmo, y no hay mejor que mediante el seudocódigo y un ejemplo donde de ponga a prueba su funcionamiento. El algoritmo de QuickHull nos dice lo siguiente:


Entonces, dada una nube de puntos como la de la imágen:


El algoritmo nos dice que como primer paso debemos seleccionar el punto más a la izquierda y el punto más a la derecha, quedándonos algo así:


Luego debemos separar en dos conjuntos, los que están a la derecha del segmento formado por los dos puntos encontrados anteriormente, y los que están a la izquierda. Estos conjuntos recibirán el nombre de S1 y S2 respectivamente.


Agregamos a la cerradura el punto min, los puntos que hallaremos al procesar el conjunto S1, el punto max y por último los puntos que hallaremos al procesar el conjunto S2.


En la pila en donde se almacenan los puntos hay dos elementos que están con un color de fondo determinado, esto es así porque quiero indicar que en estas posiciones se insertarán conjuntos de puntos que serán hallados de manera recursiva, dada la naturaleza del algoritmo.

Ahora procesaremos S1. En esta parte se llamara a la función encargada de procesar el subconjunto de puntosd. Lo que se hace es escoger el punto más lejano de la recta formada por los puntos a y b, que son las entradas para este subprocedimiento. El punto más lejano es el punto 6 y este punto no tiene ningún punto, ni a la derecha ni a la izquierda, tal como indica el seudocódigo mostrado. Entonces el resultado de procesar el subconjunto S1 será el punto 6.


Ahora es el turno del subconjunto S2. El punto más lejano es el punto 2, el cuál al formar el segmento cb no tiene puntos a su derecha, pero si a su derecha (área amarrilla), pero al formar el segmento ac, presenta un punto a su derecha. Algo que rescatar aquí es que el proesamiento de S2 nos devolverá más de un punto. Entonces añadimos el resultado de procesar subconjunto A (región amarilla) a la pila y luego el punto 2.

Ahora, siguiendo el procesamiento anterior, el resultado de procesar la región amarilla nos retornará solo el punto 3 el cuál será añadido a la pila y terminará con la recursivad de este algoritmo al cumplir con la condición de finalización (if noEsVacio(s)), ya que no nos quedan más puntos por procesar.


Utilizando los puntos almacenados en la pila podemos generar la envolvente convexa de nuestra nube de puntos, finalizando con esto todo el proceso.


Evidentemente todo esto debe ser contrastado con un modelo que permita certificar que todo lo expuesto anteriormente es cierto y bueno, aquí les dejo una simulación que, de manera interactiva, les permitirá verificar que el algoritmo funciona.



La implementación del Algoritmo QuickHull es la siguiente:
public static List<Point2D> quickHull(List<Point2D> nube) {
    List<Point2D> cerradura = new ArrayList<Point2D>();
    Point2D min_x = new Point2D.Double(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
    Point2D max_x = new Point2D.Double(Double.NEGATIVE_INFINITY, Double.NEGATIVE_INFINITY);
    for(Point2D aux:nube) {
        if(aux.getX()<min_x.getX()) {
            min_x = aux;
        }
        if(aux.getX()>max_x.getX()) {
            max_x = aux;
        }
    }
    List<Point2D> S1 = puntosLado(min_x, max_x, nube);
    List<Point2D> S2 = puntosLado(max_x, min_x, nube);
    cerradura.add(min_x);
    cerradura.addAll(findHull(min_x, max_x, S1));
    cerradura.add(max_x);
    cerradura.addAll(findHull(max_x, min_x, S2));
    return cerradura;
}

public static List<Point2D> findHull(Point2D a, Point2D b, List<Point2D> S) {
    List<Point2D> cerradura = new ArrayList<Point2D>();
    Point2D c = new Point2D.Double();
    if(!S.isEmpty()) {
        List<Point2D> A = new ArrayList<Point2D>();
        List<Point2D> B = new ArrayList<Point2D>();
        c = puntosMayorArea(a, b, S);
        A = puntosLado(a, c, S);
        B = puntosLado(c, b, S);
        cerradura.addAll(findHull(a, c, A));
        cerradura.add(c);
        cerradura.addAll(findHull(c, b, B));
    }
    return cerradura;    
}
El código fuente completo lo pueden descargar aquí:

Photobucket

Bueno, espero que les sea de utilidad. Muy pronto postearé otros algoritmos para la cerradura convexa. No se olviden de dejar sus comentarios y críticas.

Quizás te pueda interesar también esos posts:
http://rolandopalermo.blogspot.com/2010/11/java-convex-hull-jarvis.html
http://rolandopalermo.blogspot.com/2010/09/algoritmo-de-graham-para-la-cerradura.html

martes, 16 de noviembre de 2010

Servidor Radius en Debian

Evidentemente si has llegado hasta este post es porque ya sabes qué es un servidor de autenticación Radius, así que las explicaciones las dejaremos de lado. Sin embargo, a pesar de que existen muchos artículos que abordan este tema, estos no siempre nos funcionan a la primera. Bueno, en este post trataremos de que nuestro servidor quede correctamente configurado al primer intento. Lo primero que debemos hacer utlizar los mismos repositorios. El usar otros repositorios podría cambiar ligeramente el proceso de configuración descrito en este post. Bien, vayamos al grano, estos son mis repositorios:
#Repositorios no Libres
deb http://http.us.debian.org/debian/ lenny main contrib non-free

# Seguridad
deb http://security.debian.org/ lenny/updates main contrib
deb-src http://security.debian.org/ lenny/updates main contrib

#### Unstable (sid)
deb http://ftp.fi.debian.org/debian/ unstable main non-free contrib
deb-src http://ftp.fi.debian.org/debian/ unstable main non-free contrib
# deb http://mirrors.kernel.org/debian/ sid main contrib non-free
# deb-src http://mirrors.kernel.org/debian/ sid main contrib non-free

#### Testing
deb http://ftp.fi.debian.org/debian/ testing main contrib non-free
# deb-src http://ftp.fi.debian.org/debian/ testing main contrib non-free
# deb http://security.debian.org/ testing/updates main contrib non-free

#### Experimental
deb http://mirrors.kernel.org/debian/ experimental main contrib non-free
# deb-src http://mirrors.kernel.org/debian/ experimental main contrib non-free
Luego ejecutamos los comandos los siguientes comandos
apt-get clean
apt-get update
Instalamos los paquetes necesarios
apt-get install apache2
apt-get install mysql-server
apt-get install freeradius freeradius-mysql
Editamos el archivo de usuarios (que serían los host o o usuarios finales que harían peticiones de autenticación)
gedit /etc/freeradius/users
En el archivo hay varios ejemplos de usuarios. Descomentamos (borramos este símbolo: #) el usuario steve que viene como ejemplo. Nos quedaría algo así:

 

En este caso he agregado el usuario toshiba y su clave será cisco. Para probar que el servidor autentica correctamente debemos hacer lo siguiente:
En modo root primero detendremos el servicio:
/etc/init.d/freeradius stop
Iniciamos el modo debug
freeradius -X
Verificamos la autenticación por parte del servidor servidor
radtest steve testing 127.0.0.1 1812 testing123
Debemos obtener algo como esto
Sending Access-Request of id 115 to 127.0.0.1 port 1812
 User-Name = "toshiba"
 User-Password = "cisco NAS-IP-Address = 127.0.1.1
 NAS-Port = 1812
rad_recv: Access-Accept packet from host 127.0.0.1 port 1812, id=115, length=38
 Service-Type = Framed-User
 Framed-Protocol = PPP
 Framed-Compression = Van-Jacobson-TCP-IP

Con esto el servidor ya estaría listo para aunteticar usando los parámetros que trae por defecto. Evidentemente estos deben ser cambios y se le deben agregar algunas otras funcionalidades. En otro post explicaré cómo hacer que nuestro servidor autentique usando usuarios almacenados en una base de datos de MySQL.

Saludos y espero les sea de utilidad.

Algoritmo de Jarvis para la Cerradura Convexa

En esta oportunidad vamos a ver el funcionamiento del algoritmo de Jarvis para la cerradura convexa. Veamos de qué trata el algoritmo:


Bueno, el seudocódigo está bastante claro, pero vamos a ver cómo funcionaría con un pequeño conjunto de puntos. Supongamos que tenemos el siguiente conjunto de puntos:



Primero seleccionamos el punto de menor coordenada y lo llamamos p.


Luego escogemos el punto que forma el menor ángulo con la horizontal, al que llamaremos q y agregamos p a la pila que guardará los puntos que forman la cerradura convexa.


Ingresamos al bucle y vamos a empezar a encontrar los puntos que forman la cerradura convexa teniendo como condición que este deberá formar el menor ángulo con la recta que forma los puntos p y q.

En la primera iteración pasaría esto:


El punto 3 es el que forma el menor ángulo por lo que pasará a formar parte de la cerradura convexa. Vayamos a la siguiente iteración.


El siguiente punto ahora es el punto 2. El punto 3 ya pasó a formar parte de la cerradura convexa. Ahora veamos la siguiente iteración.


Vemos que el punto con menor ángulo es el punto de inicio, además la condición de parada nos dice que q!=inicio. Y la siguiente iteración no se ejecutará ya que nos quedará algo como esto:

El bucle se termina y graficamos la cerradura convexa con los puntos almacenados en nuestra pila, quedándonos así:

Aca les dejo un aplet para verificar el funcionamiento de nuestro algoritmo.




La implementación del Algoritmo de Jarvis es la siguiente:
/**
 *
 * @author Rolando
 */
public static List<Point2D> jarvis(List<Point2D> nube) {
    List<Point2D> cerradura = new ArrayList<Point2D>();
    double min = 0,ang = 0;
    //O(n)
    Point2D p = new Point2D.Double();
    Point2D q = new Point2D.Double();
    Point2D pInicio = new Point2D.Double();
    Point2D posMin = new Point2D.Double();
    p = menorCoordenadaY(nube);
    pInicio = p;
    q = calcularMenorAngulo(nube, p);
    cerradura.add(p);
    while(q!=pInicio) {
        cerradura.add(q);
        min=180;
        for(Point2D aux:nube) {
            if(aux!=q) {
                ang=angulo(q,p,aux);
                if(ang<min) {
                    posMin=aux;
                    min=ang;
                }
            }
        }
        p=q;
        q=posMin;
    }
    return cerradura;
}

El código fuente completo lo pueden descargar aquí:

Photobucket

Bueno, espero que les sea de utilidad. Muy pronto postearé el algoritmo de QuickHull. No se olviden de dejar sus comentarios y críticas.

Quizás te pueda interesar también esos posts:
http://rolandopalermo.blogspot.com/2010/09/algoritmo-de-graham-para-la-cerradura.html
http://rolandopalermo.blogspot.com/2010/11/quickhull-java-convex-hull.html

miércoles, 3 de noviembre de 2010

Acelerar el proceso de arranque en Sistemas Windows 7 con varios procesadores

El arranque en sistemas operativos Windows 7 por defecto se realiza con un solo procesador, pero podemos sacarle provecho a nuestras computadoras si es que estas poseen más de un núcleo. El proceso es sencillo.

1. Pulsamos las teclas Windows + r y nos aparecerá la siguiente ventana:


2. Escribimos msconfig y pulsamos enter o damos clic en aceptar.


3. Seleccionamos la pestaña Arranque y damos clic en Opciones avanzadas...


4. En la ventana que nos aparecerá marcamosNúmero de procesadores para que la habilite.


5. Seleccionamos el número de procesadores de la lista desplegable y hacemos clic en Aceptar.


6. Luego hacemos clic en Aplicar, luego en Aceptar y se nos pedirá que reiniciemos nuestra computadora.


Eso es todo, espero les sea de utilidad. Cualquier duda o sugerencia, estoy presto a atenderla.

Configuración de Servidor Radius en Packet Tracer

En este post voy a mostrar la forma de como configurar un servidor Radius en el entorno de simulación de packet tracer. La imágen que muestro a continuación es el reto de integración del CCNA3 v 4.0 que se dicta en Trujillo-Perú (Universidad Privada del Norte). La idea es es que los usuarios que se conecten a ambos access points puedan autenticarse usando un servidor radius ubicado en la misma VLAN en que la que se encuentran estos access points (VLAN 10).

Bueno, una vez que hemos colocado el servidor radius en la misma VLAN le vamos a asignar un IP, máscara de subred y gateway de forma correcta. La VLAN 10 tiene el siguiente rango de direcciones: 30.30.30.0/24

Y ya que se usa enrutamiento entre VLANS usando router-on-a-stick, la dirección gateway será 30.30.30.1 (para más detalle descarga el archivo de packet tracer al final del post).

Entonces debería quedarnos algo así:


Bien, ahora vamos a configurar el servidor RADIUS. La siguiente imágen nos indicará cómo hacerlo:


Los clientes serán los access points que utlizarán este servidor para la autenticación y los usuarios serán los hosts finales que necesitarán de un usuario y contraseña. Ahora vamos a configurar los access points para que utilizen el servidor.

Primero debemos establecer el método de cifrado que utilizará y luego indicarle la dirección IP del servidor radius de esta manera:


Ahora tenemos que configurar en cada host el nombre de usuario y la contraseña. Para esto seguiremos los siguientes pasos:

1. Editar el perfil del host. Seleccionamos el perfil y le damos clic en Edit.


2. Seleccionamos el SSID del access point al que nos queremos conectar y seleccionamos Advanced Setup.


3. Verificamos que en efecto sea el SSID del access point al que nos queremos conectar (Lo podemos editar, si ese fuese el caso) y luego damos clic en Next.


4.  Si tenemos un servidor DHCP entonces dejamos la opción marcada en rojo, en caso contrario tendremos que ingresar los datos requeridos para un host con IP estática. Luego hacemos clic en Next.


5. Seleccionamos el tipo de encriptación que usa el access point y damos clic en Next.


6. Ingresamos el usuario y contraseña que habíamos añadido anteriormente a la base de datos del servidor RADIUS (El número de usuarios en radius dependerá del número de clientes que se conecten a los access points). Luego damos clic en Next.


7. Hacemos clic en Save y listo!!


Y para finalizar el post aca les dejo el archivo de packet tracer.

Photobucket

Con eso ya tenemos nuestro proceso de autenciación usando un Servidor Radius. Cualquier inquietud, no duden en comentarla.

También te podría interesar estos posts:

CCNA4 v4 - Módulo 1 - Exámen Capítulo 7
Exámen CCNA4 v4 - Capítulo 2
Configuración de servidor Radius en Debian
CCNA 4 v4 - Caso de estudios 2
CCNA4 v4 - Reto de Integración Capítulo 10