Hispanopedia Wiki
Articulo de referencia

Algoritmo TPK

El algoritmo TPK es un programa sencillo creado por Donald Knuth y Luis Trabb Pardo para ilustrar la evolución de los lenguajes de programación . En su obra de 1977, "El desarro...

Hispanopedia WikiContenido en espanolLectura gratuita

El algoritmo TPK es un programa sencillo creado por Donald Knuth y Luis Trabb Pardo para ilustrar la evolución de los lenguajes de programación . En su obra de 1977, "El desarrollo temprano de los lenguajes de programación", Trabb Pardo y Knuth presentaron un pequeño programa que incluía arreglos , indexación, funciones matemáticas , subrutinas , entrada/salida , condicionales e iteración . Posteriormente, implementaron el algoritmo en varios lenguajes de programación primitivos para mostrar cómo se expresaban dichos conceptos.

Para explicar el nombre "TPK", los autores se refirieron a la ley de Grimm (que se refiere a las consonantes 't', 'p' y 'k'), los sonidos de la palabra "típico" y sus propias iniciales (Trabb Pardo y Knuth). [ 1 ] En una charla basada en el artículo, Knuth dijo: [ 2 ]

Solo se puede apreciar la profundidad del tema viendo cómo personas brillantes lo abordaron y cómo las ideas surgieron poco a poco. Para estudiarlo —creo que Luis fue el principal impulsor de esta idea— tomamos un programa —un algoritmo— y lo escribimos en todos los lenguajes de programación. De esta manera, a partir de un solo ejemplo, podemos captar rápidamente las características de cada lenguaje. A esto lo llamamos el programa TPK, y bueno, el hecho de que tenga las iniciales de Trabb Pardo y Knuth es solo una curiosa coincidencia.

El algoritmo

Knuth lo describe de la siguiente manera: [ 3 ]

Introdujimos un procedimiento simple llamado “algoritmo TPK” y le dimos el sabor a cada lenguaje expresando TPK en cada estilo particular. […] El algoritmo TPK recibe como entrada once números ; luego produce una secuencia de once pares dondea0,a1,…,a10{\displaystyle a_{0},a_{1},\ldots ,a_{10}}(10,b10),(9,b9),…,(0,b0),{\displaystyle (10,b_{10}),(9,b_{9}),\ldots ,(0,b_{0}),}

bi={F(ai),si F(ai)≤400;999,si F(ai)>400;F(incógnita)=|incógnita|+5incógnita3.{\displaystyle b_{i}={\begin{cases}f(a_{i}),&{\text{si }}f(a_{i})\leq 400;\\999,&{\text{si }}f(a_{i})>400;\end{cases}}\quad f(x)={\sqrt {|x|}}+5x^{3}.}

Esta sencilla tarea obviamente no supone un gran desafío en ningún lenguaje de programación decente.

En pseudocódigo:

Solicitar que se lean 11 números en una secuencia S, invertir la secuencia S, para cada elemento de la secuencia S llamar a una función para realizar una operación, si el resultado se desborda alertar al usuario, de lo contrario imprimir el resultado .

El algoritmo lee once números de un dispositivo de entrada, los almacena en una matriz y luego los procesa en orden inverso, aplicando una función definida por el usuario a cada valor e informando del valor de la función o de un mensaje que indique que el valor ha superado un determinado umbral.

Implementaciones

Implementaciones en el artículo original

En el artículo original, que cubría "aproximadamente la primera década" del desarrollo de los lenguajes de programación de alto nivel (desde 1945 hasta 1957), dieron el siguiente ejemplo de implementación "en un dialecto de ALGOL 60 ", señalando que ALGOL 60 fue un desarrollo posterior a los lenguajes que se discutían en el artículo: [ 1 ]

TPK : inicio entero i ; real y ; matriz real a [ 0 : 10 ] ;procedimiento real f ( t ) ; real t ; valor t ;f := sqrt ( abs ( t )) + 5 × t ↑ 3 ;para i := 0 paso 1 hasta 10 hacer leer ( a [ i ]) ;para i := 10 paso - 1 hasta 0 hacerbegin y := f ( a [ i ]) ;Si y > 400 , entonces escribe ( i , 'DEMASIADO GRANDE' )de lo contrario escribe ( i , y ) ;finfin TPK .

Como muchos de los primeros lenguajes de alto nivel no podían manejar el algoritmo TPK exactamente, permitían las siguientes modificaciones: [ 1 ]

  • Si el lenguaje solo admite variables enteras, entonces suponga que todas las entradas y salidas son de valor entero, y eso sqrt(x)significa que el entero más grande no excede .incógnita{\displaystyle {\sqrt {x}}}
  • Si el idioma no admite la salida alfabética, en lugar de la cadena 'TOO LARGE', muestre el número 999.
  • Si el lenguaje no permite ninguna entrada ni salida, entonces suponga que los 11 valores de entrada han sido proporcionados por un proceso externo de alguna manera, y la tarea es calcular los 22 valores de salida (con 999 reemplazando valores demasiado grandes de ).a0,a1,…,a10{\displaystyle a_{0},a_{1},\ldots ,a_{10}}10,F(10),9,F(9),…,0,F(0){\displaystyle 10,f(10),9,f(9),\ldots ,0,f(0)}F(i){\displaystyle f(i)}
  • Si el lenguaje no permite a los programadores definir sus propias funciones, entonces reemplácelo f(a[i])con una expresión equivalente a .|ai|+5ai3{\displaystyle {\sqrt {|a_{i}|}}+5a_{i}^{3}}

Con estas modificaciones cuando sea necesario, los autores implementan este algoritmo en Plankalkül de Konrad Zuse , en los diagramas de flujo de Goldstine y von Neumann , en la notación propuesta por Haskell Curry , en Short Code de John Mauchly y otros, en el Intermediate Program Language de Arthur Burks , en la notación de Heinz Rutishauser , en el lenguaje y compilador de Corrado Böhm en 1951-52, en Autocode de Alick Glennie , en el sistema A-2 de Grace Hopper , en el sistema de Laning y Zierler , en el primer Fortran propuesto (1954) de John Backus , en el Autocode para Mark 1 de Tony Brooker , en ПП-2 de Andrey Ershov , en BACAIC de Mandalay Grems y RE Porter, en Kompiler 2 de A. Kenton Elsworth y otros, en ADES de EK Blum, el Internal Translator de Alan Perlis , en Fortran de John Backus, en ARITH-MATIC y MATH-MATIC del laboratorio de Grace Hopper , en el sistema de Bauer y Samelson , y (en adiciones de 2003 y 2009) PACT I y TRANSCODE. Luego describen qué tipo de aritmética estaba disponible y proporcionan una calificación subjetiva de estos lenguajes en parámetros de "implementación", "legibilidad", "estructuras de control", "estructuras de datos", "independencia de la máquina" e "impacto", además de mencionar en qué fue el primero cada uno. [ 1 ]

Implementaciones en lenguajes más recientes

Implementación en C

Esto muestra una implementación en C equivalente al ALGOL 60 mencionado anteriormente.

#include <math.h>#include <stdio.h>doble f ( doble t ){devolver sqrt ( fabs ( t )) + 5 * pow ( t , 3 );}int principal ( void ){doble a [ 11 ] = { 0 }, y ;para ( int i = 0 ; i < 11 ; i ++ )scanf ( "%lf" , &a a [ i ]);para ( int i = 10 ; i >= 0 ; i -- ) {y = f ( a [ i ]);si ( y > 400 )printf ( "%d DEMASIADO GRANDE \n " , i );demásprintf ( "%d %.16g \n " , i , y );}}

Implementación en Python

Esto muestra una implementación en Python.

from math import sqrtdef f ( t ):devolver raíz cuadrada ( abs ( t )) + 5 * t ** 3a = [ float ( input ()) for _ in range ( 11 )]para i , t en reversed ( lista ( enumerar ( a ))):y = f ( t )imprimir ( i , "DEMASIADO GRANDE" si y > 400 sino y )

Implementación en Java

Esto muestra una implementación en Java.

import java.util.Arrays ;import java.util.ArrayList ;import java.util.Collections ;import java.util.List ;import java.util.Scanner ;clase pública TPKAlgorithm {// Función definida por el usuarioprivado estático doble f ( doble x ) {return Math.sqrt ( Math.abs ( x ) ) + 5 * Math.pow ( x , 3 ) ;​​​​}public static void main ( String [] args ) {// Crea un objeto Scanner para la entrada del usuarioScanner scanner = new Scanner ( System . in );// Crea un ArrayList para almacenar los números de entradaLista < Double > inputNumbers = new ArrayList <> ();System.out.println ( " Ingrese once números : " ) ;entero número de entrada ;// Obtener 11 números de la entrada del usuariopara ( int i = 1 ; i <= 11 ; i ++ ) {si ( escáner . hasNextDouble ()) {inputNumber = scanner.nextDouble ( ) ;números de entrada . agregar ( número de entrada );}}escáner.cerrar ( ) ;// Lógica del algoritmoColecciones.reverse ( inputNumbers ) ;​para ( int n = 0 ; n < inputNumbers . size (); n ++ ) {int i = inputNumbers.size ( ) - ( n + 1 ) ;double y = f ( inputNumbers . get ( n ));si ( y > 400 ) {System.out.printf ( " % d DEMASIADO GRANDE%n " , i ) ;} demás {System.out.printf ( " % d %.2f%n " , i , y ) ;}}}}

Implementación en Rust

Esto muestra una implementación en Rust.

usar std ::{ io , iter };fn f ( t : f64 ) -> Opción < f64 > {sea ​​y = t . abdominales (). raíz cuadrada () + 5,0 * t . powi ( 3 );( y <= 400.0 ). then_some ( y )}fn main () {sea ​​mut a = [ 0 f64 ; 11 ];para ( t , entrada ) en iter :: zip ( & mut a , io :: stdin (). líneas ()) {* t = input . unwrap (). parse (). unwrap ();}a . iter (). enumerate (). rev (). for_each ( | ( i , & t ) | match f ( t ) {Ninguno => println! ( "{i} DEMASIADO GRANDE" ),Algunos ( y ) => println! ( "{i} {y}" ),});}

Referencias

  1. 1 2 3 4 Luis Trabb Pardo y Donald E. Knuth, "El desarrollo temprano de los lenguajes de programación".
    • Publicado por primera vez en agosto de 1976 en forma de borrador mecanografiado, como Informe de Ciencias de la Computación de Stanford STAN-CS-76-562.
    • Publicado en Encyclopedia of Computer Science and Technology , editado por Jack Belzer, Albert G. Holzman y Allen Kent , vol. 6, págs. 419-493. Dekker, Nueva York, 1977.
    • Reimpreso ( doi : 10.1016/B978-0-12-491650-0.50019-8 ) en A History of Computing in the Twentieth Century , N. Metropolis , J. Howlett y G.-C. Rota (eds.), Nueva York, Academic Press, 1980. ISBN 0-12-491650-3
    • Reimpreso con modificaciones como Capítulo 1 de Selected Papers on Computer Languages , Donald Knuth, Stanford, CA, CSLI, 2003. ISBN 1-57586-382-0)
  2. ↑ "Una docena de precursores de Fortran", conferencia de Donald Knuth, 3 de diciembre de 2003 en el Museo de Historia de la Computación : Resumen , vídeo
  3. ↑ Donald Knuth, TPK en INTERCAL , Capítulo 7 de Artículos seleccionados sobre diversión y juegos , 2011 (pág. 41)
Obtenido de " https://en.wikipedia.org/w/index.php?title=TPK_algorithm&oldid=1345817750 "
Lecturas relacionadas
6 articulos
Programa de computadoraPrograma de computadoraUn programa informático es una secuencia o conjunto de instrucciones en un lenguaje de programación que un ordenador debe ejecutar . Es un componen...Donald KnuthDonald KnuthDonald Ervin Knuth ( nacido el 10 de enero de 1938) es un informático y matemático estadounidense. Es profesor emérito de la Universidad de Stanfor...Lenguaje de programaciónLenguaje de programaciónEl código fuente de un programa informático en C. Las líneas grises son comentarios que explican el programa a los humanos. Cuando se compila y se ...Array (data structure)In computer science , an array is a data structure consisting of a collection of elements ( values or variables ), of same memory size, each identi...{\displaystyle f(x)=x^{2}+1;}Function (mathematics)In mathematics, a function from a set X to a set Y assigns to each element of X exactly one element of Y.[1] The set X is called the domain of the ...Función (programación informática)Función (programación informática)En programación informática , una función (también procedimiento , método , subrutina , rutina o subprograma ) es una unidad invocable [1] de lógic...