Algoritmo

Clasificado en Informática

Escrito el en español con un tamaño de 11,3 KB

 


Qué es un algoritmo?
Un algoritmo es un conjunto finito de instrucciones precisas que realizan una tarea, la cual, dado un estado inicial, culminará por arrojar un estado final reconocible.
¿ Cuá l es el orden de ejecució n de un algoritmo?
El orden de' ejecució n será casi siempre crí tico para su funcionamiento en general, se asume que las instrucciones se enumeran explí citamente, y deben ejecutarse desde arriba hacia abajo.
¿ Mencione ejemplos de algoritmos?
*Ios instructivos (manuales de usuario)
*el algoritmo de Euclides para calcular el má ximo comú n divisor de dos enteros positivos,
*el mé todo c;le Gauss/para resolver un Sistema lineal de ecuaciones.
¿ A quié n se le atribuye el padre de la computació n digital y porque?
Alan Mathison Turing, famoso matemá tico inglé s (1912-1954), porque ideó un dispositivo imaginario al que denominó má quina de computació n ló gica (LCM, Logical Cpmputing Machlne), pero que ha recib.ido en su honor el nombre de má quina de Turlng.
¿ En que consiste la má quina de Turing?
Es un autó mata que se mueve sobre una secuencia lineal de datos. en cada instante, la má quina puede leer un ú nico dato de la secuencia (generalmente un cará cter) y realizar ciertas acciones en base a una tabla que tiene en cuenta su estado actual (interno) y el ú ltimo dato leí do.
¿ Qué acciones puede reé ;!lizar?
Puede realizar, la posibilidad de escribir nuevos datos en la secuencia, recorrer la secuencia en ambos sentidos y cambiar de estado dentro de un conjunto finito de estados posibles.
¿ Có mo especificar un algoritmo?
Para especificar un algoritmo de forma tal que su implementació n sea correcta, es decir, que haga exactamente lo que se espera de é l y que, a la vez, pueda implementarse con diferentes lenguajes o herramientas, un mé toqo consiste en definir sus entradas y salidas, con sus correspondientes precondiciones y poscondiciones.
I

8) ¿ Cuá l es la historia del algoritmo?

Proviene del nombre ~el matemá tico llamado Muhammad ibn Musa al-Khwarizmi, Su trabajo consistió en simplificar la matemá tica a punto tal que pudieran ser comprendidas y aplicadas por un mayor nú mero de personas. Tambié n estudió la manera de reducir las operaciones que formaban el cá lculo. , de la palabra algorismo, que originalmente hacíí ;l referencia a las reglas de uso de la ¡ ;¡ ritmé tica utilizando dí gitos á rabes, se evolucionó í ;lla palabra latina, derivació n de alKhwarizmi, algobarismus, que má s tarde mutarí a a algoritmo en el siglo XVIII. La palabra ha cambiado de forma que en SI,J definició n se incluye a todos los procedimientos finitos para resolver problemas.

9) ¿ Cuá les son los requisitos de un algoritmo V quien las séñ alo?
El cientí fico de computació r:l ponald Knuth, Cará cter finito, precisió n, entrada, salida y eficacia.

10) ¿ En que consist~ cará cter finito?
Un algoritmo siempre debe terminar despué s de un nú meró finito de paso".

11) ¿ En que cons¡ st~ precisió n?
Cada paso de un algoritmo debe estar precisamente definido; las operí ;lciones a llevar a cabo deben ser especificadas de manera rigurosa y no ambigua para cada caso.

12) ¿ En que consiste la entrada?
Un algoritmo tiene cero o má s entradas: cantidades que le son dadas antes de que el algoritmo comience, o diná micamente mientras el algoritmo corre. Estas entradas son tomadas de conjuntos especificas de objetos.

13) ¿ En qtí e consiste la salida?

Un algoritmo tiene una o má s salidas: cantidades que tienen una relació n especí fica con la entrada.

14) ¿ En que consiste la eficacia?

Tambié n se espera que un algoritmo sea eficaz, en el sentido de que todas las operaciones a realizar en un algoritmo deben ser suficientemente bá sicas como para que en principio puedan ser hechas de manera exacta y en un tiempo finito por un hombre usando lá piz y papel.

15) ¿ Qué calcula un al~oritmo?

Como cl,Jalquie~ conjunto finito es numerable, y cualquier conjunto numerable se puede expresar en té rminos del conjuntp de los nú meros naturales (infinito, pero numerable, de hecho no existe otro conjunto má s grande que sea tambié n numerable), en esencia, todo algoritmo calcula a funciones definidas en los nú meros naturales.
16) ¿ Có mo ~e les llama a las funciones que tengan un algoritmo?

Se denomina funció n computable (parcialmente computable o totalmente computable depenQe del grado de definiciQn de la funció n en cuestió n)

17) ¿ Cuá les son las funciones parcialmente computables?

Una funció n es parcial cuando hay nú meros naturales qqe n0 pertenecen a su dominio (es decir, hay nú meros naturales sobre los que no está definida la funció n), solo devolverá un resultado (es decir gasta un tiempo de cá lculo finito) para los valores en los que la funció n está definida, no devolviendp resultado (el tiempo de cá lculo es infinito) para el resto de valores.

18) ¿ Cuá les son las funciones totalmente computables?

Un algoritmo qlle calcula a una funció n total siempre devuelve un resultado para todo valor, y que al igual que las funciones parciales, é ste debe coincidir exactamente con el valor que devuelve la funció n a la que calcula; y reiterativan;tente, en caso 'contrario, no calcularí a a esa funtió n sino a otra. Así , todo algoritmo calcula a una funció n definida sobre los nú meros naturales, sea cuá l sea é sta su naturalé za.

19) ¿ Có mo pueden ser expresados l:es algoritmos?

Lenguaje natural, pseudocó digo, Diagramas de flujo y Lenguajes de programació n.

20) ¿ Cuá les son los niveles para hacer la descripció n de un algoritmo?
.

Descripció n de alto nivel, Descripció n formal, Implementació n.

21) ¿ En que consisten cada uno de los anteriores?

Descripció n de alto nivel. Se establece el problema, se selecciona un modelo matemá tico y se explica el algoritmo de manera verbal, posiblemente con ilustraciones y omitiendo detalles.

Descripció n' formal. Se ~sa pseudocó digo para describir la secuencia de pasos que encuentran la solució n.

Implementació n. Se m¡ .testra el algoritmo expresado en un lenguaje de programació n esp~cí f¡ co o algú n objeto capaz de llevar a cabo instrucciones.

22) ¿ q.ue es un qiagrarha de flujo?
Un diagrama de flujo es una representaCió n grá fica de un algoritmo o de una parte del mismo.

23) (Nombra I~~ sí mbolos del diagrama de flujo?
rerminal, proceso, decisió n, entrajsa1ida, conectar y lí nea de flujo.

24) ¿ Qué es el pSeudocó digo?
Pseudocó digo Es ú n lenguaje artificial e informal que ayuda a los programadores a desarrollar algoritmos.

25) ¿ Segú n su funció n cuales son los tipos de algoritmos?
Algoritmo de ordenamiento Algoritmo de bú squeda.

26) ¿ De qué se encarga el algoritmo de ordenamiento?
Es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relació n de orden.

27) ¿ Cuá les son í as relaciones de orden má s usadas?
Son el o¡ ;den numé rico y el orden lexicogr~fico.

28) ¿ De qué forma se pueden clasificar los algoritmos de ordenamiento?
La má s comú n es clasificar segú n el lugar donde se realice la ordenació n a. Algorittnos de oroenamiento interno: en la memoria del ordenador.
b. Algoritmos de ordenamiento externo: en un lugar externo como un disco duro.
Por el tiempo que tardan en realizar la ordenació n, dadas entradas ya ordenadas o inversamente ordenadas:
c. Algoritmos de ordenació n natural: Tarda lo mí nimo posible cuando la entrada está ordenada.
d. Algoritmos de ordenaciÓ n no natural: Tarda lo mí nimo posible cuando la entrada está inversa mente ordenada.
Por estabilidad: un ordenamiento est~ble mantiene el orden relativo que tení an originalmente los elementos con c;:laves iguales.

29) ¿ Clasificació n del algó .ritmo de ordenamiento?
Algoritmos de ordenamiento interno, Algoritmos de ordenamiento externo, A~goritmos de ordenació n natural, AI~oritmos de ordenació n no natural.

30) ¿ Qué es el algoritmo de bú squeda?
Es aquel que está diseñ ado para localizar un elemento concreto dentro Qe una estructura de datos.

31) Menciona alguna de las té cnicas de algoritmos Algoritmos voraces (greedy) Algoritmos paralelos Algoritmos probabilí sticos Algqritmos deterministico Algoritmos no deterministico
Divide y vencerá s Metaheurí sticas Programació n diná mica Ramificació n y acotació n Vuelta Atrá s (Backtracking)

32) ¿ Qué algoritmo se dice que tiene comportamiento lineal?
Algoritmo deterrninistico

33) ¿ Cuá l es la forma en que trabaja el algoritmo de Divide y Vencerá s?
Divide el problema en subconjuntos disjuntos obteni€ ndo una solució n de cada uno de ellos para despué s unirlas, logrando así la solució n al problema completo.

34) ¿ En que se basa el algoritmo de Ramificació n y acotació n?
Se basa en la construcció n de las soluciones al problema mediante un á rbol implí cito que se retorre de forma controlada encontrando las mejores soluciones.

35) ¿ Cuá ndo hablamos de seleccionar los elementos má s prometedores del conjunto de ~andi~atos hasta encontrar una solució n hablamos de?
Algoritmos voraces (greedy) .

36) ¿ los algoritmos de Met;;¡ heurí sticas nos hablan de?
Encontrar soluciones aproximadas (no ó ptimas) a problemas basá ndose en un conocimiento anterior (a veces llamado experiencia) de los mismos.

37) ¿ Cuá l es el algoritmo que intenta resolver problemas disminuyendo su coste computacional aumentando el coste espacial?

Programació n diná mica

38) ¿ Có mo calculan la medida de eficiencia de los algoritmos?
Se suelen estudiar los recursos (memoria y tiempo) que consume el algoritmo

39) ¿ Para qué se ha desarrollado el aná lisis de algoritmos?
El aná lisis de algoritmos se ha desarrollado para obtener valores que de alguna forma indiquen (o especifiquen) la evolució n del gasto de tiempo y memoria en funció n del tamañ o de los valores de entrada.

40) Menciona una forma de plasmar o codIficar un algoritmo Es escribitlo er¡ pseudocó digo o utilizar un lenguaje muy simple tal como Lé xico, cuyos có digos pueden estar en el idioma del programador.