martes, 27 de mayo de 2014

Introduction to algorithms 3rd. edition - Excercises

Introduction to algorithms 3rd. edition
THOMAS H. CORMEN
CHARLES E. LEISERSON
RONALD L. RIVEST
CLIFFORD STEIN

Ejercicios
1.1-1 Organizar un padrón electoral; diseñar la carcasa de un coche.
1.1-2 Gastar los mínimos recursos (papel, nafta, horas de cierta maquinaria).
1.1-3 Lista doblemente enlazada: fortaleza: fácil inserción/borrado en cualquier lado. Debilidad: para llegar a un elemento se requiere acceder a todos los anteriores.
1.1-4 Que uno tiene que volver al punto de partida y el otro no. Que en uno los caminos son en cualquier sentido y en el otro hay que elegir un camino según el sentido.
1.1-5 Marcar un número de teléfono: sólo se admite el número exacto. Calcular las cantidades de comida de una dieta: se puede aproximar. Realizar una comida con una receta: las cantidades de cada ingrediente no tienen que ser exacta, los minutos de cocción, batido, etc. también se pueden aproximar.

1.2-1 Un programa de dibujo de gráficos / de manejo de un plotter: calcular los puntos de una curva, una calculadora de bolsillo: entre otras cosas tiene que interpretar las fórmulas y realizar las operaciones; programa de manejo de un lavarropas: el usuario pone el programa que quiere (una secuencia de etapas) y el lavarropas las ejecuta.
1.2-2
8 n^2 < 64 n lg n
n < 8 lg n
n <~ 40 (valor entero de lg n más cercano: 5 <=> n = 32)
1.2-3
100 n^2 < 2^n
lg (100 n^2) < lg 2^n
lg 100 + 2 lg n < n
lg 100 < n - 2 lg n
7 <~ n - 2 lg n
16 <~ n

Problemas

f(n) = [microseconds]
1 s = 1.000.000  µs
1 m = 1.000.000 * 60  µs



1  second
1 minute
1 hour
1 day
1 month
1 year
1 century
  lg n
 2^1.000.000
2^1.000.000*60
2^1.000.000*3.600
2^1.000.000*3.600*24
2^1.000.000*3.600*24*30
2^1.000.000*3.600*24*365
2^1.000.000*3.600*24*36.500
  \/¯n
 1.000.000^2






  n
 1.000.000






  n lg n
 ~ 2^16






  n^2
 1.000






  n^3
 100






  2^n
 ~ 20






  n!
 ~ 10





~ 17

1 second:
n lg n < 1.000.000
n lg n <~ 2^20 = 2^16 . 2^4  /// 16+4=20  y  lg 2^16=2^4
n <~ 2^16

n! < 1.000.000
n <~ 10

1 century:
n! < 1.000.000*3.600*24*36.500
n  <~ 17

1000000*3600*24*36500= 3.1536E+15
3153600000000000/2= 1.5768E+15
1576800000000000/3= 5.256E+14
525600000000000/4= 1.314E+14
131400000000000/5= 2.628E+13
26280000000000/6= 4.38E+12
4380000000000/7= 6.2571E+11
625714285714.286/8= 7.8214E+10
78214285714.2857/9= 8690476190
8690476190.47619/10= 869047619
869047619.047619/11= 79004329
79004329.004329/12= 6583694.08
6583694.08369408/13= 506438.006
506438.006438007/14= 36174.1433
36174.1433170005/15= 2411.60955
2411.6095544667/16= 150.725597
150.725597154169/17= 8.8662116
8.86621159730404/18= 0.49256731


Siguiente: página 22 (43/1313), Exercises
2.1-1
Using Figure 2.2 as a model, illustrate the operation of I NSERTION-SORT on the array A D h31;41;59;26;41;58i.



2.1-2 Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of non-decreasing order.
INSERTION-SORT .A/
1 for j = 2 to A.length
2   key = A[j]
3   // Insert j into the sorted sequence A[1..j-1].
4   i = j - 1
5   while i > 0 and A[i] < key
6     A[i - 1] = A[i]
7     i = i - 1
8   A[i + 1] = key



2.1-3
Consider the searching problem:
Input: A sequence of n numbers A =  (a 1 ;a 2 ;...;a n ) and a value v.
Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.
Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
i = A.length
while i >= 0 and A[i]<>v
  i = i-1

Loop invariant: At the start of each iteration none of the elements at the right hand side are the searched one. And the searched element is either the one at the current iteration or any of the others at the left hand side, if it exists.
Initialization: It is true prior to the first iteration of the loop.
At the first loop, all of the array is at the left hand side. Only the current element is being looked at. The right hand side has no elements.
Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
At each iteration, which goes through downwards, the elements on the right hand side are all failed to the searched condition. And the left ones aren't yet tested.
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
When the loop terminates, it was either because all the array stand at the right hand side or the last one examined was the searched one. The left hand side, consists of the elements not examined, if any.

2.1-4
Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an n+1-element array C. State the problem formally and write pseudocode for adding the two integers.

The binary sum of 2 numbers is:
For all the digits:
0 if both digits and the overflow is 0
1 if one and only one of the 3 is 1
0 if 2 of them are 1, and carrying overflow=1 since that
1 if the 3 are 1, and carrying overflow=1 either
The overflow is always taken from a less-significant-ward digit (hence the least one has not overflow).

overflow='0'
for i=0 to A.length  // A.length = B.length
  if overflow='0'
    if A[i]='0'
      C[i] = B[i]
    else
      if B[i]='0'
        C[i]='1'
      else
        C[i]='0'
        overflow='1'
  else
    if A[i]='0'
      if B[i]='0'
        C[i]='1'
        overflow='0'
      else
        C[i]='0'
    else
      C[i]=B[i]
C[i]=overflow    // exit loop with i = C.length = A.length+1

  

2.2-1 n^3
2.2-2 
// SELECTION-SORT

for i=0 to A.length-1
  jMin = i
  min = A[jMin]

  for j = i+1 to A.length
    if A[j] < min
      jMin = j
      min = A[jMin]
  A[jMin] = A[i]
  A[i] = min


Loop invariant: At the start of each outer iteration the elements at the left side are sorted.
Initialization: It is true prior to the first iteration of the loop.
At the first loop, all of the array is at the right side. The left side is void and since it has none element it's "sorted".
Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
At each outer iteration, the current element is exchanged with the least from the right side, taking part of the left side in the next iteration and being the least of the remainder means to be is order with the others.
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
When the loop terminates, All the array is at the left side, except the last element which is the remainder and therefore is the greater of all, resulting in all the array being sorted.

// SELECTION-SORT

for i=0 to A.length-1      // c1  n
  jMin = i                 // c2  n-1
  min = A[jMin]            // c3  n-1

  for j = i+1 to A.length  // c4  sum(i=1..n) i
    if A[j] < min          // c5  sum(i=1..n-1) i
      jMin = j             // c6  sum(i=1..n-1) ti
      min = A[jMin]        // c7  "
  A[jMin] = A[i]           // c8  n-1
  A[i] = min               // c9  n-1

Best case: ti=0:  c1 n + (c2+c3+c8+c9)(n-1)+c4 n (n+1)/2 -1 + c5 n (n-1) /2=
= (c1+c2+c3+c8+c9) n - (c2+c3+c8+c9) + (c4 n^2 + c4 n) / 2 - 1 + (c5 n^2 -c5 n) / 2 =
= (c1+c2+c3+c8+c9) n - (c2+c3+c8+c9) + (c4+c5) n^2 / 2 + (c4 - c5) n / 2 - 1= 
= (c1+c2+c3+c8+c9+c4/2-c5/2) n - (c2+c3+c8+c9) + (c4+c5) n^2 / 2 - 1= a n^2 + b n + c
Worst case ti=i: c1 n + (c2+c3+c8+c9) (n-1) + c4 n (n+1) / 2 - 1 + (c5+c6+c7) n (n-1) / 2 =
= ... = (c1+c2+c3+c8+c9+c4/2-c5/2-c6/2-c7/2) n - (c2+c3+c8+c9) + (c4+c5+c6+c7) n^2 / 2 - 1= a n^2 + b n + c

2.2-3
average case: sum(i=0..n) i / n = [n (n+1) /2 -1]/n ~ n/2
worst case: n
O() notation:
average case: O(n) (like the average running time but coefficient omitted).
worst case: O(n)

2.2-4 To first check if the input already meets the supposed output so as to avoid any processing.

2.3-1
Using Figure 2.4 as a model, illustrate the operation of merge sort on the array
A = <3;41;52;26;38;57;9;49>

2.3-2
Rewrite the M ERGE procedure so that it does not use sentinels, instead stopping
once either array L or R has had all its elements copied back to A and then copying
the remainder of the other array back into A.




MERGE (A, p, q, r)
1. n1 = q - p + 1
2. n2 = r - q
3. let L[1..n1] and R[1..n2] be new arrays
4. for i = 1 to n1
5. L[i] = A[p + i - 1]
6. for j = 1 to n2
7. R[j] = A[q + j]
8. i = 1
9. j = 1
10. k = p
11. while i<=n1 and j<=n2
12. if L[i] <= R[j]
13. A[k] = L[i]
14. i = i + 1
15. else A[k] = R[j]
16. j = j + 1
17. // end if
18. k = k+1
19. // end while
20. while i<=n1
21. A[k] = L[i]
22. i=i+1
23. k=k+1
24. //end while
25. while j<=n2
26. A[k] = R[j]
27. j=j+1
28. k=k+1
29. //end while


MERGE-SORT (A;p;r)
1. if p < r
2. q = floor((p + r)/2)
3. MERGE-SORT (A;p;q)
4. MERGE-SORT (A;q + 1;r)


2.3-3
Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence
T(n)=
{
2 if n = 2 ;
2T(n/2) + n if n = 2^k , for k > 1
is T(n)= n lgn.





2.3-4



 


2.3-5

2.3-5 Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is O(lg n).

BINARY-SEARCH(A, v)
p=1
q= A.length
MIENTRAS p<=q && v<> A[(p+q)/2]
  SI v < A[(p+q)/2]
    q= (p+q)/2-1
  SI v > A[(p+q)/2]
    p= (p+q)/2+1
SI p<=q
  DEVOLVER (p+q)/2
SI NO
  DEVOLVER NIL


BINARY-SEARCH-R(A,v,p,q)
SI p>q                                                // c1
  DEVOLVER NIL                                        // c2
SI v= A[(p+q)/2]                                      // c3
  DEVOLVER (p+q)/2                                    // c4
SI v < A[truncar((p+q)/2)]                            // c5
  DEVOLVER BINARY-SEARCH-R(A,v,p,truncar((p+q)/2)-1)  // T1: T(n/2-1), excluyente con T2
SI v > A[(p+q)/2]                                     // c6     // C=c1+c2+c3+c4+c5+c6
  DEVOLVER BINARY-SEARCH-R(A,v,truncar((p+q)/2)+1,q)  // T2: T(n/2-1), excluyente con T1


BINARY-SEARCH(A,v)
  DEVOLVER BINARY-SEARCH-R(A,v,1,A.length)


 

sábado, 17 de mayo de 2014

Windows desactivar programar que se ejecutan al inicio

Método 1: Inicio -> Ejecutar -> MSCONFIG ->seguir los pasos de http://www.wikihow.com/Alter-Startup-Programs-in-Windows-XP

Método 2: Descargar Windows Defender de download.cnet.com -> seguir los pasos del mismo link de arriba

Método 3: Editor del Registro de Windows (regedit), las claves donde están los startup programs:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Run
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\RunOnce
Seguir la explicación en el mismo link que el método 1.

Método 4: Buscarlo y borrarlo de la carpeta "Inicio": Inicio -> Programas -> Inicio

Método 5: Inicio -> Programas -> Accesorios -> Herramientas del sistema -> Tareas Programadas: eliminar el programa no deseado

Método 6: Panel de control -> Herramientas Administrativas -> Servicios: los servicios que están como "inicio automático", poner "manual" o "desactivado".

Windows administrador de hardware

La forma de ver el hardware instalado en Windows:
Panel de control -> Sistema -> Hardware

Sin embargo, si es una placa madre con hardware integrado (ej.: placa de sonido), puede que no aparezca hasta que se instale el controlador.


Para visualizar el hardware más a bajo nivel, por ejemplo para ver el modelo del mother y así poder buscar el controlador del fabricante: Inicio -> Programas -> Accesorios -> Sistema -> Información del sistema. Se puede exportar en txt y en formato INFO.

Si hay un dispositivo no reconocido (en Panel de Control -> Sistema -> Hardware) que a la vez impideque se instale el nuevo controlador, hay que eliminarlo, y hacer una "búsqueda de cambios en el sistema" (siempre en Panel de Control -> Sistema -> Hardware), y cuando vuelve a detectar el hardware eliminado, no permitir que Windows instale el controlador automáticamente, luego, instalar el que bajamos de Internet / CD / etc.: Solucion para error driver de audio xp sp3

lunes, 5 de mayo de 2014

Seguridad informática

OpenPGP
The GNU Privacy Guard
Transport Layer Security - Wikipedia, the free encyclopedia
OpenSSL: The Open Source toolkit for SSL/TLS
Gentoo Forums :: View topic - openssl vs gnupg in initrd for encrypting LUKS-keyfile
OpenPGP "añade un poco de sal" al rededor del mensaje en claro en el proceso de encriptación. Si lo que estoy encriptando es un mensaje expresado en lenguajes naturales (inglés, español, símbolos matemáticos, etc.), esta "sal agregada" contribuye a la dificultad de someter el mensaje encriptado a análisis estadísticos. En cambio, si lo que estoy encriptando es un código generado por un random-number-generator, como ser la key de una partición LUKS, no añade valor criptográficamente hablando.
encryption - Are private keys generated by different software packages compatible? - Information Security Stack Exchange
RSA (cryptosystem) - Wikipedia, the free encyclopedia
Uso de un criptosistema para la encriptación / desencriptación de documentos:
A public and private key each have a specific role when encrypting and decrypting documents. A public key may
be thought of as an open safe. When a correspondent encrypts a document using a public key, that document is
put in the safe, the safe shut, and the combination lock spun several times. The corresponding private key is the
combination that can reopen the safe and retrieve the document. In other words, only the person who holds the
private key can recover a document encrypted using the associated public key.
Open safe
Uso de un criptosistema para la firma / verificación de documentos:

Creating and verifying signatures uses the public/private keypair in an operation different from encryption and decryption. A signature is created using the private key of the signer. The signature is verified using the corresponding public key.

Signature



Moving/Copying your PGP Keys

Encriptar una Partición:
Comparación de técnicas: Encrypting an entire system (ver la tabla comparativa en "Overview").
Otra técnica: En lugar de encriptar la partición entera, encripta a nivel de archivo individual encfs
Paso a paso: How To Migrate to a full encrypted LVM system

Bases de datos de contraseñas en Debian:
pwsafe es un administrador de contraseñas por línea de comandos.
A partir de Wheezy, no existe más el package pwsafe en el repositorio oficial. Repositorio alternativo. Aplicación alternativa: KeePass2.
Referencias:
http://blog.steve.org.uk/a_mixed_week_with_minor_tweaks.html
http://forums.debian.net/viewtopic.php?f=10&t=105015



Temas relacionados en este Blog: Seguridad informática en Java