Friday, December 31, 2010

I Love You Christmas Commercial



evening, but surely, a warm thank you to Alexis Prudkin for their review in educ.ar (see here) ... And a very good start to the year for everyone!

Monday, December 27, 2010

Masquerade Theme Dress For Sweet 15

Journey to Planet Biplantar

One time Spock, the space traveler student of logic, came to the planet Biplantar. On this planet, as in many others visited by Spock, the whole population is divided into two groups: the truthful and the liars. The strictly true only makes statements true while lying only make false claims.

On this planet, in addition, every house has two floors, which, in a display of imagination, call lower and upper . In one plant (may be lower or higher may be, it depends on each home) live only true to the other plant, of course, live only liars. This does not mean that each is confined to a specific plant, as if they were prisoners. By contrast, those living in a plant can freely visit the other, but "live" (Moran, overnight, live) only one of two.

In villages or small towns the houses are of simple structure and any visitor always knows what floor of the house is. In large cities, however, houses may have a very complex structure, labyrinthine would say, with false steps that seem to lead to plants lacking, false windows with landscapes (gardens created by artificially high or games of mirrors), false doors and other traps for the collection so that, after a transit time for their rooms, visitors can lose track of if you are in the lower or higher (although the resident never lost and always knows where you are).

On his first day on the planet Biplantar, Spock was in a house in a small town. He had arrived an hour or two, but still had no idea who lived on each floor. At that time he saw a resident (who lived in that house, though not necessarily on the ground where they met) and after greeting him, Spock asked which group (ie, whether it was truthful or lying). The native replied:

If I said: "If there is a floor above us then I live in it", then you could deduce which group I belong.

Spock deduced from this information immediately on what the true and living plant which plant, liars. Maybe other things concluded, perhaps not. (But note that the fact that Spock has enough information to make a certain deduction does not necessarily mean that we also have.)

The questions are: Does native spoke to Spock was truthful or a liar ? What floor of the house were the two, the upper or lower? Which of the two plants lived truthful?

For each question, the challenge is either to answer or demonstrate that the information you have is insufficient to give an accurate answer.

Have fun ...

Tuesday, December 21, 2010

Heart Palpitations Kidney

A theorem on 0 ^ 0

Theorem: Let T a theory that speaks to the non-negative integers and their operations, if this theory is defined as 1 0 ^ 0 then there is no contradiction.

Demo: If we define a non-negative integers in the context of the theory of finite sets F (defined as the cardinal of the same sets) then the statement 0 ^ 0 = 1 can be proved as a theorem (see here.) Therefore, the finding is consistent with the theory F, ie, FU {0} ^ 0 = 1 is consistent.

Therefore, TU {0 ^ 0 = 1} is also consistent (regardless of T consistent and defines a non-negative integers), because, otherwise, the same contradiction arises in TU {0 ^ 0 = 1} also exist in FU {0 ^ 0 = 1}, but this alleged contradiction, we have seen, does not exist.

... everything else is irrational prejudice.

Saturday, December 18, 2010

Difference Between A G String Wax And Brazilian

Riddler in 6 by 6

The protagonist of this problem is a board of 6x6 ...

... and the goal is complete in accordance with the following rules:

1. Each of the boxes with a circle must contain a number, which can only be, in each case, a 1 or a 4. In the other boxes will not numbers.
2. At the end, there must be at least 1 and at least a 4.
3. Some of the remaining boxes contain mines (by way of help, one is already in place), others may eventually become empty.
4. boxes with circles do not contain mines or may be empty.
5. Minesweeper As in Windows, each number should indicate how many mines there are in boxes that are around him.

Have fun ....

Thursday, November 25, 2010

Dvd Third Party Decryption

Weird (but true)

0.999 .... (With infinite nines) is an integer.

Sunday, November 21, 2010

Nico Stremaing Megavidio

The Omegon and all that ... (Part 17 what end?)

( A part 16 - part 18 A )

The beginning and end

We said in the previous chapter, in the early 1870's, Georg Cantor came to Halle. Cantor began working under the direction of Eduard Heine who proposed the following problem: Is it only the Fourier series decomposition of a periodic function, even if it is at all time, an infinite number of singular points? (Heine had proved that the answer is positive when the number of singular points is finite.)

few months later, around 1872, Cantor got a first answer: the decomposition is unique provided that the singular points of the function are distributed on the real line in a certain way. But Cantor is not found, in principle, a clear and precise way to state what conditions must comply with this distribution.

As a theorem not only be shown, but this demonstration must be written so that it is understandable [the shows are written and read in human beings], Cantor was devoted to the problem, essentially linguistic, find a way clearly explaining what the assumptions to be met by the set of singular points for the decomposition in Fourier series was unique. And it was in the course of solving this problem which Cantor created a concept that would later career in mathematics: the concept of accumulation point .

is not necessary here a precise definition of this concept (this link is a very brief explanation - in this post extending ). Suffice to say that, given a set P of real numbers, we can define (the terminology and notation are Cantor) a set P ', which is called the derived set of P , which contains all accumulation points P. This set P 'can be equal to P, or P may contain, or may be the empty set, etc. For example, if P = [0.1], then P 'is set to be the same [0.1].

But we can also calculate the derivative of the derivative, P '. And the derivative of the derivative of derivative P''', etc. In the case of P = [0.1] all these successive derivatives remain the [0.1], but in other cases different sets are obtained. For example, if P = {0, 1, 1 / 2, 1 / 3, 1 / 4 ,...} then P '= {0} and P is the empty set.

Cantor noted that in some cases these successive derivations ending in the empty set (as in the second example), while in other cases this never happened (as in the case of [0.1]). Cantor sets of first type called the first and second type to second. and stated his theorem as follows: if the singular points of a periodic function are a set of first type write sing its Fourier series is unique. Since finite sets out to be the first type, the result of Cantor included as a special case that of Heine.

But Cantor was not consistent with this result and kept thinking. He noted that this process of successive derivatives could define a "derivative infinite" means the limit of P (n) (nth derivative of P) with n tending to infinity. Sien embargo, so far, still was not making use "dangerous" of infinity, still in the familiar terrain of infinite potential, infinite limit. However, he was on the verge of great discovery, which occurred when, at one point, he found an example of a set P such that P (infinity) = {0} ... and therefore (P (infinity)) '= P (infinity + 1) = {0}' = empty.

What was this "infinity + 1"? He was not the infinite potential, the limit because the limit for both "infinite" as "infinity + 1" are the same. But in this case was not the case, as P (infinity) and P (infinity + 1) were different outfits. Then it was a different concept of infinity.

must have been very traumatic for Cantor the face to face with him for so many centuries banned and feared infinite potential. So much so that it took ten years to accept that what I had on hand was nothing more, nothing less, than a way of counting beyond infinity. And when I finally accepted in 1883, published an article entitled Fudamentos for a General Theory of Sets , where Cantor includes his much-quoted phrase: "I was taken by the logic of my research to break with traditions that had taught me to respect "[some translations say" worship "]. In this work, also changed the usual symbol of infinity (the "horizontal eight) by the Greek letter omega, in order to emphasize that" his "infinite was not the limit. In that work, also dubbed "ordinal" these new "infinite numbers" and began the story I have narrated.

And here the story ends, or perhaps begins, because the paradoxes of Cantor's theory led to the Crisis of Foundations, the program of Hilbert, Gödel's Theorem, to Turing machines, jobs Frege, the intuitionism of Brouwer, ... Remains in the desire of the reader deep into the maze, a labyrinth of which we have shown only the entry and that, fortunately, has no outlet.

The End? - It seems that no ...

(16 A Part - A part 18)

Friday, May 21, 2010

Help How To Stop Breakthrough Bleeding

RSA Encryption asymptotic analysis

Now demonstrate an example of the review exercise 2: asymptotic analysis. This was how I answered the question 2 previous examination.

2. Find an asymptotic complexity function f (n) so the function g (n) defined experimentally by twelve points in the table below is $ \\ Omega f (n) $.

Justify this with a graph and discusses the quality of the elevation gained.






1.038
n
g (n)
n
g(n)
n
g(n)
3
15
130
3,800
3,982
190,000
12
170
203
7,500
5,002
240,000
30
600
603
22,000
10,393
550,000
57
1,500
42.000
40.039
2,600,000

First notice that the first 4 data, f (n) may be n 2 because 3 2 approaches 15, 12 2 approaching 170, 30 2 approaching 600 and 57 2 1.500 approaches but in calculating the past, no: 3.982

2 = 5.002
15,856,324 2 25,020,004
= 10.393 2 = 108,014,449
40.039 2 = 1,603,121,251

As asymptotic complexity is more important to large bodies 2 n grows too fast, we'll try to function but was obviously less than n.

3.982 1.5 5.002 = 251,276.5054
= 353,765.5438
1.5 10.393 1.5
= 1,059,525.4449 40.039 1.5 = 8,011,702.8514

too, now with power 1.4:

3.982 1.4 5.002 = 109,683.6155
1.4 = 150,938.8936
10.393 1.4 40.039 = 420,181.8590
1.4

= 2,776,364.6813 Enough for me, g (n) = n 1.4 now seek a lower level.

know that a lower bound g (n) can be f (n) = log n, but not so close an 1.4, a more serious immediate n 1.35, so we'll take it and compare:

3.982 1.35
= 72,466.4013 5.002 98,592.5224 = 1.35
10.393 1.35 40.039
= 264,606.3437 1.35 = 1,634,377.4061

data are lower than 1.4 n, then f (n) = n 1.35 be our lower bound or $ \\ Omega f (n) $.

see the graph:

As you can see the red line represents our function g (n) approximately, the green lower bound f (n) and the blue the experimental data in the table. The lower bound is quite good because we did not go to log n to make it less than the linear n 1.4 1.35 but an which is just below g (n).


Finally I wish to comment on how do this post because someone could serve in the future. The powers are like that and n, is made with a tool that is already included in the blogs is called superscript and subscript and become writing \u0026lt;sup> \u0026lt;/ sup> and \u0026lt;sub> \u0026lt;/ sub> respectively, while symbols such as $ \\ Omega $ are adding to the gadget blog (java code) to recognize LaTeX writing, but I already explained in this post .

other hand the graph I made with a program called gnuplot download and free use, when downloading a document I include tutorial or guide to learn and use. It is a program based on command line but is very powerful.

Monday, May 17, 2010

Pokemon Chaos Black-pokemon List



Encryption (encryption, encoding). The Encryption is the process of re illegible information considered important. Once encrypted the information can only be read by applying a key.

is a security measure that is used to store or transfer sensitive information should not be accessible to third parties. Can be passwords, credit card numbers, private conversations, etc.

I recently read about a method for encrypting information that is very interesting, was created in 1978 and is called RSA, which stands for its creators: Rivest, Shamir and Adleman, is based on the difficulty of factoring large numbers prime numbers, for example, it is easy multiply 2 primes for a third but it is difficult from the third to get his 2 prime factors. In fact this is the best encryption method used there and banks, government institutions, etc. A bank of Monterrey, NL using this system supplied then by RSA, The Security Division of EMC is Banorte :



Most prime numbers used in RSA encryption are 250 digits or more, ie for more because security is later factored a prime number is the bigger. Theoretically raw 250-digit numbers takes millions of years to factor.

it works exactly

turns out that:

$ c \\ equiv m ^ {e} \\ mod \\ n $
$ m \\ equiv c ^ {d} \\ mod \\ n $


If and only if $ n = pq $, q are primes
$ 1 \u0026lt;e \u0026lt;\\ phi (n) $ and $ gcd (e, \\ phi (n)) = 1 $, with $ \\ phi (n) = (p- 1) (q-1) $
and meets a $ d \\ equiv 1 \\ mod \\ n $
m c would be a numeric message against encrypted part.
and serious public key to encrypt d the private key to decrypt.
Note: phi (n) is the Euler function. Procedure



  1. two numbers p and q are sought to be cousins.
  2. n are obtained by multiplying p and q, and phi (n) by multiplying (p-1) and (q-1).
  3. and is looking for a number that has no common divisors phi (n), which divides phi (n) +1 no residue.
  4. d It is the division phi (n) +1 from e.
  5. now have everything and be the public key (e, n) while the private is (d), like the rest of the numbers (p, q, phi (n)) are not going to need, can be destroyed for safety.



Example Suppose we choose:

$ p = 11, \\ q = $ 23, two small primes ideals for our example.
Then calculate n: $ n = pq = 253, $
compute phi (n) $ \\ phi (n) = (p-1) (q-1) = (11-1) (23-1) = 220 $
And e: $ $ 1 \u0026lt;e \u0026lt;\\ phi (n) = 220 \\ and \\ gcd (e, 220) = 1 $ $.
it meets a number is 13: $ $ 1 \u0026lt;13 \u0026lt;\\ phi (n) = 220 \\ and \\ gcd (13, 220) = 1 $ $
Now d is the division of phi (n) +1 between and $ \\ frac {221} {13} = 17 $. We note that we have: $ (17) (13) \\ equiv 1 \\ mod \\ $ 253, or is, phi (n) +1 can be divided by and with residue 0.

Check:


With the message: 11
$ c = 11 ^ {13} \\ mod \\ 253 = $ 132
$ m = 132 ^ {17} \\ mod \\ 253 = $ 11


Another example

clearer Another example would be:

$ p = 3, \\ q = $ 11
$ n = $ 33
$ \\ phi n = (3-1) (11-1) = 20 $
$ e = $ 7 because it complies with 1 \u0026lt;7 \u0026lt;20 and gcd (7, 20) = 1
$ d = \\ frac {\\ phi (n) +1} {e} = \\ frac { 21} {7} = $ 3

Check: With the message

m = 2

$ c = m ^ {e} \\ mod \\ n = 2 ^ {7} \\ mod \\ \\ 33 = 128 \\ mod \\ 33 = $ 29
$ m = c ^ {d} \\ mod \\ n = 29 ^ {3} \\ mod \\ 33 = 24 389 \\ mod \\ 33 = $ 2

We can see that if we introduce the message m = 2 is encrypted in c = 29 and can be decrypted with the private key d. Now with our keys can encrypt and decrypt any message Numeric longer be.

Note that if you are making very large exponentiation operations, you must use the binary algorithm potentiation saving operations.

Some ways to convert text to numbers is to apply a numerical key for parties or simply making ASCII values \u200b\u200b(although this is not so sure). More information




http://www.rsa.com/
http://www.tagoror.com/enciclopedia/es/wikipedia/f/fu/funcion_phi_de_euler.html
http://boards5.melodysoft.com/canalingenio/la-funcion-phi-de-euler-225.html
http://neo.lcc.uma.es/evirtual/cdd/tutorial/presentacion/rsa . html

Now I will show the pseudocode I'm doing, not finished but I get the idea what I do to implement it.

/ * Pseudocode for encryption, RSA method * / # include

< stdio.h >
#include < time.h >
#define p long 47
#define q long 13
long p, q, n, h, e, d, m;
char M[4000];
long a[3], b[3], m[3], res;

n();
h();
e();
d();
string();
ps();
encrypt();
decrypt();
show-string();

main()
{
  n();
  h();
  e();
  d();
  put-string();
  ps(M)
  encrypt(m);
  decrypt(c);
  ps(m);
  show-string(M);
  getch();
}

n()
{
  //Elegir 2 primos (p y q)
  n=p*q;
}

h()
{
  //Funcion phi Euler
  h=(p-1)*(q-1);
}

e()
{
  //e   long fac[3];
  e=(5*h)/8;
  fac[0]=e;
  fac[1]=h;
  gcd();
  while (fac[1]!=1&&)

{e + +;
gcd ();}



} d ( )

{/ / Extended Euclidean Algorithm to calculate
/ / the modulo multiplicative inverse: e (mod h)
a [1] = 1;
b [1] = 0;
m [1] = e;
a [2] = 0;
b [2] = 1;
m [2] = h;
res = e-(h * m [2]);
while (m [2]! = 1) {

/ / Run the values
a [0] = a [1];
a [1] = a [2];
, b [0] = b [1];
b [1] = b [2];
m [0] = m [1];
m [1] = m [2];
/ / Calculate last
values \u200b\u200bof [ 2] = a [0] - (a [1] * res);
b [2] = b [0] - (b [1] * res);
m [2] = m [0] - (m [1] * res);}

d = a [2];}

string
() {

printf ("Enter the message you want to encrypt: \\ n");
scanf ("% s", M);}


ps (char x) {

/ / Convert string to numbers or vice versa
if (isalfa (x)) {
tonumber
m = (x);
return m;

} else {

M=toalfa(x);
      return M;
    }
}

long encrypt(long)
{
  c=pow(m, e) mod n;
  return c;
}

long decrypt(long)
{
  m=pow(c, d) mod n;
  return m;
}

show-string()
{
  printf("%s", M);
}

gcd()
{
  //Algoritmo euclidiano
  fac[0]=e;
  fac[1]=h;
fac [2] = factor [0]% fac [1];
while (fac [2]! = 0) {
fac
[0] = fac [1];
factors [1] = factor [2];
fac [2] = factor [0] % fac [1];
}}






pseudocode and will continue improving Improve public information contained herein. They can shop around from time to time to see the progress. Also add more links to information if they are unsure how to get all the numbers for the keys, is supposed to use certain methods of factorization and the Euclidean algorithm we learned last class in room but for lack of time not show you here.

Updated May 18, 2010: I corrected a few important things and add one more example.
Updated May 21, 2010: Using binary algorithm potentiation saving operations.

Sunday, May 16, 2010

How Fast Can A Veyron Do A Quarter Mile

Project 5: Isomorphism

The topic I chose is called Eulerian cycle, Euler is pronounced oil-er. " In this issue also called Euler circuit, Euler circuit, Euler tour or euler tour. Definition



An Eulerian cycle is a path in a graph G that begins and ends at the same vertex, which includes every edge of the graph exactly once and may have repeated vertices, ie, a cycle that includes all the edges of E and that these do not recur. Similar Topics



This topic is extremely mind related to Eulerian path that is about finding a path in a graph G so as to include all edges without repetition, and also compared further with the Hamiltonian cycle about a cycle that includes all vertices at once. Sources



This conundrum arises with the problem of the 7 pu entities Königsberg (eighteenth-century German town situated on the river Prague) which was decided by the Swiss mathematician Leonhard Euler in 1736 and published in an article entitled Solutio ad geometriam problematis pertinentis situs (Solve a problem with the geometry of position).

The problem is about the 7 bridges through the city connecting 2 islands, once each.


Königsberg

roads bridges are white on the gray river.

Euler solved the problem by imagining the territory of the islands and the river with a connected graph.

To understand the problem of the 7 pu entities Königsberg, imagine that the edges are the bridges and the vertices are islands or territories in the following image.


Now we must try to find a cycle that includes all the edges so that the line has not been repeated edges.

...


Euler discovered that this is impossible in this graph!, But it was he who gave the mathematical proof but was Carl Hierholzer until 1873.

What I said was Leonhard Euler (in our terms) a Eulerian cycle in a graph G exists if and only if:
  1. The graph was connected, ie there is at least one way to reach any vertex
  2. The degree of all vertices of G is an even number or put another way, if there is one vertex of odd degree.
And as you can see, the degree of each vertex in the graph is an odd number of so that not even close to have a Eulerian cycle and that if we create it we should add or delete the three middle edge of the graph or to add 2 edges. Explanation



We can understand the argument of Euler because in an Eulerian cycle as we pass through a vertex we have to have 2 paths (edges) or any other even number, this is gra (e) mod 2 = 0, one to get the other to leave, or vice versa and complete the cycle, otherwise we would be "stuck" in the same vertex or else we might never return, in any case always an edge to go missing to complete the cycle.

Problem must resolve

can say that Euler solved the problem following decision:
"There is a path that includes all the edges without repeated, starting from a vertex v back to the same vertex v in a graph G ?. "

Without their algorithm to determine this decision problem, we should make all possible routes to determine whether there is any Eulerian cycle and it will have an asymptotic complexity O (n!), but with the simple rules we get the complexity O Euler (n). Example

Eulerian cycle

is interesting that no matter how large or complex a graph, if it complies with the 2 above conditions (1 and 2), this has an Eulerian cycle.


In this picture the graph is also related to the degree of all vertices is an even number. Algorithm

problem

several algorithms are possible depending on what it intends to solve, for example, one that solves the decision problem: There is an Eulerian cycle in a graph G?, One that solves the problem of decision: What is an Eulerian cycle in G?, and even a third party to solve the decision problem: What are all Eulerian cycles in G? (A variant of above). Besides

variations may exist Eulerian cycle optimization to solve problems like: Find an Eulerian cycle so as to travel some vertices before others, in this case could balance the vertices according to preference and optimizing the way to go to get the best possible cycle. Algorithm
existence

  1. For each vertex in the graph will analyze their degree (ignore the neighbors, it is trivial).
  2. If anyone has an odd degree, we can say that there is no Eulerian cycle in the graph and ends the algorithm.
  3. If at the end of analyzing all the corners, never said there was no Eulerian cycle, then said that if there is a Eulerian cycle.
search algorithm (which is an Eulerian cycle?)

  1. started at a vertex chosen at random or
  2. imagine starting a barrier to cross an edge chosen at random.
  3. The barrier will move until it can reach a vertex with degree other than 1. The barrier stored in a stack each edge of the journey he visited, in order.
  4. Note: This barrier aside a way of arriving at the initial vertex, ensuring the cycle.
  5. barrier each time you move to a new position, remove the edges covered.
  6. other hand imagine a traveler travel edges at random and that of course does not have access to the removed edges in the path of the barrier.
  7. Every time you move the passenger to a nearby ridge, keep the edge covered in a list or array and removes the same edge (not to go through there.)
  8. When the barrier and the traveler can not move to any neighboring vertex, which it says is the Eulerian cycle, showing first the list and then the stack whose items appear in reverse order of their introduction.

Note: There is probably a better way to find a Eulerian cycle due to time but I just thought in this algorithm. Computational Complexity



In the algorithm consider the instance of there n as the number of edges in the graph, in step 1 is known from a series of n times to conduct operations within it. In the second step (which is inside the loop) modular operation is performed with 3 and compared with 0 to determine if the degree is odd, these are 2 operations (2n so far). And the third step is waiting to complete the cycle to say that if there is a Eulerian cycle. In total was:

$ O (2n) $, as the constants do not matter is $ O (n) $. The problem of existence of an Eulerian cycle is in P because the complexity O (n) is polynomial.

pseudocode of the algorithm

Decision problem (there is an Eulerian cycle?)

# define num_de_vertices 4000
main ()
int i, grad [ num_de_vertices ];

for (i = 0 i \u0026lt;= size (grad []) i + +)
if (degree [i]> 1)

if (degree [i]% 3 == 0)
Puts On Eulerian cycle exists;
goto end;
else puts
There Eulerian cycle;
end


decision problem (which is an Eulerian cycle?)

# define num_vertices 4000
int n, end = 0, shift = 1, barrier, travel, view, edges [400] [ 400], / / \u200b\u200bedges [] [] is nothing more than an adjacency matrix

main ()
datafile read / / Is the information in the graph
ver = rand (0)% 3 / / We choose a vertex to the "random" barrier =
see;
while (! fin)
switch (shift) / / shifts the barrier functions and traveler
case 1:
fbarrera ();
           break;
      case 2:
           fviajero();
           break;
  if (detenerbarrera==true&&detenerviajero==true)
print path (); / / The end of the day and show results
print stack () / / in the correct order
end


fbarrera ()
if (degree (barrier) == 0) / / If you do not have anywhere to go, check over
detenerbarrera ();
, end = true;
if (degree (barrier) == 1) / / If there is only one way possible, moves
battery (barrier) / / Stores the path when it moved
barrier = neighbor (barrier) / / This moves
delete (barrier, neighbor ());// barrier that path is removed / / to avoid repeating
shift + +;
end


fviajero ()
if (degree (traveler) == 0) / / If you do not have anywhere to go, check over
detenerviajero ();
way (passenger) / / Storing the path is
traveler = neighbor (passenger) / / Moves an edge allowed
delete (traveler, neighbor (traveler ));// To avoid repeating edges
shift -;
end


neighbor (int x) int i
;
for (i = 0; i \u0026lt;= num_vertices; i + +)
if (edges [x] [j] == 1) / / If there is an edge incident on x, / / \u200b\u200breturns the vertex to the leading edge
return alpha (j) end



remove (int t, int k)
edges [t] [k] = null; / / By removing the relationship ensures remove
edges [k] [t] = null, / / \u200b\u200bin any direction
end


asymptotic analysis algorithm

For the first algorithm in the worst case is $ O (n) $ because:

is assigned a constant (num_de_vertices). The
+1 step for creating a cycle where the complexity depends upon the processes within it.
two comparisons are made, grad [i]> 1 and grad [i] == 0 mod 3, and a modular operation, mod 3. N +3 steps

We then O (3n +3) but as the constants do not matter is O (n) and is polynomial.

In this pseudocode the best is O (1) this is because the first vertex can be introduced odd degree and therefore eliminate the possibility of owning a cycle graph Eulerian, then the average case would be $ O (\\ frac {1 + (3n +1)} {2}) $, as the constants are trivial, is still $ O (n) $.


For the second algorithm (search) is $ O (n) $ because:

declare a constant, num_vertices, and a variable shift. +2 Steps
attach a vertex to "chance." Match
barrier +2 steps and see. +1
step command are exchanged and fviajero fbarrera program in turn, this depends on how fast we find the Eulerian cycle.

fbarrera to compare if I end up searching for the cycle (1 transaction), compares the current vertex degree (1 stored procedure if its degree).
steps
+2 Here comes the interesting part, if the vertex degree is 1, the barrier can move forward and do the following:

  • Stores your journey on the stack (1 operation) changes of position (1 transaction) to a neighbor node to find it done in about n steps depending on the extent of current vertex (n operations so), and removes the edge that ran (2 operations). n +4
  • steps increases the shift. +1 Step

fviajero stores its way into an array or list, moves (1 operation) to a neighbor node to find it done in about n steps depending on the degree of current vertex and removes the edge that ran (2 operations). n +3 steps


The result is $ O ((t / 2) (2n +9)) $, where t is the number of times it turns.

Note: Actually the asymptotic complexity is lower than before but I will not get into details of numbers. Finally

constants are ignored and we are left with $ O (n) $. The problem is P , polynomial time.

data structures used

Use dimensional arrays in the first pseudocode and dimensional arrays, batteries and ready in the second. Applications



Eulerian cycle An application may be in the optimization of route maps, for example if we were asked if there is a way for a tourist trip so that they do not flown any of the paths more than once or in the extended version, which is the best cycle for tourists visiting certain places before others and without going through the same paths over than once?.

also just occurred to me that can be applied in determining the flexibility in decision problems in large institutions or companies, for example if you create a graphical model to simulate the choices that you can choose a company with edges and final states to carry out what with vertices chosen, one could know then the degree of flexibility in decisions of each state depending on whether there is an Eulerian cycle that allows return to the initial state by different options (different edges), it becomes more real if we allow the elimination of options over time, ie remove edges from time to time, either randomly or not. Curiosities



  • The 7 Bridges of Königsberg were bombed and destroyed by the Allies in 1944 and only 5 were rebuilt.
  • The city Königsberg was renamed Kaliningrad and is now part of Russia.
  • Now you can visit the bridges with an Euler path but not an Euler cycle.
  • The problem of the 7 bridges of Königsberg solved by L. Euler gave way to the topology, a branch of mathematics which is responsible for studying properties of geometric objects that have to do with the relative position between points. Sources


http://www.itl.nist.gov/div897/sqg/dads/HTML/eulercycle.html
1 2
http://www.economicexpert.com/a/Eulerian : path.htm http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK4/NODE165.HTM
3 4
http://books.google.com.mx / books? id = 7XUSn0IKQEgC & pg = PA502 & lpg = PA502 & dq = euler + cycle + Applications & source = bl & ots = z6cFQPOS0e & sig = gCQCrKXT4T2ZWCFZLVtJ9k-juhk & hl = en & ei = x-DpS5DhHoyCtgOX3IX-Bw & sa = X & oi = book_result & ct = result & resnum = 9 & ved = 0CFkQ6AEwCA # v = onepage & q & f = false Http://theoremoftheweek.wordpress.com/2009/09/29/theorem-8-eulerian-circuits/
5 6
http://www.personal.kent.edu/ ~ rmuhamma / Algorithms / MyAlgorithms / GraphAlgor / eulerTour.htm
http://mathworld.wolfram.com/EulerianCycle.html
7 8 9 http://mathforum.org/isaac/problems/bridges2.html
http:// www.cs.sunysb.edu/ ~ Skiena / combinator / animations / euler.html
10 http://mathdl.maa.org/mathDL/46/?pa=content&sa=viewDocument&nodeId=1310&bodyId = 1452 (paragraph explains each show written by L. Euler)
11 http://math.dartmouth.edu/~euler/docs/originals/E053.pdf
12 http://www.iesezequielgonzalez.com/matematicas/grafos.htm
13 http://www.mathematische-basteleien.de/house.html
14 http://books.google.com.mx/books?id=aFDWuZZslUUC&printsec=frontcover&dq=CRC+concise+encyclopedia+of+mathematics&ei=f1z0S9qxLpTukgSM_YS8Bw&cd=1
15 http://books.google.com.mx/books?id=TrXd-gxPhVYC&printsec=frontcover&dq=The+algorithm+design+manual+2&ei=x1z0S9aPFJf4lASauI2uBw&cd=1
16 ~ Jlrodri/Topgen5/introduccion.html http://www.ual.es/



Self-Assessment Review


I think make a good job with the blog report, included all requirements, add images, try to explain in the simplest way possible, on the other hand showed the algorithm that I thought to solve the problem, and some parts I asked the reader's participation, was very comprehensive and included 16 source links at the bottom for readers to find more information on the subject.

Regarding the presentation, the first few seconds at the beginning was a little nervous but after I was as time passed and I concentrated on the theory, the number of slides to show that I found exceeded 2 for the time of this opportunity but I explain them to jump and very fast, yet so focused on only those 2 slides the later example of the algorithm and was easier for the public to understand the solution to the problem of the latter form. The design of the presentation was very simple to keep everything clean, clear and concise.

participant also made the public presentation and comment a little curious about the Eulerian cycle problem afterwards. The time I was a bit late but the limit agreed but it was worth those extra seconds to the public.

Thursday, May 6, 2010

Welded Wire Stretchers

Eulerian Cycle Test

That is isomorphism?

The property of a graph that shows that the graph can be obtained from other re label their vertices. Mathematically speaking

:

G = (V, E) and G '= (V', E ') are isomorphic $ G \\ cong G' $ if there exists a bijective f between their respective sets of vertices V and V ' preserving its surroundings:

$ $ \\ forall v, w \\ in V, v ~ w \\ leftrightarrow f (v) ~ f (w) $ $

The idea is simple, all the neighbors who belong to a vertex, must also belong to the vertex of another graph.

For example if the graph G (1, 5) has a vertex v whose neighbors are {a, b, c, d, e} and a graph M (1, 5) has a vertex x whose neighbors are also {a, b, c, d, e}, then the vertex v is the same as the vertex xy graphs G and M are the same except for its location in space. That is isomorphism, but is clearer with an example:


positions in the image of the vertices change as do some edges, but all the vertices remain the same neighbors, then both graphs are isomorphic.



Sources


http://mate.cucei.udg.mx/matdis/5gra/5gra6.htm Http://web.udl.es/usuaris/p4088280/teaching/terminologia.pdf

http://mathworld.wolfram.com/GraphIsomorphismComplete.html

What Happens If You Don't Treat Herpes Long Term



Test 1:

$ $ \\ int \\ int \\ frac {\\ sqrt {2x} ^ 7 \\ cos ^ 3} {8x} {9 - \\ sqrt {4x ^ 2-672}} dx $ $ $ $ \\ LaTeX! $ $

I just added a feature that I can interpret LaTeX code in the blog, how to do this is easily described in this mini guide . Here is another guide different that does the same (also provides javascript code), choose the one you like.

Summarizing the procedure: Copy the code in the gadget guide and agregenlo as HTML / Javascript to your blog.

Now you can enter any mathematical symbol between 2 signs of money $.
Example: (sign money) LaTeX code (money mark)

Some other examples:

$ $ \\ exists \\ forall \\ wedge \\ vee \\ or \\ bigcup \\ notin \\ nabla (\\ partial \\ int \\ hbar \\ prod \\ delta \\ mu \\ lambda \\ alpha \\ zeta \\ sqrt {\\ sum \\ gamma \\ eta} \\ ointH \\ Gamma) $ $
 

Sunday, April 25, 2010

Teachers Smelly Nylon Feet

writing LaTeX Project 4: Merge sort

The project that my colleagues and I chose is an algorithm that sorts an array a recursive partitioning method (merge sort or order by blending).

I did:

Help edit the presentation, create a pseudo, I was part of the implementation document interactive and went to the Internet.


As I came out:

The design of the presentation was correct, clean and orderly, the pseudocode that did not convince me at all because I did it very fast almost without thinking and maybe I should add more details but on the other hand is well keep it simple and general so that the public will understand quickly, and as for interactive implementation'm not sure to give the correct order though However you understand the steps of the algorithm.

could be improved:

probably pseudo length, instead of leaving it without details, to create the code in C and on the other side does not leave things to last minute.

In what ways I'm well and I still need to improve :

I'm okay to take command of the team because almost nobody takes the initiative, also in the extra effort to make things right. I'm bad to the lack of responsibility and leave everything at the last minute because even want to make an extra effort to improve things, and not enough time. Helped

others or support me in them:

definitely help others, if there is time I explain how some things would work, if no time I tell them after I tell them to move forward on the project and that change try to read some more about the subject.

Who is responsible for coordinating the work:

On all computers to which I belonged, I'm always me who coordinated the work, I see the capabilities and formed smaller groups, I ask that each who does something like others to cooperate all together (when possible). What

I took paper:

who coordinates the others and makes the code or pseudocode. I take a lot of initiative and I expect the same from others but most likely will not happen.

personal reflection:

I miss going to extend the pseudocode for the race, being honest is not that manage my time if the organization with the other members was difficult, we plan to work things together and agree dates to meet but the schedule along with the distance prevented us from many things.

Links to blogs:

Angel Joel Escamilla Montemayor

Jorge Martinez Chavez


Download:
Download
Show

Interactive Dynamics: Java Applet

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: