https://www.cubawiki.com.ar/api.php?action=feedcontributions&user=157.92.4.151&feedformat=atomCuba-Wiki - Contribuciones del usuario [es]2024-03-29T12:52:54ZContribuciones del usuarioMediaWiki 1.39.2https://www.cubawiki.com.ar/index.php?title=Pr%C3%A1ctica_3_(LyC_Verano)&diff=3124Práctica 3 (LyC Verano)2007-02-22T03:42:36Z<p>157.92.4.151: /* Ejercicio 11 */</p>
<hr />
<div>== Ejercicio 1 ==<br />
<br />
Sea f: N -> N computable. <br />
<br />
=== Item A ===<br />
<br />
Demostrar que la función<br />
<br />
g(x) = min {y : f(y) = x} si existe y tal que f(y) = x<br />
se cuelga si no<br />
<br />
es parcialmente computable.<br />
<br />
'''Solución'''<br />
<br />
Damos un programa que computa g.<br />
<br />
Z1 <- X1<br />
[A] Z3 <- f(Z2) //Dado que f es computable, supongo que tengo el progama homónimo que la calcula, <br />
//y además sé que no se cuelga.<br />
IF Z3 = Z1 GOTO B<br />
Z2 <- Z2 + 1<br />
GOTO A<br />
[B] Y <- Z2<br />
<br />
La idea es sencillamente chequear si f(y) = x, empezando con y = 0 e incrementando de a uno. Si en algún momento esto ocurre, ese y es el que busca la minimización de la primer rama de g. Si no ocurre nunca, el programa sigue incrementando el valor chequeado infinitamente, o sea se cuelga.<br />
<br />
<br />
=== Item B ===<br />
<br />
Demostrar que si f es además biyectiva, f^-1 es computable. <br />
<br />
'''Solución'''<br />
<br />
Notar que el programa que dimos computa f^-1. Como f es biyectiva, es inyectiva. Esto asegura que el resultado de la expresión min{y:f(y) = x} devuelve no sólo el mínimo y, sino el único. Además, la sobreyectividad nos asegura la existencia de tal y, con lo cual el programa no puede colgarse.<br />
<br />
== Ejercicio 2 ==<br />
<br />
Sea f: N -> N una función computable y sobreyectiva. Probar que existe una función computable e inyectiva g: N -> N tal que g(f(x)) <= x para todo x perteneciente a N.<br />
<br />
'''Solución'''<br />
<br />
Es casi el mismo problema que en el ejercicio 1. Podríamos ver a g como una especie de generalización de f^-1. Si f es inyectiva y sobreyectiva (i.e. biyectiva) se puede definir una f^-1 tal que f^-1(x) = g(f(x)) = x, para todo x natural.<br />
<br />
Si debilitamos la hipótesis sobre f, y sólo pedimos que sea sobreyectiva, pasa a haber más de un xi tal que g(f(xi)) = x. Pero siempre habrá un único x1 tal que g(f(x1)) = x y además x1 es más chico que todos los xi. Este x1 se encuentra con la minimización:<br />
<br />
min{y : f(y) = x}<br />
<br />
Por otra parte, esta minimización es computable, dado que está garantizado por la sobreyectividad de f la existencia de al menos un y que verifique f(y) = x. Nuevamente, esta función se computa con el programa del ejercicio 1, item A. Por último, g es inyectiva porque en la expresión f(y) = x, dos valores x1 y x2 distintos no pueden provenir del mismo y, dado que esto violaría la definición de función.<br />
<br />
== Ejercicio 3 ==<br />
<br />
Sea f: N -> N una función computable biyectiva. Probar que Halt(f(x), x) no es computable. Sugerencia: considerar la función:<br />
<br />
h(x) = 1 si fi(x, f^-1(x)) se cuelga<br />
se cuelga en otro caso<br />
<br />
El siguiente programa computa h, suponiendo que HALT(f(x),x) sea computable:<br />
<br />
[A] IF HALT(f(f^-1(x)), f^-1(x)) GOTO A<br />
Y <- 1<br />
<br />
que es equivalente a:<br />
<br />
[A] IF HALT(x, f^-1(x)) GOTO A<br />
Y <- 1<br />
<br />
Llamemos P a este programa, entonces existe e perteneciente a N tal que #(P) = e<br />
<br />
Ahora bien, por la definición de HALT:<br />
<br />
HALT(f(e), e) <=> P(f(e)) termina<br />
<br />
Y por el código de P:<br />
<br />
P(f(e)) termina <=> -(HALT(f(e), e)<br />
<br />
Lo que nos lleva a un absurdo, que proviene de la única suposición que hicimos, que es que HALT(f(x), x) es computable.<br />
<br />
== Ejercicio 4 ==<br />
<br />
Sean f, g y h las funciones dadas por:<br />
<br />
f(x) = fi(x,x) + 1 si fi(x,x) termina<br />
se cuelga si no<br />
<br />
g(x) = 1 si x pertenece al dominio de f<br />
se cuelga si no<br />
<br />
h(x) = 0 si fi(x,x) termina<br />
se cuelga si no<br />
<br />
Para resolver esto es suficiente con dar 3 programas que computen cada una de estas funciones.<br />
<br />
Este programa computa f:<br />
<br />
Y <- fi(x,x) + 1<br />
<br />
Este programa computa g:<br />
<br />
Z <- f(x)<br />
Y <- 1<br />
<br />
Y este computa h:<br />
<br />
Y <- not(g(x))<br />
<br />
<br />
== Ejercicio 5 ==<br />
<br />
Probar que la siguiente función es primitiva recursiva:<br />
<br />
f(x) = 1 si x = <<a,b>,c> y fi(b,a) termina en menos de c pasos<br />
0 en otro caso<br />
<br />
'''Solución'''<br />
<br />
f(x) es pr porque tanto los valores que devuelve como las funciones utilizadas en las guardas lo son. La decodificación de x en a, b y c es pr. y el predicado "fi(b,a) termina en menos de c pasos" es computado por el programa STP(b,a,c), que es pr.<br />
<br />
<br />
== Ejercicio 6 ==<br />
<br />
Decimos que una funcion parcialmente computable f es extensible si existe g computalbe tal que g(x) = f(x) para todo x en el dominio de f. Probar que existe una funcion f parcialmente computable que no es extensible.<br />
<br />
¿<math>f(x) = \Phi _x(x)</math>?<br />
<br />
Sea <math>g(x_1, \dots, x_n, y) = \begin{cases} min_t STP(x_1,\dots,x_n,y,t)\ si \ \Phi_y (x_1,\dots,x_n) \downarrow \\<br />
\uparrow \ sino \end{cases}</math><br />
<br />
Supongamos ahora <math>g</math> es extensible y sea <math>f</math> computable la función que la extiende. Pero entonces, podríamos reescribir la función <math>Halt</math> con <math>f</math><br />
<br />
<math>Halt(x_1,\dots,x_n,y) = STP(x_1,\dots,x_n,y,f(x_1,\dots,x_n,y))</math><br />
Lo cual es absurdo, ya que <math>Halt</math> no es computable y con esta definición es claramente computable. (la idea es que como <math>g</math> te devuelve en qué número de "iteración" <math>y</math> termina, no importa qué te devuelva la extensión <math>f</math> ya que podés chequear si es fruta o es uno de los valores de <math>g</math>, chequeando con <math>STP</math> si efectivamente <math>x</math> terminó en la cantidad de pasos que te dijo f)<br />
<br />
== Ejercicio 7 ==<br />
<br />
== Ejercicio 8 ==<br />
<br />
== Ejercicio 9 ==<br />
<br />
== Ejercicio 10 ==<br />
<br />
Probar que las siguientes funciones no son computables<br />
<br />
==== Item A ====<br />
<br />
f(x) = 1 si <math>\Phi _x(x) = 2x</math><br />
0 si no<br />
<br />
Supongo f es computable, por ende es total<br />
<br />
Sea g(x,y) tal que<br />
g(x,y) = 2x+1 si f(x)<br />
2x si no<br />
<br />
Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math><br />
<br />
Supongo <math>\Phi _e(e) = 2e</math><br />
<math>\Rightarrow f(e) \Rightarrow g(e,e) = \Phi _e(e) = 2e+1 \neq 2e</math><br />
<br />
Supongo <math>\Phi _e(e) \neq 2e</math><br />
<math>\Rightarrow \alpha(f(e)) \Rightarrow g(e,e) = \Phi _e(e) = 2e</math><br />
<br />
Absurdo que proviene de suponer que f es computable<br />
<br />
Todos los items siguientes se resuelven con el mismo mecanismo<br />
<br />
==== Item B ====<br />
<br />
f(x) = 1 si <math>dom(\Phi _x) = \emptyset</math><br />
0 si no<br />
<br />
Supongo f es computable<br />
<br />
Sea g(x,y) tal que<br />
g(x,y) = 1 si f(x)<br />
<math>\uparrow</math> si no<br />
<br />
Por teorema de la recursion, <math>\exists e / \Phi _e = g(e)</math><br />
<br />
Evaluando g en e se llega al absurdo<br />
<br />
==== Item C ====<br />
<br />
f(x,y) = 1 si <math>\Phi _x = \Phi _y</math><br />
0 si no<br />
<br />
Supongo f es computable, por ende tambien total<br />
<br />
Sea g(x,y) tal que<br />
g(x,y) = <math>\Phi _y + 1</math> si f(x,y)<br />
<math>\Phi _y</math> si no<br />
<br />
Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math><br />
<br />
Sea a tal que <math>\Phi _a\downarrow</math><br />
<br />
Por teorema del parametro, <math>\exists s / \Phi _s = g(e,a) = \Phi _e(a)</math><br />
<br />
Evaluando g en (s,a) se llega al absurdo<br />
<br />
==== Item D ====<br />
<br />
f(x) = 1 si <math>Im(\Phi _x)</math> es infinita<br />
0 si no<br />
<br />
Supongo f es computable, por ende tambien es total<br />
<br />
Sea g(x,y) tal que<br />
g(x,y) = 0 si f(x)<br />
y si no<br />
<br />
Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math><br />
<br />
Supongo <math>Im(\Phi _e) infinita</math>,<br />
<math>\Rightarrow f(e) \Rightarrow (\forall y) g(e,y) = \Phi _e(y) = 0 \Rightarrow Im(\Phi _e) = {0}</math><br />
<br />
Supongo <math>Im(\Phi _e) no infinita</math>,<br />
<math>\Rightarrow \alpha(f(e)) \Rightarrow (\forall y) g(e,y) = \Phi _e(y) = y \Rightarrow Im(\Phi _e) = Naturales</math><br />
<br />
==== Item E ====<br />
<br />
f(x) = 1 si <math>1 \in dom(\Phi _x)</math><br />
0 si no<br />
<br />
La condicion equivale a decir que <math>\Phi _x(1)\downarrow</math><br />
<br />
Supongo f es computable, por ende tambien es total<br />
<br />
Sea g(x,y) tal que<br />
g(x,y) = <math>\uparrow</math> si f(x)<br />
0 si no<br />
<br />
Por teorema de la recursion, <math>\exists e / \Phi _e(y) = g(e,y)</math><br />
<br />
Evaluando g en (e,y) para todo y, se llega al absurdo<br />
<br />
<br />
== Ejercicio 11 ==<br />
<br />
Analizar la validez de las siguientes afirmaciones<br />
<br />
==== Item A ====<br />
<br />
Si B es r.e., entonces B es computable o su complemento es computable.<br />
<br />
'''Solucion'''<br />
<br />
Falso.<br />
<br />
<math>B = \{ x : \Phi _x(x)\downarrow \} </math> <br/><br />
B es r.e., pero no es computable, ni tampoco su complemento. Si lo fueran, entonces el Halting problem seria computable.<br />
<br />
==== Item B ====<br />
<br />
Si <math>B_1,...,B_k</math> son r.e., entonces la union tambien lo es.<br />
<br />
'''Solucion'''<br />
<br />
Verdadero.<br />
<br />
Basta construir un programa que vaya evaluando en paralelo todas las posibilidades, hasta que alguno termine.<br />
<br />
==== Item C ====<br />
<br />
Idem anterior, pero si la cantidad de conjuntos es infinita.<br />
<br />
'''Solucion 1'''<br />
<br />
Verdadero.<br />
<br />
Se deberia poder construir un programa utilizando la tecnica de Dove Tailing que vimos en la teorica.<br/><br />
Es decir, para determinar si ''x'' pertenece, evaluo ''STP(b1, x, 1)''.<br/><br />
Si es falso, pruebo con ''STP(b1, x, 2)'' y ''STP(b2, x, 2)''.<br/><br />
Si dan falso, pruebo con ''STP(b1, x, 3)'', ''STP(b2, x, 3)'' y ''STP(b3, x, 3)''.<br/><br />
Asi sucesivamente hasta hallar un valor que verifique, o colgarse si no pertenece al conjunto.<br />
<br />
En forma recursiva, la funcion seria:<br />
<math>U(x) = (\exists t)(\exists y) STP(B_y, x, t)</math><br/><br />
Como la minimizacion es no acotada (ni tampoco propia), el programa es parcialmente computable y caracteriza un conjunto r.e.<br />
<br />
'''Solucion 2'''<br />
<br />
Falso.<br />
<br />
Si la proposición fuera verdadera, entonces cualquier conjunto de naturales sería r.e.:<br />
<br />
Sea <math>A</math> un conjunto de naturales cualquiera. Definimos la familia de conjuntos <math>B_i = \{ x: x\in A\land x < i \}</math>. Los <math>B_i</math> son todos finitos, por lo tanto son todos computables, por lo tanto son todos r.e. Además, es claro que <math>A = \cup_{i=1}^\infty B_i</math>. Por lo tanto, si la proposición fuera verdadera, <math>A</math> tendría que ser r.e.<br />
<br />
Pero sabemos que existen conjuntos de naturales que no son r.e. (por ejemplo el complemento de <math>K</math>). Por lo tanto, la proposición debe ser falsa.<br />
<br />
<br />
==== Item D ====<br />
<br />
Encontrar el error en alguna de las soluciones del item C.<br />
<br />
== Ejercicio 12 ==<br />
<br />
Sea B un conjunto infinito<br />
<br />
==== Item A ====<br />
<br />
Probar que B es r.e. sii existe una funcion f inyectiva computable tal que la imagen de f sea B.<br />
<br />
'''Solucion'''<br />
<br />
<math>\Rightarrow</math>)<br />
<br />
Como B es r.e., existe una funcion g primitiva recursiva (por lo tanto, computable) tal que su imagen sea B. Defino f en funcion de g:<br />
<br />
<math>f(0) = g(0)</math> <br/><br />
<math>f(n+1) = g(min_t((\forall i \leq n) g(t) \neq f(i))</math><br />
<br />
Intuitivamente, f va seleccionando todos los valores de g tal que no se hayan repetido anteriormente. Como B es infinito, siempre existira algun nuevo valor t que no sea repetido. Por lo tanto, la minimizacion es propia y f resulta computable e inyectiva, pues no repite valores; y su imagen es igual a B.<br />
<br />
<math>\Leftarrow</math>)<br />
<br />
<br>Existe una funcion f inyectiva computable tal que su imagen es igual a B, por lo tanto, B es r.e.<br />
<br>Se puede usar la funcion del 1.a para probarlo.<br />
<br />
==== Item B ====<br />
<br />
Probar que B es computable sii existe una funcion f de una variable computable y creciente tal que Im f = B.<br />
<br />
'''Solucion'''<br />
<br />
<math>\Rightarrow</math>)<br />
<br />
B = {x : B(x)} = {f(0), f(1), ... }<br />
<br />
<math>f(0) = min_t (B(t))</math> <br/><br />
<math>f(n+1) = min_t (f(n) < t \wedge B(t))</math><br />
<br />
La idea de f es que va probando con todos los numeros naturales y para cada uno de ellos chequea si B(i) es verdadero o no. Si lo es, entonces lo devuelve como valor de la funcion, si no, sigue probando.<br />
<br />
<math>\Leftarrow</math>)<br />
<br />
B es computable sii su funcion caracteristica B(x) lo es. <br/><br />
<math>B(x) = (\exists t \leq x) f(t) = x</math><br />
<br />
Como f es computable, entonces B lo es.<br />
<br />
== Ejercicio 13 ==<br />
<br />
Probar que todo conjunto re infinito contiene un subconjunto computable infinito.<br />
<br />
'''Solucion'''<br />
<br />
Sea f p.r. tal que la imagen de f sea igual al conjunto B (r.e. e infinito).<br />
<br />
Defino la funcion g tal que:<br />
g(0) = f(0)<br />
g(n+1) = f(min(t) (f(t) > g(n)))<br />
<br />
Intuitivamente, la funcion g selecciona los valores que estan en orden creciente en la imagen de f. Como B es infinito, para cualquier indice elegido siempre existira otro mayor tal que la funcion resulte creciente. Por lo tanto, la minimizacion es propia y la funcion g resulta computable ademas de creciente.<br />
<br />
Como g es computable y creciente, entonces su imagen define un conjunto, contenido en B, que es computable e infinito (vale por ej 12).<br />
<br />
== Ejercicio 14 ==<br />
<br />
Probar que si B es re y f es una funcion parcialmente computable, entonces <math>A = {x : f(x) \in B}</math> es re.<br />
<br />
<br />
Como B es re, existe g parcialmente computable tal que <br />
<math>B = {x : g(x)\downarrow}</math><br />
<br />
Para que A sea re, tiene que existir una funcion h parcialmente computable tal que <math>A = {x : h(x)\downarrow}</math>.<br />
<br />
Sea h = g(f(x)), parcialmente computable por ser composicion de pc. <br />
<math>g(f(x)) = f(x) \in B</math><br />
<br />
Entonces A es re.<br />
<br />
== Ejercicio 15 ==<br />
<br />
== Ejercicio 16 ==<br />
<br />
<br> =>) Sea A = We = {x: Φx↓} => x є A si existe un tiempo t tal que Φe(x)↓, entonces<br />
<br> A = {x: (<math>\exists</math> t) STP<sup>(1)</sup>(x,e,t)}, y se sabe que STP es un predicado PR<br />
<br />
<br> <=) Sea el predicado PR J(x) = (<math>\exists</math> y) P(x,y), y el siguiente programa P:<br />
<pre><br />
[A] IF J(Z)=1 GOTO F<br />
Z++<br />
GOTO A<br />
[F] Y <- 1<br />
</pre><br />
Como puede verse, P computa la funcion parcialmente computable<br />
<pre><br />
f(x) = {1 si J(x)=1<br />
{↑ sino<br />
</pre><br />
Con lo cual B = dom f => B es RE<br />
<br />
== Ejercicio 17 ==<br />
<br />
Definir un predicado pr P tal que <math>A = {x : (\forall y)P(x,y)}</math> no sea re.<br />
<br />
Sea <math>P(x,y) := STP(x,x,y)=0</math><br />
Como STP es p.r., <math>P(x,y)</math> es claramente p.r. también<br />
Notemos ahora que <math>B=\{x: (\forall y) STP(x,x,y)=0\}</math> es lo mismo que <br />
<math>B=\{x | \Phi_x (x)\uparrow\}</math> , o sea, es el complemento del famoso conjunto <math>K</math> (x tal que Halt(x,x)), que ya sabíamos que no es r.e. porque lo probamos en la teórica/práctica.<br />
<br />
== Ejercicio 18 ==<br />
<br />
Sea <math>B=\{ x \ : \ \Phi_x \ es\ una\ funcion\ total\}</math><br />
<br />
a. Probar que B no es r.e.<br />
<br />
b. Probar que <math>N - B</math> no es r.e.<br />
<br />
====Item A====<br />
<br />
Este lo hicimos en clase.<br />
<br />
====Item B====<br />
<br />
Lo que nos piden probar es que el complemento de B no es r.e. O sea, que el conjunto <math>A=\{ x \ : \ \Phi_x \ es\ una\ funcion\ parcial\}</math> no es r.e. Supongamos entonces lo contrario. Esta suposición implica que la pertenencia a B es parcialmente computable (devuelve 1 si es true, se cuelga sino).<br />
<br />
Definamos entonces:<br />
<br />
<math>f(x,y) = \begin{cases} 1\ si\ x \in A \\ \uparrow\ sino \end{cases}</math><br />
Por el teorema de la recursión, existe un e tal que:<br />
<math>\Phi_e(y) = f(e,y)</math>, pero entonces:<br />
<br />
Si <math>e \in A \rightarrow \Phi_e(y)=1 \rightarrow e\ es\ total</math> (Absurdo porque partimos de que e era parcial y por eso estaba en A)<br />
<br />
Si <math>e \notin A \rightarrow \Phi_e(y)\uparrow \rightarrow e\ es\ parcial</math> (Absurdo porque partimos de que e era total y por eso no estaba en A).<br />
<br />
Pero entonces superabsurdo, que partió de suponer que A era un conjunto r.e.<br />
<br />
==Ejercicio 19==<br />
Probar que existe un <math>e</math> tal que <math>W_e=\{e\}</math>.<br />
<br />
<br />
Tal e existe,por definición de <math>W_e</math>, si y sólo si existe un <math>e</math> tal que <math>\{e\}=\{x \in N\ |\ \Phi_e(x)\downarrow\}</math>.<br />
<br />
[... EN CONSTRUCCIÓN ...]<br />
<br><br><br />
''Posible resolucion'' '''(Sin verificar)'''<br />
<br><br><br />
<math>f(x,y) = \begin{cases} 1\ si\ y = x \\ \uparrow\ sino \end{cases}</math><br />
Por el teorema de la recursión, existe un e tal que:<br />
<math>\Phi_e(y) = f(e,y)</math>, pero entonces:<br />
<br />
<math>\Phi_e(y)</math> estará definida solo si y=e, es decir, el dominio de <math>\Phi_e(y)</math> será e, eso significa que <math>W_e=\{e\}</math> que era lo que queriamos probar.<br />
<br />
== Ejercicio 20 ==<br />
<br />
Demostrar que las funciones definidas en el Ejercicio 10 no son computables aplicando el Teorema de Rice<br />
<br />
==== Item C ====<br />
<br />
f(x,y) = 1 si <math>\Phi _x = \Phi _y</math><br />
0 si no<br />
<br />
A = {x: <math>\Phi _x = \Phi _0</math>}<br />
<br />
Quiero ver que A no es computable por Rice. Para esto tengo que probar que:<br />
<br />
1. <math>A \neq \emptyset</math><br />
<br />
A representa el conjunto de los programas que computan el programa 0 (aquel que devuelve 0 para toda entrada).<br />
<br />
Ejemplo: <br />
el programa que computa f(x,y) donde<br />
<br />
f(x,y) = (x>y).(y-x)+(x<=y).(x-y)<br />
<br />
claramente, esta función hace lo mismo que #P=0<br />
donde P es el programa que computa a <br />
<br />
n(x) = 0<br />
<br />
Entonces, <math>A \neq \emptyset</math><br />
<br />
2. <math>A \neq N</math><br />
<br />
Ejemplo: <br />
el programa que computa la función constante <br />
<br />
g(x) = 8<br />
<br />
Además, puede verse que hay programas que no están en A<br />
<br />
Entonces, <math>A \neq N</math><br />
<br />
3. A es un conjunto de índices<br />
<br />
Se dice que A es un conjunto de índices si dado C una clase de funciones parcialmente computables A es el conjunto de los programas que computan a dichas funciones. <br />
En este caso, A es el conjunto de los programas que computan lo mismo que <math>\Phi _0</math> (la función nula). <br />
Entonces dado x perteneciente a A y <math>\Phi _x = \Phi _y</math> --> y pertenece a A.<br />
<br />
Muy bien, ahora, por Rice, A no es computable<br />
<br />
Supongo f computable. Entonces f(x,0) es computable. <br />
Pero f(x,0) = g(x) es la función característica de A. Absurdo, porque A no es computable --> f no es computable :)<br />
<br />
El resto sale de la misma forma :)<br />
<br />
[[Category:Lógica y Computabilidad]]</div>157.92.4.151https://www.cubawiki.com.ar/index.php?title=Pr%C3%A1ctica_10:_Matching_-_Flujo_M%C3%A1ximo_(Algoritmos_III)&diff=1682Práctica 10: Matching - Flujo Máximo (Algoritmos III)2006-12-01T18:14:15Z<p>157.92.4.151: /* Ejercicio 10.02: */</p>
<hr />
<div>==Propiedades==<br />
(Para todo G: grafo) <br />
<br />
* (DEF) Una '''correspondencia o matching''' entre los vertices de G es un conjunto M de ejes tq <math>\forall</math> v en V, v incide hasta en un eje de M <i>(no hay dos ejes de M que toquen un mismo vertice)</i><br />
* (DEF) Un '''conjunto independiente''' I de vertices de G es un conjunto I de vertices tq <math>\forall</math> e en E, e incide hasta en un vertice v de I <i>(no hay vertices de I adyacentes entre si)</i><br />
* (DEF) Un '''recubrimiento de los ejes''' de G es un conjunto Re de vertices tq <math>\forall</math> e en E, e incide al menos en un nodo v de Re <i>(los vertices de Re "cubren" todos los ejes de G)</i><br />
* (DEF) Un '''recubrimiento de los vertices''' de G es un conjunto Rn de ejes tq <math>\forall</math> v en V, v incide al menos en un eje e de Rn <i>(los ejes de Rn "cubren" todos los vertices de G)</i><br />
* (DEF) Un vertice v se dice '''saturado por un matching M''' si hay un eje de M incidente a v<br />
* (DEF) Dado un matching M en G, un '''camino alternado''' en G es un camino simple donde se alternan ejes que estan en M con ejes que no estan en M<br />
* (TEO) Sean M0 y M1 dos matching en G y sea G´ tq E´= (M0 - M1)<math>\cup</math>(M1 - M0) -> las componentes conexas de de G´son de alguno de los siguientes tipos:<br />
**i) nodo aislado<br />
**ii) circuito simple con ejes alternadamente en M0 y M1<br />
**iii) camino simple con ejes alternadamente en M0 y M1<br />
* (DEF) M es un '''matching maximo''' <=> no existe un camino alternado entre pares de nodos no saturados<br />
* (TEO) Si M es un matching máximo y Rn un recubrimiento mínimo de los vertices de G -> |M|+|Rn|=n<br />
* (TEO) Si S es un conjunto independiente maximo y Re un recubrimiento mínimo de los ejes de G -> |I|+|Re|=n<br />
<br />
* (DEF) Una '''red''' N es un grafo orientado conexo que tiene dos nodos distinguidos una fuente s con grado de salida positivo y un sumidero t con grado de entrada positivo.<br />
* (DEF) Una '''función de capacidades''' en la red es una función c(e)>=0 definida para todo e en EN<br />
* (DEF) Un '''flujo factible''' en una red N con capacidades, es una función f: EN->R+ que verifica:<br />
**i) 0<=f(e)<=c(e) <math>\forall</math> e en EN.<br />
**ii) Σ{e en In(v)} f(e) = Σ{e en Out(v)} f(e) <math>\forall</math> v (salvo s y t), donde<br />
***In(v)={e en EN, e=w->v con w otro vertice de N} <br />
***Out(v)={e en EN, e=v->w con w otro vertice de N}<br />
*(DEF) Un '''corte''' en la red N es un subconjunto S(V tq s en S y t no en S<br />
*(DEF) SS'={ejes que tienen la cola en S y la cabeza en S'} y S'S={ejes que tienen la cola en S' y la cabeza en S} donde S'=V\S<br />
* (TEO) Sea f un flujo definido en una red N y sea S un corte -> F= Σ{e en SS'} f(e)-Σ{e en S'S} f(e)<br />
* (DEF) La '''capacidad de un corte''' S se define como c(S)=Σ{e en SS'} c(e)<br />
* (TEO) Si f es una función de flujo con valor F y S es un corte en N, entonces F<=c(S).<br />
* (COR) Certificado de optimalidad: Si F es el valor de un flujo y S un corte en N tal que F=c(S) entonces F es un flujo máximo y S es un corte de capacidad mínima<br />
* (DEF) Un '''camino de aumento''' en N es un camino P entre s y t tal que el flujo en un eje “hacia delante” puede crecer y en un eje “hacia atrás”puede decrecer, o sea para todo eje e de P se verifica que f(e)<c(e) si e es “hacia delante”o f(e)>0 si e es “hacia atrás”<br />
* (TEO) Si los valores del flujo inicial y las capacidades de los ejes son enteras -> el método de Ford y Fulkerson termina en un número finito de pasos y determina un flujo máximo en N<br />
* (COR) El valor del flujo máximo en una red N es igual a la capacidad de un corte mínimo<br />
* (TEO) Sea N una red tal que dout(s)>din(s), din(t)>dout(t) y tal que dout(v)=din(v) <math>\forall</math> v distinto de s y t -> hay un camino orientado simple entre s y t en N<br />
* (TEO) Sea N una red tal que dout(s)-din(s)=dint(t)-dout(t)=p y tal que dout(v)=din(v) <math>\forall</math> v distinto de s y t -> existe un conjunto de p caminos simples orientados disjuntos en los ejes entre s y t<br />
* (TEO) Sea N una red con fuente s y sumidero t, tal que c(e)=1 para todo eje e -> el valor F* de un flujo máximo en N es igual al número de caminos simples disjuntos en los ejes entre s y t<br />
<br />
* (DEF) Un conjunto de ejes '''"s-t separador"''' en un digrafo G es un conjunto de ejes, tal que si se los saca de G, no quedan caminos orientados entre s y t en el grafo resultante<br />
* (TEO) Sea N una red tal que c(e)=1 para todo eje e. La capacidad de un corte mínimo en N es igual al cardinal de un conjunto de ejes “s-t separador” mínimo en N<br />
* (TEO) (Menger) Sean s y t dos nodos distintos en un grafo orientado D. Entonces el máximo número de caminos orientados disjuntos entre s y t en D es igual al cardinal de un conjunto de ejes “s-t separador” mínimo en D<br />
* (TEO) (Hall) Si G es un grafo bipartito con partición (V1, V2) -> G tiene un matching que satura a V1 <=> <math>\forall</math> W<math>\subset</math>V1 |W|<=|Г(W)|, donde Г(W) es el conjunto de vertices vecinos a W<br />
<br />
<table bgcolor="blue"><tr><td><font color="white"> Matching </font></td></tr></table><br />
<br />
==Ejercicio 10.01:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
<br />
==Ejercicio 10.02:==<br />
<br>a) F (Un grafo sin ejes no tiene)<br />
<br>b) F (Idem a)<br />
<br>c) V (En todo grafo, un solo vertice es conj. indep)<br />
<br>d) V (En todo grafo, todos los vertices forman un recub. de ejes)<br />
<br>e) V El matching maximo en peor caso tiene n/2 ejes (seria uno con todos los pares de vertices, salvo n impar, entonces queda uno aislado), que a su vez es el minimo de ejes de un recub. de vertices, por la misma razon -> |M| <= |Rv|<br />
<br>f) V El conjunto indep. maximo en peor tiene tiene n vertices, entonces cada uno estaria en un clique distinto, y entonces el recub. de ejes tiene como minimo n vertices en total -> |I| <= |Re|<br />
<br>g) F, por ejemplo uno.<br />
<br />
==Ejercicio 10.03:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)Si un recub. de vertices contiene ciclos -> hay vertices cubiertos por mas de 1 eje -> no es minimal -> ABS. Si un recub. de ejes contiene ciclos -> hay ejes cubiertos por mas de 1 vertices -> no es minimal -> ABS<br />
<br>e)<br />
<br>f)<br />
<br />
==Ejercicio 10.04:==<br />
Si G tiene un conjunto independiente de n nodos, entonces cada uno esta en un clique distinto, y el cubrimiento minimo tiene por lo menos n cliques -> |I|<=|Rn|<br />
<br />
==Ejercicio 10.05:==<br />
Probar que si G es bipartito, m <= <math>\alpha * \beta </math>, donde <math>\alpha</math>=#(conj. indep. maximo) y <math>\beta</math>=#(Recubrimiento minimo de aristas)<br />
<br />
<br>Sea: <math>v \in \real</math>, y V1,V2 las particiones de G<br />
<br><math>m \leq 2*m = \sum d(v) \leq max(|V1|,|V2|)* \beta \leq \alpha * \beta </math><br />
<br />
Fin :P<br />
<br />
<br />
<br />
<br />
Posted by Alejandro<br />
<br />
==Ejercicio 10.06:==<br />
==Ejercicio 10.07:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
==Ejercicio 10.08:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
==Ejercicio 10.09:==<br />
<br>a)<br />
<br>b)<br />
<br />
<table bgcolor="blue"><tr><td><font color="white"> Flujo Maximo </font></td></tr></table><br />
<br />
==Ejercicio 10.10:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 10.11:==<br />
==Ejercicio 10.12:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 10.13:==<br />
Usando BFS en el algoritmo de camino de aumento para marcar nodos y ejes queda O(n*m^2), ya que.. (completar)<br />
<br />
==Ejercicio 10.14:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 10.15:==<br />
<br />
<br />
Asignar f(e)<math>\forall e \in ciclo dirigido</math><br />
<br> Crear un camino de S a T y luego incrementar todos los ejes <br />
<br />
<br><math>\forall </math> e tal que f(e)=0<br />
<br> Si hay camino de S a T tal que: <br />
<br>incluya a e, aumentar el flujo del camino en 1.<br />
<br>OW= No hay flujo factible.<br />
<br />
<br />
<br>Buscar caminos de disminucion:<br />
<br>Si e1,e2,ei... es un camino de S a T.<br />
<br>Tal que f(ei) > c(ei)<math> \forall i \Longrightarrow </math> es camino de disminucion.<br />
<br>... Y podemos disminuir el flujo del camino en min(f(ei)-c(ei))<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
Posted By Alejandro<br />
<br />
==Ejercicio 10.16:==<br />
==Ejercicio 10.17:==<br />
==Ejercicio 10.18:==<br />
==Ejercicio 10.19:==<br />
==Ejercicio 10.20:==<br />
==Ejercicio 10.21:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 10.22:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 10.23:==<br />
==Ejercicio 10.24:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 10.25:==<br />
<b>HECHO EN CLASE, ALGUIEN QUE LO TENGA SUBALO</b><br />
<br>a)<br />
<br>b)<br />
<br />
==Ejercicio 10.26:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
<br>e)<br />
<br>f)<br />
==Ejercicio 10.27:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 10.28:==</div>157.92.4.151https://www.cubawiki.com.ar/index.php?title=Pr%C3%A1ctica_9:_Planaridad_-_Coloreo_(Algoritmos_III)&diff=1527Práctica 9: Planaridad - Coloreo (Algoritmos III)2006-11-17T20:03:45Z<p>157.92.4.151: /* Ejercicio 09.02: */</p>
<hr />
<div>==Ejercicio 09.01:==<br />
==Ejercicio 09.02:==<br />
<br />
Si G es planar <math> \Rightarrow </math> <font color="red"> m <math> \le </math> 3n-6 </font><br />
<br />
Si T es arbol <math> \Rightarrow </math> m = n-1<br />
<br />
Hay que ver si n-1 <math> \le </math> 3n-6 <p><br />
n-1 <math> \le </math> 3n-6 <math> \Leftrightarrow </math> 5 <math> \le </math> 2n </p><p> <br />
Esto vale para n <math> > </math> 2 . (Para n=1, n=2 son casos triviales)<br />
</p><br />
<br />
==Ejercicio 09.03:==<br />
==Ejercicio 09.04:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.05:==<br />
==Ejercicio 09.06:==<br />
==Ejercicio 09.07:==<br />
==Ejercicio 09.08:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.09:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
==Ejercicio 09.10:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.11:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.12:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.13:==<br />
==Ejercicio 09.14:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.15:==<br />
==Ejercicio 09.16:==<br />
==Ejercicio 09.17:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
==Ejercicio 09.18:==<br />
==Ejercicio 09.19:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.20:==<br />
==Ejercicio 09.21:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.22:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.23:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.24:==<br />
==Ejercicio 09.25:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.26:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.27:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
<br>e)<br />
<br>f)<br />
==Ejercicio 09.28:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
==Ejercicio 09.29:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
<br>e)<br />
==Ejercicio 09.30:==<br />
==Ejercicio 09.31:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.32:==<br />
==Ejercicio 09.33:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.34:==<br />
==Ejercicio 09.35:==</div>157.92.4.151https://www.cubawiki.com.ar/index.php?title=Pr%C3%A1ctica_9:_Planaridad_-_Coloreo_(Algoritmos_III)&diff=1526Práctica 9: Planaridad - Coloreo (Algoritmos III)2006-11-17T19:43:12Z<p>157.92.4.151: /* Ejercicio 09.02: */</p>
<hr />
<div>==Ejercicio 09.01:==<br />
==Ejercicio 09.02:==<br />
<br />
Si G es planar => m <= 3n-6<br />
<br />
Si T es arbol => m = n-1<br />
<br />
Hay que ver si n-1 <= 3n-6 <br />
<br />
n-1 <= 3n-6 <=> 5 <= 2n <br />
<br />
Esto vale para n > 2 . (Para n=1, n=2 son casos triviales)<br />
<br />
==Ejercicio 09.03:==<br />
==Ejercicio 09.04:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.05:==<br />
==Ejercicio 09.06:==<br />
==Ejercicio 09.07:==<br />
==Ejercicio 09.08:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.09:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
==Ejercicio 09.10:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.11:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.12:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.13:==<br />
==Ejercicio 09.14:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.15:==<br />
==Ejercicio 09.16:==<br />
==Ejercicio 09.17:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
==Ejercicio 09.18:==<br />
==Ejercicio 09.19:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.20:==<br />
==Ejercicio 09.21:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.22:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.23:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.24:==<br />
==Ejercicio 09.25:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.26:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 09.27:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
<br>e)<br />
<br>f)<br />
==Ejercicio 09.28:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
==Ejercicio 09.29:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
<br>e)<br />
==Ejercicio 09.30:==<br />
==Ejercicio 09.31:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.32:==<br />
==Ejercicio 09.33:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 09.34:==<br />
==Ejercicio 09.35:==</div>157.92.4.151https://www.cubawiki.com.ar/index.php?title=Pr%C3%A1ctica_8:_Caminos_Eulerianos_y_Hamiltonianos_(Algoritmos_III)&diff=1456Práctica 8: Caminos Eulerianos y Hamiltonianos (Algoritmos III)2006-11-13T20:20:12Z<p>157.92.4.151: /* Ejercicio 08.08: */</p>
<hr />
<div>==Ejercicio 08.01:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 08.02:==<br />
==Ejercicio 08.03:==<br />
==Ejercicio 08.04:==<br />
==Ejercicio 08.05:==<br />
==Ejercicio 08.06:==<br />
==Ejercicio 08.07:==<br />
<br>a)<br />
<br>b)<br />
==Ejercicio 08.08:==<br />
<br>a) Para todo n impar, n >1<br />
<br>b) K2<br />
<br />
==Ejercicio 08.09:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 08.10:==<br />
==Ejercicio 08.11:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
<br>e)<br />
==Ejercicio 08.12:==<br />
==Ejercicio 08.13:==<br />
==Ejercicio 08.14:==<br />
==Ejercicio 08.15:==<br />
==Ejercicio 08.16:==<br />
==Ejercicio 08.17:==<br />
==Ejercicio 08.18:==<br />
==Ejercicio 08.19:==<br />
==Ejercicio 08.20:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
==Ejercicio 08.21:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
<br>d)<br />
<br>e)<br />
==Ejercicio 08.22:==<br />
==Ejercicio 08.23:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 08.24:==<br />
<br>a)<br />
<br>b)<br />
<br>c)<br />
==Ejercicio 08.25:==</div>157.92.4.151https://www.cubawiki.com.ar/index.php?title=Categor%C3%ADa:Organizaci%C3%B3n_del_Computador_II&diff=2074Categoría:Organización del Computador II2006-10-26T22:47:08Z<p>157.92.4.151: /* IA-64 (Itanium) */</p>
<hr />
<div>'''Organización del Computador II''' es una materia dedicada al estudio de las arquitecturas [[Organización del Computador II#IA-32|IA-32]] e [[Organización del Computador II#IA-64 (Itanium)|IA-64]] de Intel. Pertenece al área de [[Sistemas (Area)|Sistemas]] y, según el [[Plan de la Carrera]], es una materia a ser cursada en [[Plan de la Carrera#Segundo año|Segundo año]]. Es correlativa de [[Organización del Computador I]], y es requerida para cursar [[Sistemas Operativos]].<br />
<br />
Históricamente, esta materia se cursa los Martes y Jueves a la noche.<br />
<br />
== Contenidos ==<br />
Nadie lo sabe bien.<br />
<br />
== Apuntes ==<br />
*[[Orga2 - Apuntes primer parcial 03/10/2006| Apuntes primer parcial 03/10/2006]]: Clase del 03/10/2006 de Emilio Platzer con tips para el primer parcial.<br />
<br />
== IA-32 ==<br />
*[[Orga2 - Ejercicios varios IA-32| Ejercicios varios IA-32]]: Codigo assembler de funciones varias realizadas en el laboratorio.<br />
*[[Orga2 - Practica Strings| Practica de Strings]]: Ejercicios de la practica de strings.<br />
*[[Orga2 - Practica Vectores y Matrices| Practica de Vectores y Matrices]]: Ejercicios de la practica de vectores y matrices.<br />
*[[Orga2 - Practica de Aritmetica| Practica de Aritmetica]]: Ejercicios de la practica de aritmetica y relacionados.<br />
<br />
== IA-64 (Itanium) ==<br />
*[[Orga2 - Itanium for Dummies| Itanium for Dummies]]: También conocido como ''"No se nada de Itanium, ¿Cómo empiezo?"''<br />
*[[Orga2 - Ejercicios varios Itanium| Ejercicios varios Itanium]]: Codigo assembler de funciones varias realizadas en el laboratorio de Itanium. Incluye sumador y Fibonacci version iterativa y recursiva.<br />
*[[Orga2 - Rotacion de Registros y Software Pipelining| Rotacion de Registros y Software Pipelining]]: Apuntes de clase sobre Rotación de registros con ejercicio de ejemplo, próximamente también Software Pipelining.<br />
*[[Orga2 - SIMD| SIMD]]: Apuntes de clase del 26/10/2006 sobre el set de instrucciones SIMD de Itanium.<br />
<br />
== Enlaces externos ==<br />
*[http://www.dc.uba.ar/people/materias/oc2 Página oficial de la materia]<br />
*[http://www.drpaulcarter.com/pcasm/pcasm-book-pdf.zip PC Assembly Language]<br />
*[http://webster.cs.ucr.edu/AoA/Linux/aoapdf.tar.gz Art of Assembly]<br />
*[http://www.jegerlehner.com/intel/IntelCodeTable_es.pdf Tabla de códigos x86]<br />
<br />
<br />
[[Category:Materias]]<br />
[[Category:Computación]]</div>157.92.4.151https://www.cubawiki.com.ar/index.php?title=Organizaci%C3%B3n_del_Computador_II&diff=268Organización del Computador II2006-10-26T22:47:08Z<p>157.92.4.151: /* IA-64 (Itanium) */</p>
<hr />
<div>'''Organización del Computador II''' es una materia dedicada al estudio de las arquitecturas [[Organización del Computador II#IA-32|IA-32]] e [[Organización del Computador II#IA-64 (Itanium)|IA-64]] de Intel. Pertenece al área de [[Sistemas (Area)|Sistemas]] y, según el [[Plan de la Carrera]], es una materia a ser cursada en [[Plan de la Carrera#Segundo año|Segundo año]]. Es correlativa de [[Organización del Computador I]], y es requerida para cursar [[Sistemas Operativos]].<br />
<br />
Históricamente, esta materia se cursa los Martes y Jueves a la noche.<br />
<br />
== Contenidos ==<br />
Nadie lo sabe bien.<br />
<br />
== Apuntes ==<br />
*[[Orga2 - Apuntes primer parcial 03/10/2006| Apuntes primer parcial 03/10/2006]]: Clase del 03/10/2006 de Emilio Platzer con tips para el primer parcial.<br />
<br />
== IA-32 ==<br />
*[[Orga2 - Ejercicios varios IA-32| Ejercicios varios IA-32]]: Codigo assembler de funciones varias realizadas en el laboratorio.<br />
*[[Orga2 - Practica Strings| Practica de Strings]]: Ejercicios de la practica de strings.<br />
*[[Orga2 - Practica Vectores y Matrices| Practica de Vectores y Matrices]]: Ejercicios de la practica de vectores y matrices.<br />
*[[Orga2 - Practica de Aritmetica| Practica de Aritmetica]]: Ejercicios de la practica de aritmetica y relacionados.<br />
<br />
== IA-64 (Itanium) ==<br />
*[[Orga2 - Itanium for Dummies| Itanium for Dummies]]: También conocido como ''"No se nada de Itanium, ¿Cómo empiezo?"''<br />
*[[Orga2 - Ejercicios varios Itanium| Ejercicios varios Itanium]]: Codigo assembler de funciones varias realizadas en el laboratorio de Itanium. Incluye sumador y Fibonacci version iterativa y recursiva.<br />
*[[Orga2 - Rotacion de Registros y Software Pipelining| Rotacion de Registros y Software Pipelining]]: Apuntes de clase sobre Rotación de registros con ejercicio de ejemplo, próximamente también Software Pipelining.<br />
*[[Orga2 - SIMD| SIMD]]: Apuntes de clase del 26/10/2006 sobre el set de instrucciones SIMD de Itanium.<br />
<br />
== Enlaces externos ==<br />
*[http://www.dc.uba.ar/people/materias/oc2 Página oficial de la materia]<br />
*[http://www.drpaulcarter.com/pcasm/pcasm-book-pdf.zip PC Assembly Language]<br />
*[http://webster.cs.ucr.edu/AoA/Linux/aoapdf.tar.gz Art of Assembly]<br />
*[http://www.jegerlehner.com/intel/IntelCodeTable_es.pdf Tabla de códigos x86]<br />
<br />
<br />
[[Category:Materias]]<br />
[[Category:Computación]]</div>157.92.4.151https://www.cubawiki.com.ar/index.php?title=Apuntes_primer_parcial_03/10/2006_(Organizaci%C3%B3n_del_Computador_II)&diff=321Apuntes primer parcial 03/10/2006 (Organización del Computador II)2006-10-04T00:34:20Z<p>157.92.4.151: /* Strings */</p>
<hr />
<div>== Strings ==<br />
<br />
Averigue el puntero/longitud a la meseta mas larga<br />
Meseta es repeticion de letras iguales<br />
<br />
Se anidan dos ciclos/funciones/macros. <br />
<br />
Macro interna longMeseta:<br />
<br />
Dado esi (en strings, puntero al src, en gral), devuelve la longitud de la meseta q empieza en esi.<br />
Requiere: esi al comienzo de la meseta<br />
bit de direcciones en avanzar<br />
Asegura: esi en el caracter siguiente a la meseta<br />
ecx tiene la longitud del resto de la cadena<br />
ebx es la longitud de la meseta<br />
<br />
Se puede hacer mediante la instruccion scas. Se usa un lodsb para levantar el 1er byte de la meseta, el scas para iterar, y un repe para iterar mientras sea igual. La longitud de la meseta es la diferencia entre el esi del final y el esi del ppio. <br />
<br />
Se debe llamar a longMeseta para recorrer toda la cadena, en un ciclo externo.<br />
<br />
while ecx>0<br />
longMeseta<br />
ebx<- max(ebx, max_actual)<br />
<br />
== Instruccion LEA ==<br />
<br />
lea reg, [reg1 + reg2*t + k]<br />
<br />
Tiene el mismo formato que un modo de direccionamiento<br />
Donde t es 1,2,4,8; k es un inmediato de 32 bits; y los registros son de 32 bits<br />
<br />
== Pila ==<br />
<br />
El push decrementa<br />
El pop incrementa<br />
<br />
== Numeros grandes ==<br />
<br />
Para laburar con enteros grandes, se pueden hacer suposiciones sobre el tamaño maximo de los mismos. No hay que validar de mas en assembler, la idea es funciones rapidas.<br />
<br />
<br />
==== Multiplicacion de numeros grandes por potencias chicas de 2 ====<br />
<br />
Sea el numero 08 00 CA FE<br />
Lo consideramos "grande" para este ejercicio<br />
<br />
Lo queremos multiplicar por 2<br />
En el primer byte uso un SHL/SAL 1<br />
En los siguientes, RCL, rotate left circular<br />
<br />
El shift saca el bit mas significativo y lo mete en el CF<br />
El RCL hace un shift, mete el CF en el menos significativo, y pisa el CF con el mas significativo q saco afuera<br />
El ROL pasa directamente del mas significativo al menos, y copia el mas significativo al CF<br />
<br />
El SHR mete un cero en el mas significativo, y el SAL repite el 7mo bit.<br />
Tiran el bit menos significativo que sacaron en el CF.<br />
Para dividir hay que ir del dword mas significativo al menos.<br />
<br />
Para multiplicar por 4, no conviene correr 2 veces el algoritmo anterior por los accesos a memoria<br />
Como se necesitarian 2 carry flag, se puede ir tirando los bits del carry a otro registro, haciendo RCL del reg que tiene el numero para cargar el carry, despues otro RCL contra el reg adicional para guardar ahi el carry, y asi sucesivamente. Antes de seguir a la proxima dword, se shiftea lo necesario para pasar los bits guardados de la parte mas alta a la mas baja.<br />
Otra posibilidad es guardar los bits mas significativos con operaciones logicas: copiar el registro y hacer un and con una mascara que deje solo los mas altos que se quieran guardar.<br />
<br />
<br />
==== Multiplicar numeros grandes con signo ====<br />
<br />
Para multiplicar numeros grandes, primero pasar los dos a positivo y despues multiplicar, y ver cual deberia ser el signo del resultado.<br />
<br />
Para cambiar de signo, empiezo por el menos significativo y voy negando y sumando uno (el carry despues de la 1er dword). La negacion se puede hacerla en los registros, no negarlo en memoria. Hay que guardar el carry en ese caso para saber que sumar.<br />
<br />
<br />
==== Multiplicar un numero grande por un registro de 32bit ====<br />
<br />
Se tiene un numero grande en memoria, en esi el puntero. En ebx el numero por el que se quiere multiplicar. Cargo la parte baja en eax, multiplico por ebx y queda el resultado en edx:eax. En la 1er iteracion, se puede bajar eax directamente. La parte alta, edx, es necesario guardarla (x ej en ecx). <br />
<br />
mov eax, [esi]<br />
mul ebx<br />
mov [edi], eax<br />
mov ecx, edx<br />
<br />
Luego hay que sumar eax y ecx antes de bajar a memoria. El carry que se produce por sumar ecx y edx hay que pasarlo a edx. Ese pasaje de carry NO puede producir carry, por el tamaño de los numeros.<br />
<br />
(incPunteros)<br />
mov eax, [esi]<br />
mul ebx<br />
add eax, ecx<br />
adc edx, 0<br />
mov [edi], eax<br />
mov ecx, edx</div>157.92.4.151https://www.cubawiki.com.ar/index.php?title=Apuntes_primer_parcial_03/10/2006_(Organizaci%C3%B3n_del_Computador_II)&diff=320Apuntes primer parcial 03/10/2006 (Organización del Computador II)2006-10-04T00:30:33Z<p>157.92.4.151: </p>
<hr />
<div>== Strings ==<br />
<br />
Averigue el puntero/longitud a la meseta mas larga<br />
Meseta es repeticion de letras iguales<br />
<br />
Se anidan dos ciclos/funciones/macros. <br />
<br />
Macro interna longMeseta:<br />
<br />
Dado esi (en strings, puntero al src, en gral), devuelve la longitud de la meseta q empieza en esi.<br />
Requiere: esi al comienzo de la meseta<br />
bit de direcciones en avanzar<br />
Asegura: esi en el caracter siguiente a la meseta<br />
ecx tiene la longitud del resto de la cadena<br />
ebx es la longitud de la meseta<br />
<br />
Se puede hacer mediante la instruccion scas. Se usa un lodsb para levantar el 1er byte de la meseta, el scas para iterar, y un repe para iterar mientras sea igual. La longitud de la meseta es la diferencia entre el esi del final y el esi del ppio. <br />
<br />
Se debe llamar a longMeseta para recorrer toda la cadena, en un ciclo externo.<br />
<br />
while ecx>0<br />
longMeseta<br />
ebx= max(ebx, max_actual)<br />
<br />
== Instruccion LEA ==<br />
<br />
lea reg, [reg1 + reg2*t + k]<br />
<br />
Tiene el mismo formato que un modo de direccionamiento<br />
Donde t es 1,2,4,8; k es un inmediato de 32 bits; y los registros son de 32 bits<br />
<br />
== Pila ==<br />
<br />
El push decrementa<br />
El pop incrementa<br />
<br />
== Numeros grandes ==<br />
<br />
Para laburar con enteros grandes, se pueden hacer suposiciones sobre el tamaño maximo de los mismos. No hay que validar de mas en assembler, la idea es funciones rapidas.<br />
<br />
<br />
==== Multiplicacion de numeros grandes por potencias chicas de 2 ====<br />
<br />
Sea el numero 08 00 CA FE<br />
Lo consideramos "grande" para este ejercicio<br />
<br />
Lo queremos multiplicar por 2<br />
En el primer byte uso un SHL/SAL 1<br />
En los siguientes, RCL, rotate left circular<br />
<br />
El shift saca el bit mas significativo y lo mete en el CF<br />
El RCL hace un shift, mete el CF en el menos significativo, y pisa el CF con el mas significativo q saco afuera<br />
El ROL pasa directamente del mas significativo al menos, y copia el mas significativo al CF<br />
<br />
El SHR mete un cero en el mas significativo, y el SAL repite el 7mo bit.<br />
Tiran el bit menos significativo que sacaron en el CF.<br />
Para dividir hay que ir del dword mas significativo al menos.<br />
<br />
Para multiplicar por 4, no conviene correr 2 veces el algoritmo anterior por los accesos a memoria<br />
Como se necesitarian 2 carry flag, se puede ir tirando los bits del carry a otro registro, haciendo RCL del reg que tiene el numero para cargar el carry, despues otro RCL contra el reg adicional para guardar ahi el carry, y asi sucesivamente. Antes de seguir a la proxima dword, se shiftea lo necesario para pasar los bits guardados de la parte mas alta a la mas baja.<br />
Otra posibilidad es guardar los bits mas significativos con operaciones logicas: copiar el registro y hacer un and con una mascara que deje solo los mas altos que se quieran guardar.<br />
<br />
<br />
==== Multiplicar numeros grandes con signo ====<br />
<br />
Para multiplicar numeros grandes, primero pasar los dos a positivo y despues multiplicar, y ver cual deberia ser el signo del resultado.<br />
<br />
Para cambiar de signo, empiezo por el menos significativo y voy negando y sumando uno (el carry despues de la 1er dword). La negacion se puede hacerla en los registros, no negarlo en memoria. Hay que guardar el carry en ese caso para saber que sumar.<br />
<br />
<br />
==== Multiplicar un numero grande por un registro de 32bit ====<br />
<br />
Se tiene un numero grande en memoria, en esi el puntero. En ebx el numero por el que se quiere multiplicar. Cargo la parte baja en eax, multiplico por ebx y queda el resultado en edx:eax. En la 1er iteracion, se puede bajar eax directamente. La parte alta, edx, es necesario guardarla (x ej en ecx). <br />
<br />
mov eax, [esi]<br />
mul ebx<br />
mov [edi], eax<br />
mov ecx, edx<br />
<br />
Luego hay que sumar eax y ecx antes de bajar a memoria. El carry que se produce por sumar ecx y edx hay que pasarlo a edx. Ese pasaje de carry NO puede producir carry, por el tamaño de los numeros.<br />
<br />
(incPunteros)<br />
mov eax, [esi]<br />
mul ebx<br />
add eax, ecx<br />
adc edx, 0<br />
mov [edi], eax<br />
mov ecx, edx</div>157.92.4.151https://www.cubawiki.com.ar/index.php?title=Categor%C3%ADa:Organizaci%C3%B3n_del_Computador_II&diff=2058Categoría:Organización del Computador II2006-10-04T00:28:07Z<p>157.92.4.151: </p>
<hr />
<div>__NOTOC__<br />
<br />
== Contenidos ==<br />
<br />
== Profesores notables==<br />
<br />
== Apuntes ==<br />
*[[Orga2 - Apuntes primer parcial 03/10/2006| Apuntes primer parcial 03/10/2006]]: Clase del 03/10/2006 de Emilio Platzer con tips para el primer parcial.<br />
<br />
== Enlaces externos ==</div>157.92.4.151https://www.cubawiki.com.ar/index.php?title=Organizaci%C3%B3n_del_Computador_II&diff=252Organización del Computador II2006-10-04T00:28:07Z<p>157.92.4.151: </p>
<hr />
<div>__NOTOC__<br />
<br />
== Contenidos ==<br />
<br />
== Profesores notables==<br />
<br />
== Apuntes ==<br />
*[[Orga2 - Apuntes primer parcial 03/10/2006| Apuntes primer parcial 03/10/2006]]: Clase del 03/10/2006 de Emilio Platzer con tips para el primer parcial.<br />
<br />
== Enlaces externos ==</div>157.92.4.151