Problema de la Coherencia de Caché y Soluciones

Universidad Autónoma del Estado de México

Facultad de Ingeniería

Ingeniería en Computación

Problema de la Coherencia de Caché y Soluciones

Profesor: Ing Elfego Gutierrez Ocampo

Alumno: Eduardo Manuel Flores Vera

PROBLEMA DE LA COHERENCIA DE CACHÉ

Pensemos por un momento cual es el modelo intuitivo que tenemos de lo que debe ser una memoria.


La memoria debe proporcionar un conjunto de direcciones para almacenar valores, y cuando se lea una de estas direcciones debe devolver el ´ultimo valor escrito  en ella.

 Es en esta propiedad fundamental de las memorias en la que descansan los programas secuenciales cuando usamos la memoria para comunicar un valor desde un punto del programa donde se calcula a otros puntos donde es usado.
También nos basamos en esta propiedad cuando el sistema usa un espacio de direcciones compartido para comunicar datos entre hebras o procesos que se est´an ejecutando en un procesador. Una lectura devuelve el ´ultimo valor escrito en esa dirección, sin importar el proceso que escribió dicho valor.


 Las cachés (antememorias) no interfieren con el uso de múltiples procesos en un procesador, ya que todos ellos ven la memoria a través de la misma jerarquía de cachés. En el caso de usar varios procesadores, nos gustaría poder basarnos en la misma propiedad cuando dos procesos se ejecuten sobre diferentes procesadores de tal forma que el resultado de ejecutar un programa que usa varios procesos sea el mismo independientemente de si los procesos se ejecutan o no en diferentes procesadores físicos. Sin embargo, cuando dos procesos ven la memoria compartida a través de diferentes cachés, existe el peligro de que uno vea el nuevo valor en su caché mientras que el otro todavía vea el antiguo.

Informalmente se puede decir que un sistema de memoria es coherente si cualquier lectura de un dato devuelve el valor más recientemente escrito de ese dato. Esta definición, aunque intuitivamente correcta, es vaga y simple; la realidad es bastante más compleja. Esta definición simple contiene dos aspectos diferentes del comportamiento del sistema de memoria, siendo los dos críticos a la hora de escribir programas en memoria compartida. El primer aspecto, llamado coherencia definen los datos devueltos por una lectura. El segundo aspecto, llamado consistencia, determina cuando un valor escrito ser´a devuelto por una lectura



Los problemas de coherencia en la caché también ocurren cuando utilizamos un ´único procesador en el caso de las operaciones de E/S. La mayor´ıa de estas operaciones se realizan a través de dispositivos DMA con lo que es posible que que el contenido de la memoria principal y la memoria caché dejen de ser coherentes.



SOLUCIONES

Sin embargo, dado que las operaciones de E/S son mucho menos frecuentes que las operaciones de acceso a memoria, se han adoptado soluciones sencillas como usar direcciones de memoria que se marcan como no almacenables en la memoria caché o eliminar todos los bloques existentes en las cachés de las páginas que se van a utilizar en la operación de E/S antes de proceder a realizar dicha operación. En la actualidad, casi todos los microprocesadores proporcionan mecanismos para soportar la coherencia de cachés



REFERENCIAS

http://informatica.uv.es/iiguia/AAC/AA/apuntes/aic_multiproc.pdf
http://www.azulweb.net/ley-de-moore-podcast-5/
http://es.wikipedia.org/wiki/Coherencia_de_cach%C3%A9

Suma PRAM CREW----- Código en Python

Universidad Autónoma del Estado de México

Facultad de Ingeniería

Ingeniería en Computación

Suma PRAM CREW----- Código en Python

Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera


#Flores Vera Eduardo Manuel
import threading
import math
import os
#Definicion del hilo
def hilo(i,j):
    a[j]=a[j]+a[j-pow(2,i-1)]
    print a

#Programa Principal
print 'SUMA CREW'
a=[]
x=int(raw_input("INGRESE EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))
i=1
while (i<=x):
    n=int(raw_input("INGRESE DATO:"))
    a.append(n)
    print a
    i+=1


n1=len(a)
lg=int(math.log(n1))

for i in range(1,lg):
    for j in range((pow(2,i-1)+1),n1):
        h = threading.Thread(target=hilo,args=(i,j))
        h.start()
        h.join()
        print i,j

print a


os.system('pause')

Multiplicación de Matrices CREW----- Código en Python

Universidad Autónoma del Estado de México

Facultad de Ingeniería

Ingeniería en Computación

Multiplicación de Matrices CREW----- Código en Python

Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera


#Flores Vera Eduardo Manuel
from threading import Thread
import math
import os

#Definicion de Funciones



def hilo1(i,j,k):
    C[k][i][j]=int(A[i][k])* int(B[k][j])

def hilo2(i,j,k,l):
    if(((2*k) % (2 **l))==0):
        C2[2*k][i][j]=int(C[2*k][i][j]+C[2*k-(2**(l))][i][j])


#Programa Principal

print "================MULTIPLICACION DE MATRICES CREW==========================="


A=[[0 for _ in range(2)] for _ in range(2)]
B=[[0 for _ in range(2)] for _ in range(2)]
C=[[[0 for _ in range(2)] for _ in range(2)] for _ in range(2)]
C2=[[[0 for _ in range(2)] for _ in range(2)] for _ in range(2)]
   
lg=int(math.log(2,2))
print "\n\n             LLENADO DE LA MATRIZ A:"
i=0
while(i<2):
    j=0
    while(j<2):
       
        print "INGRESE EL VALOR DE LA COORDENADA [",i+1 ,", ",j+1," ]: "
        x=int(raw_input())
        A[i][j]=x
        j=j+1
    i=i+1

print "\n\n             LLENADO DE LA MATRIZ B:"
i=0
while(i<2):
    j=0
    while(j<2):
       
        print "INGRESE EL VALOR DE LA COORDENADA [",i+1 ,", ",j+1," ]: "
        x=int(raw_input())
        B[i][j]=x
        j=j+1
    i=i+1


print "\nPROCEDIMIENTO DE LAS MULTIPLICACIONES : \n"
print "[ ",A[0][0],"  ",A[0][1]," ]      X      [ ",B[0][0],"  ",B[0][1]," ]"
print "[ ",A[1][0],"  ",A[1][1]," ]      X      [ ",B[1][0],"  ",B[1][1]," ]"

k=0
while(k<2):
    i=0
    while(i<2):
        j=0
        while(j<2):
            t=Thread(target=hilo1,args=(i,j,k))
            t.start()
            t.join()
            j=j+1
        i=i+1
    k=k+1


print "\n\nPRIMER PROCESO: ",C

l=0
while(l<lg):
    i=0
    while(i<2):
        j=0
        while(j<2):
            k=0
            while(k<1):
                t=Thread(target=hilo2,args=(i,j,k,l))
                t.start()
                t.join()
                k=k+1
            j=j+1
        i=i+1
    l=l+1


print "\nRESULTADO de LAS MULTIPLICACIONES DE LAS MATRICES A Y B: \n"

print "          [ ",C2[0][0][0],"  ",C2[0][0][1]," ]"
print "          [ ",C2[0][1][0],"  ",C2[0][1][1]," ]"

os.system('pause')

Ordenamiento PRAM EREW Recursivo con Odd-Even Merge Paralelo------- Código en Python

Universidad Autónoma del Estado de México

Facultad de Ingeniería

Ingeniería en Computación

Ordenamiento PRAM EREW Recursivo con Odd-Even Merge Paralelo-------Código en Python

Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera






#Flores Vera Eduardo Manuel
from threading import Thread
import os
import math


#Definicion de Funciones
def hilo3(L2,INI,FIN):
    oddEvenMerge(L2,INI,FIN)
    print "procesos: ",L2[1:FIN+1]
 

def OddEvenMerge(L2,INI,FIN):
    t3=Thread(target=oddEvenMerge,args=(L2,INI,FIN))
    t3.start()
    t3.join()

def oddEvenMerge(L2,INI,FIN):
    m=(FIN-INI)+1
    odd=[0 for _ in range((m/2)+1)]
    even=[0 for _ in range((m/2)+1)]
    if(m==2):
        if(L2[INI]>L2[FIN]):
            intercambio(L2,INI,FIN)
    else:
        oddEvenSplit(L2,odd,even,INI,m)
        t=Thread(target=ordena,args=(odd,(m/2)))
        t.start()
        t.join()
        t2=Thread(target=ordena,args=(even,(m/2)))
        t2.start()
        t2.join()
     
        i=1
        while(i<=(m/2)):
            t=Thread(target=mezcla,args=(L2,odd,even,i,1))
            t.start()
            t.join()
            i=i+1
         
        i=1
        while(i<int(m/2)):
            t=Thread(target=HiloOddEven,args=(L2,i))
            t.start()
            t.join()
            i=i+1
        i=1
        while(i<=int(m/2)):
            t=Thread(target=HiloOddEvenC,args=(L2,i))
            t.start()
            t.join()
            i=i+1
     

def intercambio(L2,INI,FIN):
    aux=L2[INI]
    L2[INI]=L2[FIN]
    L2[FIN]=aux


def oddEvenSplit(L2,odd,even,INI,FIN):
    od=1
    ev=1
    x=INI
    while(x<=FIN):
        if((x%2)==0):
            even[ev]=L2[x]
            ev=ev+1
        else:
            odd[od]=L2[x]
            od=od+1
        x=x+1
    print "valor  odd: ",odd[1:FIN+1]
    print "\nvalor  even: ",even[1:FIN+1]

 
def ordena(L2,FIN):
    L3=L2
    numero=FIN
    OddEvenMerge(L3,1,numero)


def mezcla(L2,odd,even,j,aux):
    m=L2
    impar=odd
    par=even
    m[(2*j)-1]=impar[j]
    m[2*j]=par[j]


def HiloOddEven(num,i):
    numero=num
    j=i
    a=(2*j)
    b=(2*j)+1
    if(numero[a]>numero[b]):
        intercambio(numero,a,b)

def HiloOddEvenC(num,i):
    numero=num
    j=i
    a=(2*j)-1
    b=(2*j)
    if(numero[a]>numero[b]):
        intercambio(numero,a,b)



#Programa Principal
print "====================ORDENAMIENTO PRAM EREW RECURSIVO========================="
print""
print "\n INGRESE EL NUMERO DE VALORES A INGRESAR : "
print"(NOTA: SOLO PUEDE INGRESAR UN NUMERO PAR DE VALORES A ORDENAR)"
n=int(raw_input())
while((n%2)!=0):
    print "EL NUMERO DE VALORES NO ES PAR"
    print "INGRESE UN NUMERO DE VALORES QUE SEA PAR: "
    n=int(raw_input())

L=[0 for _ in range(n+1)]
 
i=0
while(i<n):
    print "\nINGRESE VALOR NUMERO ",i+1
    x=int(raw_input())
    L[i+1]=x
    i=i+1
 
print "VALORES INICIALES: ",L[1:n+1]
OddEvenMerge(L,1,n)

print "\nVALORES ORDENADOS: ",L[1:n+1]

os.system('pause')

Ordenamiento PRAM EREW Recursivo con Merge Secuencial------- Código en Python

Universidad Autónoma del Estado de México

Facultad de Ingeniería

Ingeniería en Computación

Ordenamiento PRAM EREW Recursivo con Merge Secuencial-----Código en Python

Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera






#Flores Vera Eduardo Manuel
import os


#Definicion de Funciones
def mergeSort(alist):
    print("DIVIDIENDO ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i]<righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("UNIENDO ",alist)

#Programa Principal
alist = []
x=int(raw_input("INGRESE EL NUMERO DE VALORES A INGRESAR"))
i=1
while (i<=x):
    n=int(raw_input("INGRESE UN VALOR"))
    alist.append(n)
    i=i+1
             
   
print 'VALORES ORDENADOS:'
print(alist)

os.system('pause')

Ordenamiento PRAM CRCW------ Código en Python

Universidad Autónoma de Estado de México
Facultad de Ingeniería
Programación Paralela y Distribuida


Ordenamiento  PRAM CRCW ------ Código en Python
Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera

#Flores Vera Eduardo Manuel

from threading import Thread

import os

import math

#Definicion de Funciones

def hilo1(win,i):

    win.insert(i,0)

def hilo2(win,i,j):

    if(L[i]>L[j]):

        win[i]=win[i]+1

    else:

        win[j]=win[j]+1

def hilo3(i,win):

    L2.insert(win[i],L[i])

    L2.pop(win[i]+1)

#Programa Principal

L=[]

L2=[]

WIN=[]

indexMin=[]

print"==================ORDENAMIENTO CRCW========================"

n=int(raw_input("INGRESE EL NUMERO DE VALORES A ORDENAR: "))

i=0

while(i<n):

    print "INGRESE VALOR",i+1,":",

    x=int(raw_input())

    L.append(x)

    L2.append(0)

    i=i+1

n=len(L)

print "\nVALORES DE ENTRADA:           ",L

i=1

while(i<=n):

    t=Thread(target=hilo1,args=(WIN,i))

    t.start()

    t.join()

    i=i+1

print "\nINICIALIZANDO UN VECTOR AUXILIAR WIN WIN:              ",WIN

i=0

while(i<=n):

    j=i+1

    while(j<n and i<j):

        t=Thread(target=hilo2,args=(WIN,i,j))

        t.start()

        t.join()

        j=j+1  

    i=i+1

print "\nLLENANDO EL INDICE DE  WIN:  ",WIN

i=0

while(i<n):

    t=Thread(target=hilo3,args=(i,WIN))

    t.start()

    t.join()

    i=i+1

print "\nVALORES ORDENADOS:             ",L2

os.system('pause')

Búsqueda CRCW--------Código en Python

Universidad Autónoma de Estado de México
Facultad de Ingeniería
Programación Paralela y Distribuida


Búsqueda PRAM CRCW ------ Código en Python
Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera

#Flores Vera Eduardo Manuel

import os

import math

from threading import Thread

#Definicion de Funciones

def hilo1(Win,i):

    Win[i]=0

    

def hilo2(L,Win,i,j):

    if(L[i]>L[j]):

        Win[i]=1

    else:

        Win[j]=1

    

def hilo3(Win,i,ind):

    if(Win[i]==0):

        ind[0]=i

print "                              BUSQUEDA PRAM CRCW"

print"========================================================================================"

L=[]

x=int(raw_input("INGRESE EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))

i=1

while (i<=x):

    n1=int(raw_input("INGRESE DATO:"))

    L.append(n1)

    print L

    i+=1

Win=[1,1,1,1,1,1,1,1,1,1,1,1,1]

ind=[1000000000000000000000000]

i=0

n=len(L)

while(i<n):

    if(i>=0):

        t = Thread(target=hilo1, args = (Win,i))

        t.start()

        t.join()

    i=i+1

i=0

j=i+1

print "PROCESO 1"

print "Vector original:----->", L

print Win

while(j<n):

    if(i<j):

        if(i>=0):

            t = Thread(target=hilo2, args = (L,Win,i,j))

            t.start()

            t.join()

    i=i+1

    j=j+1

i=0

print "\nPROCESO 2"

print Win

while(i<n):

    if(i>=0):

        t = Thread(target=hilo3, args = (Win,i,ind))

        t.start()

        t.join()

        i=i+1

print "\nPROCESO 3"

print "Señalando el valor minimo con un cero en el vector 0\n", Win 

        

print " \nEl valor minimo es:  ", L[ind[0]]

os.system('pause')

Búsqueda EREW-----Código en Python

Universidad Autónoma de Estado de México
Facultad de Ingeniería
Programación Paralela y Distribuida


Búsqueda PRAM EREW ------ Código en Python
Profesor: Ing Elfego Gutierrez Ocampo
Alumno: Eduardo Manuel Flores Vera

#Flores Vera Eduardo Manuel
import os
import math
from threading import Thread

#Definicion de funciones
def hilo1(Temp2,i,j):
    Temp2.insert(j,Temp2[j-(2**i-1)])
 

def hilo2(K,Temp2,x,n):
    if(x<(n-1)):
        if(K[x]==Temp2[x]):
            Temp2[x]=x+1
        else:
            Temp2[x]=99999


def hilo3(Temp2,n,k):
    if(Temp2[(2**(k))-1]>Temp2[2**k]):
        Temp2[k]=Temp2[2*k]
    else:
        Temp2[k]=Temp2[(2**(k))-1]


def Broadcast(Temp,x,n):
    Temp2=[]
    Temp2=Temp
    Temp2.insert(0,numero)
    Temp2.insert(1,numero)
    i=1
    while(i<=lg):
        j=(2**(i-1))+1
        while(j<=2**i):
            t=Thread(target=hilo1,args=(Temp2,i,j))
            t.start()
            t.join()
            j=j+1
        i=i+1
     


def SearchPram(Temp,lista,n):
    i=0
    while(i<=n):
        t=Thread(target=hilo2,args=(lista,Temp,i,n))
        t.start()
        t.join()
        i=i+1


def MinPram(Temp,n):
    i=1
    while(i<=lg):
        j=1
        while(j<=int(n/(2**j))):
            t=Thread(target=hilo3,args=(Temp,n,i))
            t.start()
            t.join()
            j=j+1
        i=i+1




#Programa Principal
print "==================BUSQUEDA PRAM EREW=================="
a=[]
Temp=[]
lista=[]
x=int(raw_input("INGRESE EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))
i=1
while (i<=x):
    n1=int(raw_input("INGRESE DATO:"))
    lista.append(n1)
    print lista
    i+=1
n=len(lista)
lg=int(math.log(n,2))

numero=int(raw_input("ingresa el valor a buscar:"))
print "==================RESULTADOS OBTENIDOS=================="
print "------------------------------------------------------------------------"
print "NUMEROS INGRESADOS:"

print lista
Broadcast(Temp,numero,n)
print "------------------------------------------------------------------------"
print "\nVECTOR TEMPORAL: "
print Temp
SearchPram(Temp,lista,n)
print "------------------------------------------------------------------------"
print "\nINDICES:"
print Temp
MinPram(Temp,n)
h=1
while(h<len(Temp)):
    if(Temp[h]!=99999):
        pos=Temp[h]
        break
    h=h+1
print "------------------------------------------------------------------------"
print "DONDE",numero," ESTA EN LA POSICION NUMERO: ",pos

os.system('pause')

Suma EREW: Código en Python

#Flores Vera Eduardo Manuel

import threading
import math
import os
#Definicion de Funciones
def hilo(i,j):
    if ((2*j)%(2**i)==0):
        a[int(2*j)]=a[int(2*j)]+a[int((2*j)-2**(i-1))]
        print a
       
#Programa Principal
a=[]
x=int(raw_input("INGRESE EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))
i=1
while (i<=x):
    n=int(raw_input("INGRESE DATO:"))
    a.append(n)
    print a
    i+=1
n=len(a)
lg=int(math.log(n,2))
print a
i=1
while(i<=lg):
    j=1
    while(j<=(n/2)):
        t=threading.Thread(target=hilo, args=(i,j, ))
        t.start()
        j=j+1
    i=i+1
os.system('pause')

Procesamiento Pipeline

Universidad Autónoma del Estado de México

Facultad de Ingeniería 

Procesamiento Pipeline

Profesor: Ing Elfego Gutierrez Ocampo

Alumno: Eduardo Manuel Flores Vera

Fecha: Febrero de 2015

PROCESAMIENTO PIPELINE

Es aquel en el cual, los datos son procesados mediante fases que se van dividiendo en fases secuenciales. En el procesamiento Pipeline, la salida de una fase es la entrada de otra.

El procesamiento Pipeline, o tambien conocido como de segmentación, se utiliza el traspaso de la ejecucion de diversas instrucciones, siendo este, el método una de las tecnologías mas utilizadas actualmente para la fabricación de procesadores.

Este método permite varias cosas, entre las cuales estan:

• Realización de diferentes tareas con la ayuda de diferentes recursos.
• Permite el almacén para las dependencias
• La velocidad puede aumentar si se incrementa e número de segmentos
• Esta orientado al procesamiento de datos e instrucciones

Referencias

http://www.chw.net/2006/06/como-funcionan-los-pipelines-de-un-cpu/

http://www.ie.itcr.ac.cr/jdiaz/licenciatura/estructura%20de%20microprocesadores/PRESENTACIONES/pipeline-intro.pdf

http://es.wikipedia.org/wiki/Tuber%C3%ADa_(inform%C3%A1tica)

http://es.wikipedia.org/wiki/Arquitectura_en_pipeline_(inform%C3%A1tica)

Métodos de Ordenamiento (Quick Sort, Insertion Sort, Bubble Sort, Merge Sort, Selection Sort) y Búsqueda Binaria - Código en Python

UNIVERSIDAD AUTONOMA DEL ESTADO DE MEXICO

FACULTAD DE INGENIERIA

DIVISION DE INGENIERIA EN COMPUTACION

METODOS DE ORDENAMIENTO

(CODIGO EN PYTHON)

PROFESOR: ING ELFEGO GUTIERREZ OCAMPO

ALUMNO: EDUARDO MANUEL FLORES VERA

NO. CUENTA: 0914132

FECHA:ABRIL DE 2014

BUBBLE SORT

La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.

Éste algoritmo es esencialmente un algoritmo de fuerza bruta lógica 

CODIGO EN PYTHON

#Flores Vera Eduardo Manuel

importmath

import os

#Definicion de Funciones

defbubbleSort(b):

forpassnum in range(len(b)-1,0,-1):

for i in range(passnum):

if b[i]>b[i+1]:

temp = b[i]

b[i] = b[i+1]

b[i+1] = temp

#Programa Principal

b = [54,26,93,17,77,31,44,55,20]

bubbleSort(b)

print(b)

SELECTION SORT

El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O  operaciones para ordenar una lista de n elementos.

Su funcionamiento es el siguiente:

·         Buscar el mínimo elemento de la lista

·         Intercambiarlo con el primero

·         Buscar el siguiente mínimo en el resto de la lista

·         Intercambiarlo con el segundo

Y en general:

·         Buscar el mínimo elemento entre una posición i y el final de la lista

·         Intercambiar el mínimo con el elemento de la posición

  CODIGO EN PYTHON

#Flores Vera Eduardo Manuel

import os

#Definicion de Funciones

defselectionsort(a):

for i in range(len(a)):

mini = min(a[i:])

min_index = a[i:].index(mini)

a[i + min_index] = a[i]

a[i] = mini               

return a

#Programa Principal

print '===================SELECTIONSORT================='

a=[]

x=int(raw_input("INGRESE EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))

i=1

while (i<=x):

    n=int(raw_input("INGRESE DATO:"))

a.append(n)

    i+=1

a=selectionsort(a)

print a

QUICKSORT

El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare basado en la técnica de divide y vencerás, que permite, en promedio, ordenar nelementos en un tiempo proporcional a n log n.

El algoritmo trabaja de la siguiente forma:

·         Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

·         Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

·         La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

·         Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

CODIGO EN PYTHON

#Flores Vera Eduardo Manuel

import os

importmath

#Definicion de Funciones

defquicksort(cadena):

menor = []

igual = []

mayor = []

iflen(cadena) > 1:

pivot = cadena[0]

for x in cadena:

if x < pivot:

menor.append(x)

if x == pivot:

igual.append(x)

if x > pivot:

mayor.append(x)

returnquicksort(menor)+quicksort(igual)+quicksort(mayor)  # se realiza la suma para juntar las cadenas(listas)

else:  # cuando queda un solo elemento en la  cadena(lista) entonces hay que regresarlo

return cadena

#Programa principal

print "=========================QUICKSORT========================="

cadena=[]

x=int(raw_input("INGRESE EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))

i=1

while (i<=x):

    n=int(raw_input("INGRESE DATO:"))

cadena.append(n)

i+=1

cadena = quicksort(cadena)

print "SU LISTA ORDENADA CON EL METODO QUICKSORT ES:",  cadena

INSERTSORT

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²)operaciones para ordenar una lista de n elementos

CODIGO EN PYTHON

#Flores Vera Eduardo Manuel

import os

importmath

#Definicion de Funciones

definsertion_sort(a):

for i in range(1, len(a)):

        v = a[i]

        j = i

while a[j-1] > v and j>=1:

a[j] = a[j-1]

            j -= 1

a[j] = v

return a

#Programa Principal

print "=======================INSERTSORT=================="

a=[]

x=int(raw_input("INGRESE EL NUMERO DE DATOS A INGRESAR EN EL VECTOR:"))

i=1

while (i<=x):

    n=int(raw_input("INGRESE DATO:"))

a.append(n)

    i+=1

a=insertion_sort(a)

print "SU LISTA ORDENADA CON EL METODO INSERTSORT ES:",  a

os.system('pause')

MERGESORT

El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n).

Fue desarrollado en 1945 por John von Neumann .

Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:

1.   Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:

2.   Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.

3.   Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.

4.   Mezclar las dos sublistas en una sola lista ordenada

CODIGO EN PYTHON

def merge_sort(numbers):

n = len(numbers)

if(n == 1): return numbers

left = merge_sort(numbers[:(n/2)])

right = merge_sort(numbers[(n/2):])

return merge(left, right)

def merge(left, right):

result = []

i = 0

j = 0

len_left = len(left)

len_right = len(right)

while(i < len_left or j < len_right):

if(i >= len_left):

result.append(right[j])

j = j + 1

elif(j >= len_right):

result.append(left[i])

i = i + 1

elif(left[i] < right[j]):

result.append(left[i])

i = i + 1

else:

result.append(right[j])

j = j + 1

return result

def test(expected, actual):

sort = merge_sort(actual)

assert expected == sort

print actual, "is sort as", sort

test([1], [1])

test([1, 2], [2, 1])

test([1, 2, 3], [2, 3, 1])

test([1, 2, 3, 4], [2, 3, 1, 4])

test([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [10, 6, 2, 3, 5, 1, 7, 4, 9, 8]) BINARY TREE SORT El ordenamiento con árbol binario es un algoritmo de ordenamiento, el cual ordena sus elementos haciendo uso de unárbol binario de búsqueda. Se basa en ir construyendo poco a poco el árbol binario introduciendo cada uno de los elementos, los cuales quedarán ya ordenados. Después, se obtiene la lista de los elementos ordenados recorriendo el árbol en inorden CODIGO EN PYTHON #Flores Vera Eduardo Manuel import math import os #definicion de funciones class Node:     def __init__(self,data):         self.left = None         self.right = None         self.data = data   class BinaryTree(Node):     def __init__(self):         self.root = None       def addNode(self,data):         return Node(data)       def insert(self,root,data):         if(root == None):             root = self.addNode(data)         else:             if(data <= root.data):                root.left = self.insert(root.left,data)             else:                 root.right = self.insert(root.right,data)         return root       def PreOrder(self,root):         if root == None:             pass         else:             print(root.data)             self.PreOrder(root.left)             self.PreOrder(root.right)       a = BinaryTree() root = a.addNode(2) #root = None a.insert(root,4) a.insert(root,34) a.insert(root,45) a.insert(root,46) a.insert(root,41) a.insert(root,48) a.PreOrder(root)