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

Matriz de Competencias del Programador

Standard

Esta publicación es el resultado de la experiencia como programador y de la lectura de varios libros, no tanto de una tecnología o plataforma en concreto, si no más bien de conceptos, patrones y buenas prácticas.

En particular decidí escribir al respecto por un par de blogs y un libro que fueron seminales para esta idea:
– La discusión por la cuál nació la idea de este post, aquí se referencia la matriz, y a aparte hay una discusión muy interesante a favor y en contra de estos puntos.
– La matriz de la cual me tomé la libertad de traducir y agregar mis comentarios.
– 97 cosas que todo programador debería saber. A través de historias y anécdotas de programadores experimentados, van ilustrando algunos de los puntos considerados en esta matriz.
Cabe mencionar que más que volvernos expertos en herramientas, yo valoro los atributos como que este fuerte en los conceptos necesarios para ser programadores exitosos, ya que debido a la experiencia, las herramientas, frameworks, etc., pueden variar, pero las buenas bases y prácticas aceleran la adopción de nuevas tecnologías y mejora el desempeño de los equipos.
Gran parte de estos puntos los estamos utilizando activamente en Hunabsys, para definir que buscamos en nuestros equipos de desarrollo, en qué los vamos a entrenar y como base para seleccionar algún nuevo integrante.

Continue reading

Finite State Machines: Part II

Standard

In the last post i tried to explain what a finite state machine is (see here). In this post, we’ll talk about regular languages and the equivalence between deterministic finite state machines, often called deterministic finite automata (DFA), and nondeterministic finite state machines, often called nondeterministic finite automata (NDFA).

Equivalences

One might think that NDFAs can solve problems that DFAs cannot, but NDFAs are just as powerful as DFAs. However, a DFA will require many more states and transitions than a NDFA would take to solve the same problem. 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