Sunday, March 21, 2010

What Is Jamaicas Traditional Dress

Project 3: Calculate high power

The problem we chose for project 3 is to calculate higher powers.

Objective: Calculate high power in the shortest time possible using iterative algorithm and / or recursive

What is recursion: A recursive algorithm is one that makes a call to a subroutine inherent to it, making The steps or actions within it, can be repeated successively until one or several variables can be operated by turning it into a known fact. Subroutines properties allow us to expand its use to a myriad of programs, even the most complex.

A recursive algorithm can be used when needed to perform the same actions many times, although not more efficient than the iterative algorithm, it saves time to implement it.

As we work as group: The organization was not the best in our team, but with some effort towards the end, we could finish everything planned. I take an important role in this, because I was seeing more and more frequent as he was leading the team as assigned or corrected some work activities.

That was my contribution to the work: Make both algorithms (iterative and recursive), the 2 pseudocode from the place a code made by my partner in C, I corrected previously. I also graphs the asymptotic analysis with the program "gnuplot", correcting the introduction, conclusion and recommendations.
also computational complexity, the analysis step by step iterative algorithm just like my friend, I got the PDF to the Internet for safety.

That could improve in the future: The creation of pseudo and how individual organizations and with my team.

Links to blogs:

Dora Nelly González Martínez

Angel Joel Escamilla

Montemayor Jorge Martinez Chavez

Links
PDF document:

Show

Download



Thursday, March 4, 2010

What Happemed To Fakku

Project 2: Minimum Spanning Tree

The problem that I have chosen is: minimum spanning tree or minimum spanning tree (MST)

Objective:

is intended from a connected graph, construct a tree or subgraph with no cycles containing all vertices of the initial graph and the sum of distances or minimum weight possible. That is, we minimal expansion.

Applications:

The application of these problems lies in electrical communication networks, telephones, roads, rail, air, sea, etc. Where nodes represent power consumption, airports phones, computers, etc.

In distributed systems, weather data interpretation, computer vision, image analysis, feature extraction relationship, analysis clusters and superstructures search quasar, protein folding, recognition of cancer cells, and others).

example, if the cable television company to install cables in their neighborhood but they can only go for specific patterns or paths, it would be useful to know which are the shortest paths in order to save as much cable possible.

Another application is that of telecommunications networks to optimize the distances traveled and so the same material used. A similar to the latter is used in information networks between servers and client computers, to narrow the gap, increasing the speed of transmission and reduce costs.

another application, but less obvious is that the total minimum spanning tree can be used as an approximate solution to the traveling salesman problem (traveling salesman problem), remember to find the optimal solution to this problem is NP-Hard.

Representation:

Our graph has a number of vertices and branches or connections between these vertices, also has a number representing the distance or spread between the two vertices. Mathematically expressed G (V, E) where V = (v1, v2, ... vn) is a finite set of vertices (nodes) and E = Eij a finite set of links that represent the connection between terminals or stations. Each link has associated a positive real number denoted by W = Wij representing distance, cost, etc..


defined mathematically:




example instance and optimal solution:

transit Russia is planning the construction of a transit system connecting 7 major areas of the city. (A, B, C, D, E, F, G). Where the miles between them is a number representing the corresponding edge. Every mile of transit construction will cost 4 million.

The traffic you want to shorten the travel distance between the 7 areas but ensuring not overspend the budget. That is, seeking to optimize the construction per kilometer.

This is illustrated as



Taking into account the distances between areas can be solved as follows.

AD and CE edges are shorter, weighing 5 and AD was chosen arbitrarily therefore highlighted.
However, EC is now edge smaller cycles that is not, at a distance 5, so that is highlighted as a second edge.
The next edge, DF with distance 6 has been highlighted using the same method.
The following edges are smaller and AB BE , both with distance 7. AB is arbitrarily chosen, and highlighted. BD edge is highlighted in red, because it would form a cycle ABD if he had chosen.
The process continues to set the edges, with distance BE 7. Many other edges are marked in red in this step: BC (BCE form cycle), OF (DEBA form cycle), and FE ( cycle FEBAD form .)
Finally, the process ends with the edge away EG 9, and found spanning tree minimal.

The total obtained is 39 kilometers and the resulting cost is 156 million.

What if it had been built instead BE distance, the distance BC?
Answer: The cost would increase to 160 million.

formulate a corresponding decision problem:

there more than one way to solve the minimum spanning a graph G ( V, E)?

Yes, there are 4 algorithms for their solution, these are:

1. Kruskal Algorithm
2. Prims Algorithm
3. Borůvka Algorithm
with complexity O (log n)
4. Algorithm Edmond
With complexity O (log n) for a scattered tree and O (n 2) for a dense.


This problem was solved independently by Dijkstra (1959), Kruskal (1956) and Prim (1957) and the existence of a polynomial algorithm (which all showed) is a pleasant surprise, because a graph with N vertices may contain N-2 N subtrees T *.



The asymptotic complexity of the algorithm

The solution algorithm is NP-hard?

P resent an algorithm for the optimization problem

Prim Algorithm

The steps are:

1. any node is marked, will be the starting node.
2. Select the lower edge incident on node value set above, and mark the other node in the incident.
3. Repeat step 2 if the chosen edge marking a node link and the other is not.
4. The process ends when we have all nodes in the graph marked.

Example: determine the minimum spanning tree for the following graph:
· Following the Prim algorithm, we have:
or chose, for example, node 1 and mark it.
or chose the lower value-edge incident to 1, the (1, 3) = 1 trademarks and another node in the incident, the 3 .
or chose the lower value-edge incident on a node set and the other is not, the (1, 2) = 3 the mark and mark unmarked node, the 2 .
or chose the lower value-edge incident on a node set and the other is not, the (2, 5) = 5 mark and mark the unmarked node, the 5 .
or chose the lower value-edge incident on a node set and the other is not, the (5, 6) = 1 mark and mark unmarked node, the 6 .
or chose the lower value edge incident marked node and the other is not, the (5, 7) = 2 trademarks and unmarked node, the 7 .
or chose the lower value-edge incident on a node set and the other is not, the (5, 4) = 6 the mark and mark unmarked node, the 4 .
or FIN. We end as we marked the 7 nodes in the graph.
or Thus the resulting minimum spanning tree is:

Here is a pseudo Prim to solve it, and another example of execution.


JARNIK (Graph G, nodo_fuente s)
/ / Initialize all nodes in the graph. The distance you set it to infinity and the parent of each node to NULL
/ / Gluing in a priority queue where the priority is the distance, all graph pairs
per u in V [G] do
distance [u] = INFINITY
father [u] = NULL
Add (Queue, \u0026lt;u,distancia[u]>)
distance [s ] = 0
while tail! = 0 do
/ / NOTE: higher priority means that node whose distance [ u] is lower.
extraer_minimo u = (tail) / / returns the minimum and removes it from the queue.
per v adjacent to ' u' do
; if ((v ∈ tail) & & (distance [v]> weight (u, v)) then
; parent [v] = u
distance [ v] = weight (u, v)
; Update (cola, \u0026lt;v,distancia[v]>)




Image
Description
not seen
In the graph
In the tree
This is the starting weighted graph. There is a tree because it requires no circuits and in this graph there are. The numbers near the edges indicate the weight. None of the edges is checked, and the apex D was chosen arbitrarily as the starting point.
C, G
A, B, E, F
D
The second point is the closest to D : is 5 A away, B to 9 to 15 E and F 6. Of these, 5 is the smallest value, so we mark the edge DA.
C, G
B, E, F
A, D
The next vertex chosen is the closest to D or A . B is 9 away from D and 7 of A , E is 15, and F is 6. 6 is the smallest value, so we mark the vertex F and DF edge.
C
B, E, G
A, D, F
The algorithm continues. The apex B, which is at a distance of 7 A , is the following markup. At this point the DB edge is marked in red because its two ends are already in the tree and therefore may not be used.
null
C, E, G
A, D, F, B
Here you have to choose between C , E and G . C is 8 away from B , E is 7 away from B and G is 11 away from F . E is closer, then we mark the vertex E and EB edge. Other two edges were marked in red because the two vertices joined were added to the tree.
null
C, G
A, D, F, B, E
are available only C and G . C is 5 away from E and G -9 E distance. C is chosen, and marked with the bow EC . The arc BC also marked with red.
null
G
A, D, F, B, E, C
G is the only vertex slope and is closer than E F so EG added to the tree. All vertices are already marked, the minimum spanning tree shown in green. In this case with a weight of 39.
null
null
A, D, F, B, E, C, G


Finally I leave a link to watch and Prim's algorithm solves the problem step by step: Prime simulacion applet



Bibliography: