Issuu

Algoritmos. JULIO DEL 2021.

Algoritmos de búsqueda.

¿Qué es el algoritmo? Según el profesor Ricardo Peña Marí. “Es el conjunto de reglas que, aplicada sistemáticamente a unos datos de entrada apropiados, resuelven un problema en un numero finito de pasos elementales”.

Estructura de control. Todos los lenguajes de programación modernos tienen estructuras de control similares.

Cualquier instrucción es un algoritmo si:

·S us puntos no permiten diferentes variantes del desarrollo. ·L as indicaciones están proporcionadas para todos los escenarios posibles.

Editorial. Un algoritmo se define como un conjunto de pasos lógicos para resolver un problema. Es propio de un algoritmo tener precisión, finitud y determinismo. Dentro de estos se suelen emplear una serie de instrucciones, entre ellas tenemos las instrucciones o estructuras de control. Las estructuras de control permiten modificar el flujo de ejecución de las instrucciones de un programa. Todas las estructuras de control tienen un único punto de entrada y un único punto de salida. Los algoritmos son el objeto de estudio de la algoritmia. En la vida cotidiana, se emplean algoritmos frecuentemente para resolver problemas, en términos de programación, un algoritmo es una secuencia de pasos lógicos que permiten solucionar un problema. Autor (a):

Sahenndry Carreño.

Índice. 1

¿Qué es un algoritmo?

Estructura de control del algoritmo.

Estructuras selectivas.

Estructuras secuenciales.

Estructuras interactiva en el algoritmo.

Algoritmo de búsqueda.

Búsqueda secuencial.

Búsqueda binaria.

¿Qué es un algoritmo? Es una serie de instrucciones sencillas que se llevan a cabo para solventar un problema. Además de ser un mecanismo ciego y sin voluntad, pero que, está cambiando el mundo de forma definitiva y merece la máxima atención

“Conjunto de reglas que, aplicada sistemáticamente a unos datos de entrada apropiados, resuelven un problema en un numero finito de pasos elementales”. Según enuncia el profesor de la Facultad de Informática de la Universidad Complutense Ricardo Peña Marí, autor a la sazón del libro De Euclides a Java, la historia de los algoritmos y de los lenguajes de programación (Nívola). “Es importante notar que el algoritmo tiene que ser finito y que ejecuta las instrucciones de manera sistemática, es decir, que es ciego ante lo que está haciendo, y que los pasos con los que opera son elementales”, comenta el profesor.

Estructura de un algoritmo. Todo algoritmo consta de tres secciones principales: Entrada: Es la introducción de datos para ser transformados. Proceso: Es el conjunto de operaciones a realizar para dar solución al problema. Salida: Son los resultados obtenidos a través del proceso.

Estructura de control del algoritmo. Son instrucciones que permiten romper la secuencialidad de la ejecución de un programa; esto significa que una estructura de control permite que se realicen unas instrucciones y omitir otras, de acuerdo a la evaluación de una condición. En programación, las estructuras de control permiten modificar el flujo de ejecución de las instrucciones de un programa. Con las estructuras de control se puede: De acuerdo con una condición, ejecutar un grupo u otro de sentencias (If-Then-Else) De acuerdo con el valor de una variable, ejecutar un grupo u otro de sentencias (Select-Case) Ejecutar un grupo de sentencias mientras se cumpla una condición (Do-While) Ejecutar un grupo de sentencias hasta que se cumpla una condición (Do-Until) Ejecutar un grupo de sentencias un número determinado de veces (For-Next)

Todos los lenguajes de programación modernos tienen estructuras de control similares. Básicamente lo que varía entre las estructuras de control de los diferentes lenguajes es su sintaxis; cada lenguaje tiene una sintaxis propia para expresar la estructura. Existen 2 tipos de estructuras de control: 1. Selectivas. 2. Repetitivas. 3. Iteractivas.

Estructuras selectivas. Estas estructuras nos permite escoger entre dos o más acciones, estás evalúan una condición y a continuación ejecutan una sentencia, debes tener presente que no se ejecutan todas a la vez, o es una o es otra, pero no todas a la vez. Las estructuras selectivas se dividen en tres: ·Simples. ·Dobles. ·Múltiples. Alternativa simple (si-entonces).

Este tipo de alternativa es la más simple de todas, evalúa una condición y de ser cierta, ejecuta una acción, de ser falsa, no hace nada. Su sintaxis es la siguiente: Si (condición) entonces // Sentencias... Finsi

Ejemplo.

Verificar si el crédito de un cliente es suficiente para realizar una nueva compra y calcular su nuevo crédito disponible. Desarrollo:

If Precio < CreditoDisponible Then Cargo = "Aprobado" CreditoDisponible = CreditoDisponible - Precio End If

ESTRUCTURA SELECTIVA DOBLE (IF-ELSE-ENDIF).

Puesto que la estructura anterior es muy limitada, se creó una forma que acepta dos opciones, de esta forma siempre va a ocurrir algo porque se va a evaluar una condición, si es verdadera, entonces ejecuta una sentencia, si es falsa, se ejecuta otra. Su sintaxis es como sigue: Si (condición) entonces Escribir "Aprender a programar"; Sino Escribir "Aprender algoritmos"; Diagrama de flujo.

Finsi

Ejemplo.

El siguiente ejemplo muestra como dato de entrada la edad de una persona en la variable v Edad y se debe informar si esta persona es mayor de edad (21 años). Desarrollo:

If vEdad >= 21 Then MessageBox.Show("Es mayor de edad") Else MessageBox.Show("Es menor de edad") End If

Nota: la condición siempre va encerrada dentro de paréntesis.

ESTRUCTURA SELECTIVA MÚLTIPLE (SELECT CASE).

Como vimos en el ejemplo de la comida en el post pasado, siempre habrá un punto en donde tengamos múltiples opciones, para resolver este problema utilizamos una estructura de alternativas múltiples ya que en ocasiones puede ser más cómodo de utilizar, luego veremos que también lo podemos hacer conalternativas dobles anidadas. La alternativa múltiple (según-hacer-caso) va a evaluar una condición que podrá tomar distintos valores, según sea el resultado de esta condición, se va a ejecutar una acción especifica. Su sintaxis es: Select Case <expresión a evaluar> Case <lista de expresiones> Instrucciones Case <otra lista de expresiones> Instrucciones Case Else ‟Si no se cumple ninguna de las listas de expresiones. End Select

Ejemplo.

El siguiente ejemplo pide por medio de un inputbox un numero entre 1 y 12 y muestra una caja de mensaje con el nombre del mes del año correspondiente. Desarrollo: Dim N As Integer N = InputBox("Ingrese N?") Select Case N Case 1 : MessageBox.Show("Enero") Case 2 : MessageBox.Show("Febrero") Case 3 : MessageBox.Show("Marzo") Case 4 : MessageBox.Show("Abril") Case 5 : MessageBox.Show("Mayo") Case 6 : MessageBox.Show("Junio") Case 7 : MessageBox.Show("Julio") Case 8 : MessageBox.Show("Agosto") Case 9 : MessageBox.Show("Septiembre") Case 10: MessageBox.Show("Octubre") Case 11: MessageBox.Show("Noviembre") Case 12: MessageBox.Show("Diciembre") Case Else MessageBox.Show("Error de datos") End Select

Estructura secuenciales. La estructura secuencial es aquella en la que una acción (instrucción) sigue a otra en secuencia. Las tareas se suceden de tal modo que la salida de una es la entrada de la siguiente y así sucesivamente hasta el fin del proceso. En Pseudocódigo una Estructura Secuencial se representa de la siguiente forma:

Ejemplo 1.

En este ejemplo se convertirá de grados Celsius a grados Fahrenheit solicitando al usuario los grados Celsius. Inicio.

Ejemplo 2.

Se debe buscar el área de un triángulo solicitando el usuario base y la altura del mismo Inicio.

Real=ºC, ºF Escriba ("digite los grados Celsius"); Lea (ºC); ºF=(9/5* ºC)+32; Escriba ("los grados Celsius a Farenheit son= ", ºF); Final.

Real= B, H, Atri; Escriba ("digite base"); Lea (B); Escriba ("digite altura"); Lea (H); Atri= b*h/2; Escriba ("el área del triángulo es=", atri); Final.

Estructura iteractiva en el algoritmo. Los algoritmos iterativos son algoritmos que se caracterizan por ejecutarse mediante ciclos. Estos algoritmos son muy útiles al momento de realizar tareas repetitivas. Casi todos los lenguajes de programación modernos tienen palabras reservadas para la realización de iteraciones. La opción al uso de algoritmos iterativos es el uso de la recursividad en funciones. Estas implican una escritura más sencilla (corta), tanto para su implementación como para su entendimiento, pero en contraparte, utilizan mucho más recursos de sistema que una iteración debido a que necesitan, además del uso del procesador, la pila del sistema para "apilar" los diversos ámbitos de cada función. Una de las características importantes que se pueden aprovechar de las computadoras es precisamente su capacidad de repetir la ejecución de secuencias de instrucciones a una gran velocidad y con alto grado de confiabilidad. Para estos fines, precisamente se definen en los lenguajes de programación las estructuras de control iterativas. En C#, las instrucciones while, do/while, y for, permiten ejecutar iteraciones, bucles o ciclos. En cada caso se ejecuta un bloque de instrucciones mientras la condición que se evalúa tome valor verdadero. Se resalta que cualquiera de las 3 instrucciones cumple con el mismo objetivo que es el de ejecutar una secuencia de pasos, más de una vez.

Estructura iteractiva While. Cuando se ejecuta la instrucción while, se evalúa la condición (expresión booleana) escrita en los paréntesis, si su resultado es verdadero (1) entonces se realiza el ciclo, posteriormente, esta condición vuelve a ser reevaluada y se procede de la misma manera, este proceso continua hasta que la condición se vuelve falsa (0), dando por terminado el ciclo .

Si la condición no se vuelve falsa, entonces el ciclo nunca termina, terminando de esta forma en ciclo infinito.

Ejemplo.

En esta estructura no es necesario conocer el número de veces que se repite el ciclo, ya que esto depende de la condición definida.

Dado un número natural n se desea calcular la suma de los números naturales desde 1 hasta n. Inicio. n: entero /* se define la variable para el número */ suma: entero /* se define la variable para la suma */ i: entero /* se define la variable para recorrer los números entre 0 y n */ escribir ( “Escriba el numero: ” ) leer (n) /* lee el primer número */ suma = 0 /* inicia la suma en cero */ i :=1 /* empieza la variable que recorre los números en 1 */ mientras (i <= n) hacer suma = suma + i /* en cada iteración suma el número i */ i = i + 1 /* para tomar el siguiente número en la próxima iteración */ fin_mientras escribir (“La suma es: ”, suma).

Estructura iteractiva For. La estructura para (for) es la más utilizada y sencilla de manejar, consiste en repetir un conjunto de instrucciones un número determinado de veces.

Una de sus aplicaciones principales se tiene en los arreglos.

Ejemplo. El problema de calcular la suma de los números naturales desde 1 hasta n (enunciado anteriormente), se puede solucionar usando el bucle para, a continuación se muestra el algoritmo solución: Inicio. n: entero /* se define la variable para un número entero*/ suma: entero /* se define la variable para la suma*/ i: entero /* se define la variable la variable contadora */ escribir(“ingrese el número:”) leer n /* lee el primer número */ suma = 0 para(i =1 hasta n)hacer suma =suma + i fin_para escribir (“La suma es:”, suma)

Estructura iteractiva Do-While. Esta estructura permite repetir una acción mientras la condición es verdadera; cuando es falsa se sale de ciclo. La condición es revisada después de que el cuerpo del bucle es ejecutado. Se utiliza cuando se requiere que el ciclo se ejecute por lo menos una vez.

Ejemplo. El problema de calcular la suma de los números naturales desde 1 hasta n (enunciado anteriormente), se puede solucionar usando el bucle REPETIR… MIENTRAS. A continuación se describe el algoritmo solución:

La estructura repite y el mientras pueden ser utilizados cuando no se conoce de antemano cuantas veces ha de ser repetido el ciclo.

Inicio. n: entero /* se define la variable para el número */ suma: entero /* se define la variable para la suma */ i: entero /* se define la variable para recorrer los números entre 0 y n */ escribir ( “Introduzca el número: ” ) leer (n) /* lee el primer número */ suma :=0 /* inicia la suma en cero */ i =1 /* empieza la variable que recorre los números en 1 */ haga suma := suma + i /* en cada iteración suma el número i */ i = i + 1 /* incrementa i en 1 para tomar el siguiente número en la próxima iteración */ mientras (i <= n) escribir ( “La suma es: ”, suma ) fin.

Algoritmos de búsqueda. Es un conjunto de instrucciones que describen el procedimiento a seguir para lograr encontrar un resultado determinado y concreto en la red, dentro de una estructura de datos de mayor envergadura. Esta palabra supone una prescripción precisa de las acciones que se deben realizar para alcanzar un fin específico. Cualquier instrucción es un algoritmo si: ·Sus puntos no permiten diferentes variantes del desarrollo. ·Las indicaciones están proporcionadas para todos los escenarios posibles.

Los buscadores más utilizados actualmente son: Yandex: Este programa fue creado en 1988 por la empresa CompTek, aunque el motor de búsqueda Yandex-Web fue presentado al mundo el día 23 de septiembre de 1997.

La primera versión del programa de búsqueda llamado «Yandex» apareció en 1993, aunque en aquella época era más bien una herramienta para encontrar información dentro de un solo sitio web. En 2008 Yandex lanzó una actualización llamada Magadán. Con esta actualización se resolvía el problema de interpretación de abreviaturas y transliteración y, además, la correlación entre palabras con la misma raíz. Esa update es nuevamente actualizada unos meses después añadiendo factores de ranking adicionales. En 2008 y 2009 ven la luz Najodka y Arzamás, cuyo objetivo es mejorar los resultados para «queries» con conjunciones y preposiciones.

Bing: es el buscador web de Microsoft por excelencia, presentado en mayo de 2009. En julio del 2009, Microsoft y Yahoo! anuncian que Bing reemplazaría a Yahoo! Search, momento en el que también lanzan la nueva araña web, llamada MSN bot 2. Todo esto demuestra que éste es un motor de búsqueda relativamente nuevo. A pesar de ello, Bing ocupa el segundo lugar en el ranking de buscadores más populares según volumen de tráfico. A pesar de esta popularidad, los cambios de su algoritmo de búsqueda no son tan famosos como los de Google o de Yandex y, a diferencia de esos dos, Bing no revela las updates realizadas y no les da nombres como lo hacen Yandex y Google. Google: En una conferencia cerrada a principios de Mayo de 2014, el representante de Google mencionó que hoy en día están indexados 60 billones de documentos.

El motor de búsqueda de Google fue creado como un proyecto escolar por los estudiantes de la Universidad de Stanford Larry Page y Sergey Brin. En 1996 trabajan para el sistema de motores de búsqueda llamado BackRub y, basándose en él, crean dos años más tarde un nuevo motor de búsqueda: Google.

Tipos de búsqueda. Búsqueda secuencial. Se utiliza cuando el contenido del Vector no se encuentra o no puede ser ordenado. Consiste en buscar el elemento comparándolo secuencialmente con cada elemento del arreglo o conjunto de datos hasta que se encuentre, o hasta que se llegue al final del arreglo. La existencia se puede asegurar desde el momento que el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo. El pseudocódigo del algoritmo: Datos de Entrada:

inicio. vec: vector en el que se desea buscar el elemento tam: tamaño del vector dato: elemento que se quiere buscar. Variables pos: posición actual en el array pos = 0 Mientras pos < tam: Si vec[pos]== dato devolver verdadero y/o pos, de lo contrario: pos = pos + 1 Fin (Mientras) Devolver falso

Búsqueda binaria. Se utiliza cuando el vector en el que queremos determinar la existencia o no de un elemento está ordenado, o puede estarlo, este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente con el número de iteraciones.

El pseudocódigo del algoritmo: Datos de Entrada: inicio. vec: vector en el que se desea buscar el elemento tam: tamaño del vector dato: elemento que se quiere buscar. Variables centro: elemento central del intervalo inf: límite inferior del intervalo sup: límite superior del intervalo inf = 0 sup = tam–1 Mientras inf <= sup: centro = ((sup + inf) / 2) /* división entera: se trunca la parte decimal */ Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario: Si dato < vec[centro] entonces: sup=centro–1 En caso contrario: inf=centro+1 Fin (Mientras) Devolver Falso

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del arreglo o conjunto de datos, si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del arreglo que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del arreglo que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible, con el elemento buscado como elemento central. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en el arreglo

Ejemplos: Algoritmo de búsqueda secuencial.

Desarrollar un programa que posea una función que reciba como parámetro un arreglo de 10 enteros, y un entero, y retorne la posición del entero si es que se encuentra, de lo contrario devolver – 1.

#include <stdio. h> int encuentra(int A[], int b) { int k=1, result=-1; do{ if (A[k]== b) result =k; else k++; }while ((result==-1)&& (k<10)); return result; } int main() { int i, x[10];

Algoritmo de búsqueda binaria.

Función BB (v: vector; i,d,k:natural) devuelve booleano si (i = d) entonces devuelve (v [i] = k); sino si (v [(i+d)] < k) entonces devuelve BB (v, (i+d)/2 + 1, d, k); sino devuelveme BB (v, i, (i+d)/2, k); fsi ffuncion

for(i=0;i<10;i++) scanf("%d",&x[i]); i = encuentra( x, 10); printf("resultado %d\n",i); return 0; }

El arte desafía a la tecnología y la tecnología inspira el arte.

¿ sabes cual es el problema? Imaginarte el algoritmo y no programarlo. (Paul Hueca) Un programador que escriba un código limpio, entiende perfectamente el problema antes de escribir el código...

Las matemáticas significan esencialmente la existencia de un algoritmo mucho más preciso que el del lenguaje ordinario a menudo precedió a la formulación matemática, a la invención de un algoritmo. (Ludwig Von Bertalanffy) No documentes un problema. ¡arréglalo!