Buscar en el Blog

Mostrando entradas con la etiqueta manual. Mostrar todas las entradas
Mostrando entradas con la etiqueta manual. Mostrar todas las entradas

jueves, 11 de junio de 2015

MANUAL DE ALGORITMICA - Grafos


MANUAL DE ALGORITMICA
 Grafos
Proyecto fin de carrera
Escuela Técnica Superior de Ingeniería Informática
Departamento Matemáticas Aplicadas I
Tutor: Alberto Márquez Pérez
Borrego Ropero, Rafael
rafaborrego@gmail.com
Recio Domínguez, Daniel
danird@gmail.com

1.- Introducción................................................................................................... 6
2.- Conceptos generales. ................................................................................... 8
Grafos, tipos, ejemplos................................................................................ 8
Algunas definiciones. ................................................................................ 12
Algunos grafos básicos. ............................................................................ 17
Tipos de rutas ........................................................................................... 46
Grafo complementario............................................................................... 48
Grafo de línea. .......................................................................................... 50
3.- Algoritmos implementados. ......................................................................... 54
3.1.- Algoritmos sobre caminos mínimos. ..................................................... 54
Algoritmo de Dijkstra. ................................................................................ 54
Algoritmo de Floyd. ................................................................................... 61
3.2.- Algoritmos de distancias....................................................................... 65
Excentricidad de un vértice. ...................................................................... 65
Radio de un grafo...................................................................................... 67
Diámetro de un grafo................................................................................. 69
Distancia de un vértice. ............................................................................. 70
Algoritmo de la mediana............................................................................ 72
Algoritmo del centro. ................................................................................. 73
3.3.- Conectividad......................................................................................... 75
Algoritmo de componentes conexas. ........................................................ 75
Vértices de corte. ...................................................................................... 77
Aristas puente. .......................................................................................... 78
Bloques. .................................................................................................... 79
3.4.- Algoritmos de búsquedas. .................................................................... 88
Búsqueda en profundidad (DFS) .............................................................. 88
Búsqueda en anchura (BFS) .................................................................... 90
3.5.- Árboles recubridores de peso mínimo. ................................................. 92
Algoritmo de Boruvka. ............................................................................... 92
Algoritmo de Prim...................................................................................... 98
Algoritmo de Kruskal. .............................................................................. 100
3.6.- Prufer.................................................................................................. 103
Algoritmo de codificación. ....................................................................... 103
Algoritmo de decodificación. ................................................................... 110
3.7.- Algoritmo de emparejamientos ........................................................... 120
Algoritmo de emparejamiento maximal simple........................................ 121
Algoritmo de Kuhn-Munkres.................................................................... 128
Algoritmo de Kuhn-Munkres con preprocesamiento (peso mínimo)........ 142
Algoritmo de emparejamiento maximal de peso óptimo.......................... 146
3.8.- Euler ................................................................................................... 157
¿ Es euleriano ?. ..................................................................................... 157
3.9.- Algoritmos de búsqueda de trayectorias eulerianas. .......................... 162
Algoritmo de Fleury ................................................................................. 162
Algoritmo de Tucker. ............................................................................... 183
Algoritmo de Hierholzer........................................................................... 201
Problema del cartero............................................................................... 205
3.10.- Algoritmos de vértice coloración....................................................... 212
Algoritmo de coloración Secuencial o Voraz. .......................................... 213
Algoritmo de coloración Welsh-Powell .................................................... 215
Algoritmo de coloración Matula-Marble-Isaacson ................................... 216
Algoritmo de coloración de Brelaz........................................................... 217
¿Es bipartito?.......................................................................................... 221
3.11.- Algoritmos de aristas coloración....................................................... 225
Algoritmo basado en rellenar un cuadrado latino .................................... 225
Algoritmo basado en emparejamientos maximales................................. 228
3.-12.- Hamilton .......................................................................................... 235
Algoritmo de Dirac................................................................................... 235
Búsqueda de trayectorias hamiltonianas................................................. 239
4.- Bibliografía ................................................................................................ 248



jueves, 2 de octubre de 2014

Clonar proyecto desde bitbucket.org a nuestra Pc en Windows usando git


Bitbucket es un servicio de alojamiento basado en web, para los proyectos que utilizan el sistema de control de revisiones Mercurial y Git. Bitbucket ofrece planes comerciales y gratuitos. Se ofrece cuentas gratuitas con un número ilimitado de repositorios privados (que puede tener hasta cinco usuarios en el caso de cuentas gratuitas)

Ahora vamos a realizar una clonacion de un proyecto creado en Bitbucket y traerlo a Windows.
Para esto deben tener un proyecto creado en su cuenta de Bitbucket.


El siguiente paso es intalar Git, el cual podemos descargar de la siguiente direccion http://git-scm.com/ 


Nos vamos a Downloads y elegimos la version para windows.

Una vez descargado, ejecutamos el instalador y seleccionamos las siguientes opciones.


Luego solo le damos click a siguiente hasta que se termine la instalacion.
Con este ya tendremos git instalado: Git GUI y Git bash.




Ejecutamos el Git bash.




git config user.name <nombre>
Define el nombre del autor que se usará en todos los commits del repositorio actual. Normalmente, se usa la opción --global para ajustar las opciones de configuración del usuario actual.

git config --global user.name <nombre>
Define el nombre del autor que se usará en todos los commits por el usuario actual.

git config --global user.email <email>
Define el correo electrónico del autor que se usará en todos los commits por el usuario actual.



 configuramos el usuario y el mail asi como esta en la imgen. Deben colocar el nombre de usuario y el mismo correo de la cuenta de Bitbucker.
Luego con la instruccion cd nos ubicamos en donde vamos a crear el clonado.



Abrimos nuestra cuenta en Bitbucket y nos vamos a la opcion Clone y copiamos la URL  que nos muestra y ingresamos en la consola.



 


Luego enter.




Empezara a conectarse al servidor. Luego nos pedira la contraseña.

Una vez terminado, ya podremos visualizar nuestro proyecto(si es que este tuviera archivos)

creamos un archivo cualquiera para probar el funcionamiento dentro del directorio de clonacion.

Luego nos ubicamos en el directorio del repositorio.

 
Aqui ingresamos el comando git init para inicializar el repositorio.
Luego el comando git add seguido de un punto.
El comando git add añade un cambio en el directorio de trabajo al área de preparación. Le dice a Git que quieres incluir actualizaciones en un archivo en particular en el siguiente commit. Sin embargo, git add no afecta al repositorio de forma importante—los cambios no se guardan hasta que se ejecuta git commit.




finalmente ingresamos git commit -m "<mi mensaje>"


Ahora para enviar todo al server, debes ingresar el siguiente comando

git push origin master

Para actualizar desde el servidor a nuestra pc, el comando es el siguiente:

git pull

lunes, 8 de septiembre de 2014

Pruebas de Software y JUnit

Pruebas de Software y JUnit

Un análisis en profundidad y ejemplos prácticos

Daniel Bolaños Alonso
Departamento de Ingeniería Informática
Universidad Autónoma de Madrid
Almudena Sierra Alonso
Departamento de Ciencias de la Computación
Universidad Rey Juan Carlos
Miren Idoia Alarcón Rodríguez
Departamento de Ingeniería Informática
Universidad Autónoma de Madrid


364 paginas


viernes, 21 de febrero de 2014

Compiladores Principios Tecnicas y Herramientas - Pearson.Educacion - Dragon Book


Los principios y tecnicas de escritura de compiladores son tan amplios como las ideas encontradas en este libro se usaran muchas veces en la carrera de un cientifico de la computacion. La escritura de compiladores comprende los lenguajes de programacion, la arquitectura de computadores, la teoria de lenguajes, los algoritmos y la ingenieria de softwareñ. Por fortuna, con algunas tecnicas basicas de escritura de compiladores, se pueden construir traductores para una gran variedad de lenguajes y maquinas.