Teoria de Grafos I

Standard

Hola a todos espero y tengan un buen día, el día de hoy en esta primera parte de este blog vamos a empaparnos un poco acerca de a teoría grafos, espero y les sea útil, bien pues comencemos.

¿Que es un grafo?

Pues un grafo es una colección finita de vértices o nodos(nodes) y aristas (edges).Seguramente se preguntaran, ¿lo usamos en nuestra vida diaria?. Vamos a poner un ejemplo: Facebook. La inmensa red social que seguramente usamos casi a diario, es considerada un grafo social (social graph). En este grafo, cada persona es considerada un nodo del grafo y cada arista es la encargada de relacionar a dos personas. En facebook un amigo tuyo es una relación bi-direccional. Ejemplo A es amigo de B => B es amigo de A, entonces estamos hablando de un grafo no­-dirigido.

Cada arista de un grafo es representado como un par ordenado (u,v) donde (u,v) indica que existe una arista del vértice u al vértice v. Las aristas es posible que contengan un costo(cost), un peso (weight) o longitud (length). La valencia de un vértice es es el numero de aristas que conectan a este mismo. Continue reading

Finite State Machines

Standard

What is a Finite State Machine?

The simplest type of computing machine that is worth considering is called a ‘finite state machine’. Finite state machines may sound like a very dry and boring topic but they reveal a lot about the power of different types of computing machine. Every Turing machine includes a finite state machine so there is a sense in which they come first. They also turn out to be very useful in practice.

A finite state machine (sometimes called a finite state automaton) is a computation model that can be implemented with hardware or software and can be used to simulate sequential logic and some computer programs. Finite state automata generate regular languages. A regular language is a language that can be expressed with a regular expression or a deterministic or non-deterministic finite automata or state machine. A language is a set of strings which are made up of characters from a specified alphabet, or set of symbols. Regular languages are a subset of the set of all strings. Regular languages are used in parsing and designing programming languages and are one of the first concepts taught in computability courses. 

Continue reading

Algoritmos de Ordenamiento

Standard

Hola a todos, el día de hoy vamos a hablar un poco de métodos de ordenamiento. El conocer este tipo de algoritmos ayuda a mejorar el desempeño de algunas de nuestras aplicaciones. Mucho se ha hablado de este tema dada su importancia, ya que, existe un número considerable de algoritmos de ordenamiento, por lo que en este pequeño tutorial vamos a hablar solo de unos pocos. Así que comencemos.

Selection Sort

La idea principal de este algoritmo se basa en encontrar el mínimo o máximo elemento en el arreglo y ponerlo en la posición correspondiente para un arreglo ordenado. Por ejemplo, dado un arreglo de la forma A={7,5,4,2} que se desea ordenar de manera ascendente (de menor a mayor), lo primero es buscar el mínimo elemento en A, que es 2. Una vez encontrado, lo intercambiamos con la posición del primer elemento que se encuentra en A, es decir 7. Después, buscamos el segundo en el resto A y lo ponemos en la segunda posición y así sucesivamente. Ahora vamos a ver su implementación:

1
2
3
4
5
6
7
8
9
10
11
12
13
void selection_sort (int A[ ], int n) {
 int minimum;        
 for(int i = 0; i < n-1 ; i++)  
 {
   minimum = i ;
   for(int j = i+1; j < n ; j++ ) {
     if(A[ j ] < A[ minimum ])  {         
       minimum = j ;
     }
   }
   swap ( A[ minimum ], A[ i ]) ;
 }
}

Continue reading