Algoritmos y estructura de datos



Conceptos fundamentales


Introducción:

La principal razón para aprender a programar es utilizar la computadora como una herramienta para resolver problemas. Sin embargo no es suficiente con aprender las reglas de un lenguaje de programación para escribir programas, también es necesario hallar la solución del problema independientemente del uso de las computadoras y de los lenguajes de programación. La solución a los problemas esta dada por un algoritmo.
Asi, los algoritmos, junto a las estructuras de datos, constituyen la solución de los problemas.
El termino algoritmo se estableció en honor a Muhammad ibnMusa al-Jwarizmi, matemático árabe del siglo IX quien propuso que la solución de muchos problemas se puede obtener con un conjunto de soluciones menores.

Algoritmos y Estructura de datos. Conceptos fundamentales I

1. Procesamiento Automatizado De Información

Los actuales sistemas de información están basados en el uso de computadoras. Estas, son maquinas digitales (sincrónicas de múltiples propósitos) que ejecutan conjuntos o secuencias de operaciones matemáticas y lógicas, utilizando el sistema binario de numeración.

gol

Son herramientas poderosas para la automatización de la resolución de problemas, pero ello depende de la capacidad de su programa. Generalmente a los sistemas de procesamiento automatizado de información, los llamamos sistemas de información.
Así, los sistemas de información son un conjunto de elementos relacionados que actúan como un todo, cuyo objetivo es la obtención de información y está compuesto por elementos de hardware y software.
El hardware es el conjunto de componentes físicos que componen al sistema.
El software es un conjunto de componentes lógicos que controlan el funcionamiento del hardware y otorgan a las computadoras la capacidad de ser maquinas con múltiples propósitos.


Esto significa que para dotar a la maquina la capacidad de resolver múltiples problemas, es necesario escribir un programa (software) que los solucione de forma específica. Para ello existen pasos previos como ser:

Definición del problema del mundo real;

Análisis del problema;

Diseño de la solución;

Diseño de la solución informática.

a. Definición del problema.

Definir el problema significa comprenderlo, circunscribirlo, acotarlo (es imposible que hallemos una solución sino sabemos cuál es el problema).
El proceso de analizar el mundo real para interpretar los aspectos esenciales de un problema y expresarlo en términos precisos se llama abstracción.

ingenieria

b. Análisis del problema.

Una vez que se definió el problema hay que analizarlo. Se busca determinar claramente el contexto (entorno) del problema y describir el estado futuro deseado una vez que se soluciono el problema.
Se debe determinar qué datos son necesarios para solucionar el problema y que información debe proporcionar la solución.

dulce de leche

c. Solución del problema.

La solución de todo problema lo constituye un algoritmo. Un algoritmo es un conjunto ordenado de pasos que conducen a la solución de un problema.

algoritmos

d. Solución informática.

El algoritmo es la solución general sin tener en cuenta un lenguaje de programación ni una maquina en especial. Cuando un algoritmo se define en términos de un lenguaje de programación específico para una maquina específica, estamos en presencia de un programa. Este constituye la solución informática de un problema.
La diferencia entre algoritmo y programa radica en el hecho de que los algoritmos se especifican en términos “ideales”; mientras que los programas se especifican bajo las limitaciones impuestas por lenguajes de programación y maquinas particulares.

no se

2. Concepto de algoritmo.

La solución de un problema exige el diseño del algoritmo. Un algoritmo es la especificación de la secuencia ordenada de pasos a realizar para solucionar un problema en un tiempo finito.
Está vinculado a una maquina abstracta. Por lo tanto, los algoritmos son independientes de los lenguajes de programación y de las maquinas en las que se lo ejecutara.
Está constituido por un conjunto de acciones. Una acción es un hecho o acontecimiento que sucede en un periodo de tiempo finito, es llevado a cabo por un ejecutante y tiene un objetivo. La unión de varias acciones organizadas que se ejecutan en un tiempo finito se denomina proceso. Tanto los procesos como las acciones son componentes de los algoritmos.

sexy

a. Características de los algoritmos.

Todo algoritmo debe cumplir con tres características:

Debe ser preciso. No debe existir acción alguna que presente ambigüedades en cuanto a su estado previo y su estado posterior.

Debe estar definido. Si todas sus acciones son precisas y se sigue dos veces el mismo algoritmo con los mismos datos, se debe obtener el mismo resultado cada vez.

Debe ser finito. Los resultados de la ejecución de un algoritmo se deben obtener en un tiempo finito. Todo algoritmo debe tener un inicio y un fin.

b. Diseño de algoritmos.

En primer término, es necesario definir y analizar el problema a resolver. Una buena comprensión del problema, mas la descripción detallada de entradas (datos necesarios) y salidas requerida (datos requeridos del proceso) son los requisitos más importantes para hallar una solución del problema. Los datos proporcionados al algoritmo constituyen su entrada y los datos producidos por el su salida.
Una buena estrategia para resolver problemas complejos es descomponer al problema en varios problemas menores más fáciles de solucionar. La descomposición del problema en otros más simples y así sucesivamente hasta hallar una solución a ellos, esto se denomina diseño descendente (top-down design).

o.o

Las principales ventajas del diseño descendente son:

El problema se comprende más fácilmente al dividirse en partes mas simples denominadas módulos,

Las modificaciones en módulos son mas fáciles;

La comprobación del problema se puede verificar fácilmente.

c. Representación e algoritmos.

La elección depende del uso futuro, del objetivo y la experiencia de quien lo escriba. Entre las alternativas se pueden encontrar:

Diagrama de flujo;
Diagrama N-S (Nassi-Scheiderman);
Lenguaje natural humano;
Pseudocódigo;
Formulas;
Lenguajes de programación.

Si bien los diagramas son mas cómodos para los inexpertos, es verdaderamente mas difícil codificarlo luego a un lenguaje de programación, ya que los diagramas no tienen en cuenta las limitaciones de los lenguajes de programación.

d. Diagrama de flujo.

Un diagrama de flujo es un diagrama basado en un conjunto de símbolos gráficos que muestran la secuencia de pasos del algoritmo a través de flechas denominadas líneas de flujo.

Algunos de los principales símbolos son:

Algoritmos y Estructura de datos. Conceptos fundamentales I

e. Diagrama Naassi-Scheiderman.

Estos diagramas omiten el uso de flechas de unión y los símbolos se utilizan en forma continua. Las acciones sucesivas se simbolizan en cajas contiguas.la dificultad en el uso de estos diagramas está en que ocupan mucho lugar en forma horizontal cuando varias estructuras se anidan una dentro de otra.

gol


f. Lenguaje natural.

Puede ser muy útil para una escritura inicial. Posee muchas limitaciones para la escritura de algoritmos que luego serán programados, ya que las estructuras de los lenguajes humanos son muy distintas a las de los lenguajes de programación.

g. Pseudocódigo.

Es una alternativa intermedia entre los lenguajes naturales y los lenguajes de programación. Involucra un conjunto limitado de palabras, las reglas de utilización y unas pocas limitaciones similares a las de los lenguajes de programación, sin llegar a la escritura de programas. Con el pseudocódigo, el programador centra su atención en la lógica y la secuencia de las acciones sin la preocupación por las reglas propias de un lenguaje de programación particular.

ingenieria

h. Formulas.

Una formula es una combinación de valores y símbolos, como por ejemplo una ecuación aritmética. Para ciertos tipos de problemas, las formulas suelen ser la alternativa más valida.

i. Lenguaje de programación.

Una alternativa valida es escribir directamente la solución utilizando un lenguaje de programación. tiene la limitación de no poder utilizar el total del potencial de un algoritmo, ya que los lenguajes de programación tiene reglas que limitan la creatividad de la solución.

dulce de leche

3. Lenguajes de programación.

Un lenguaje es un sistema de comunicación compuesto por un vocabulario y una gramática . todo lenguaje esta compuesto por un conjunto de símbolos y un conjunto de reglas que indican como ha de utilizarse el conjunto de símbolos (sintaxis) para dar un significado (semántico). Los lenguajes de programación respetan este concepto.

Un lenguaje de programación, es un conjunto de instrucciones y símbolos definido por reglas sintácticas y semánticas, para la escritura de programas de computadoras.

Existen tres tipos de lenguajes de programación:

Lenguaje de maquina.

algoritmos

Lenguaje cuyas instrucciones son "entendibles" directamente por la maquina. Sus instrucciones y símbolos son secuencias de 0 y 1 (lenguaje binario). Por cada instrucción que puede ejecutar la maquina, existe una cadena binaria que la representa . Cada instrucción almacenada en memoria hace referencia a una dirección de memoria, una operación ejecutable por el procesador y la dirección de memoria donde se encuentran los datos con los cuales ha de hacerse la operación. Son lenguajes que dependen del hardware de la maquina, es decir, dos maquinas distintas tienen lenguajes de maquina distintos.

Existen varios inconvenientes para su utilización, entre ellos:

-Es muy difícil y lento escribir un programa en lenguaje de maquina.

-Es muy difícil depurar (probar y corregir) y realizar modificaciones al programa.

-Los programas se escriben para un procesador especifico (hardware especifico).

Lenguaje de bajo nivel.

no se

El lenguaje de bajo nivel por excelencia es el Assembler. Un programa escrito en este lenguaje requiere un proceso de traducción a su equivalente el lenguaje de bajo nivel.

Al igual que los lenguajes de bajo nivel, dependen de la maquina particular. Esto significa que, un programa escrito en Assembler solo podrá ejecutarse en la maquina para la cual se escribió el programa. Cada tipo de maquina tiene su propio lenguaje Assembler.

Lenguaje de alto nivel.

sexy

Son los lenguajes que se utilizan en la actualidad. Estan diseñados para que sean interpretados por las personas. En algunos aspectos, se asemejan al habla natural.

Un programa escrito en un lenguaje de alto nivel requiere de un proceso de traduccion al lenguaje de bajo nivel, ya que estos programas n son interpretados por las maquinas. A los programas de alto nivel se los llama programa fuente.

Tiene la ventaja de ser mas simples de aprender y utilizar por los programadores y no dependen de una maquina particular. esta ultima caracteristica permite que un programa escrito en lenguaje de alto nivel en una maquina particualr se pueda transportar a maquinas de caracteristicas distintas de aquellas para la cual se escribio originamente.

Son ejemplos de estos lenguajes el BASIC, Cobol, Fortran, Pascal, C.

a. Programas traductores.

Son programas cuyo objetivo es traducir programas escritos en lenguaje de alto nivel a su equivalente en lenguaje maquina. Existen dos tipos de traductores: interpretes y compiladores.

Un interprete es un traductor que toma un programa fuente, lo traduce a lenguaje maquina línea a línea y a continuación lo ejecuta. No deja almacenado el resultado de la traducción. En la actualidad prácticamente no se utiliza.

Un compilador es un traductor que toma un programa fuente, lo traduce y genera un equivalente en lenguaje de maquina (programa objeto).

b. Concepto de programa.

Un programa de computadora es un conjunto de instrucciones para realizar una tarea en una maquina particular. En esencia, un programa es la transcripción de un algoritmo en un lenguaje de programación para ser ejecutado en una maquina particular.

A diferencia de los algoritmos, los programas se escriben en términos de un lenguaje particular para una maquina particular. Constituyen la solución informática de un problema.

c. Técnica de programación.

Son diversas las técnicas de programación. Estas varían de acuerdo al paradigma de programación utilizado. En este material se presentara la programación
estructurada yla programación modular correspondientes al paradigma imperativo.

El termino programación estructurada se refiere a un conjunto de técnicas que han ido evolucionando desde los primeros trabajos de Edgar Dijkstra. Se basa en el uso de recursos abstractos, diseño descendente y numero limitado de estructuras de control que minimizan la complejidad de los programas y por, consiguiente, reducen los errores; hacen los programas mas fáciles de escribir, verificar, leer y mantener. Los programas deben estar dotados de una estructura.

o.o

La programación modular consiste en dividir al programa en módulos, cada uno de los cuales ejecuta una tarea especifica y se codifica de forma independiente de los demás. Cada programa desarrollado con esta técnica contiene un modulo denominado programa principal desde el que se controla a los demás módulos.







Bueno espero que les sirva esta pequeña introducción al mundo de la programación.

La fuente no la tengo ya que son apuntes de la facultad... pero si quieren y piden les dejo la pagina de la facu... que de todas formas no pueden ver los apuntes si no están matriculados.

Saludos a todos de parte de LittleS