Seminario Nacional XLIV Jornadas de Resolución de Problemas La Falda - Sierras de Córdoba, 6 al 8 de Noviembre de 2018

Seminario:

Algoritmos de aritmética elemental

Dr. Néstor E. AGUILERA

• Descripción:
  
  

  Entre las muchas y lindas publicaciones de la OMA se encuentra una joya de E. Gentile: Aritmética elemental en la formación matemática. Los temas abordados por ese libro han adquirido importancia práctica en años recientes debido a que gran parte de la seguridad de internet depende de algoritmos basados en las propiedades de divisibilidad de enteros. Basándonos en el libro de Gentile, en este curso veremos algunos algoritmos computacionales sencillos, integrando la teoría y la práctica, incluyendo versiones básicas de algunas aplicaciones en  criptogafía. ¿Por qué la computadora? Además de la actualidad práctica de los temas particulares que veremos, me gustaría destacar dos razones válidas en todos los casos: El pensamiento algorítmico es parte del pensamiento matemático. Desde ya, la criba de Eratóstenes o la construcción del máximo divisor común de Euclides se encuentran entre los primeros algoritmos que recuerda la historia. Fuera del ámbito numérico, la geometría clásica nos habla de construcciones con regla y compás, que no son sino algoritmos para «fabricar» algún objeto. Más aún, gran parte de las demostraciones de teoremas apelan a construcciones, más concretas o más abstractas. Por ejemplo, una de las demostraciones más bellas de la matemática es la dada por Euclides de la existencia  de infinitos primos: si p1,..., pn son primos, «fabricamos» el producto y le sumamos 1, resulta que debe haber otro primo pues ninguno de p1,..., pn divide a p1×···× pn+ 1. La matemática experimental. La tecnología nos ha brindado herramientas cada vez más poderosas, haciéndonos olvidar muchas herramientas que se usaban antes. Pasó con la calculadora, que nos hizo olvidar de las tablas de logaritmos o las reglas de cálculo, y pasó con las aplicaciones de geometría dinámica, que superaron ampliamente la regla y el compás permitiéndonos ver cómo varían los objetos cuando se cambian algunos  parámetros. El desarrollo y programación de algoritmos nos ayuda a entender más profundamente las ideas involucradas, hacer cálculos complicados o tediosos, y experimentar variando parámetros buscando patrones y realizando conjeturas. En la parte computacional tendremos como guía  — algo lejana — al libro de T. Cormen, C. Leiserson, R. Rivest y C. Stein, Introduction to Algorithms (3ra. ed., MIT Press, 2009). Para una versión más profunda de la teoría se puede consultar el libro de I. Niven, H. Zuckerman y H. Montgomery, An Introduction to the Theory of Numbers (5ta. ed., J. Wiley & Sons, 1991). Usaremos el lenguaje Python (haciendo una introducción previa), tratando de usar estructuras disponibles en la mayoría de los lenguajes de programación. Recomendamos a todos los participantes traer computadora, tableta o celular con alguna aplicación ya instalada que permita trabajar con la versión 3 (idealmente 3.6 o 3.7) de ese lenguaje. La presentación del curso se hará usando el editor IDLE que viene incorporado en la versión disponible en https://www.python.org/downloads/. Esta versión puede usarse en casi cualquier sistema operativo de computadoras (notebooks, netbooks) como Windows, Linux o MacOS. Hay muchas posibilidades para tabletas o celulares (algunas comerciales), y en este caso pedimos que antes del curso cada participante se familiarice con el uso de la implementación que haya obtenido, verificando que puede ejecutar instrucciones sencillas como print ("Hola mundo"). Contenidos tentativos Los siguientes son contenidos tentativos del curso. Lo que veamos finalmente dependerá de los intereses de los participantes y las facilidades computacionales disponibles. Los enteros, principio de buena ordenación, inducción, el algoritmo de la división. Usando Python con números enteros y decimales, operaciones, sucesiones, instrucciones if, while, for, print, return. La regla de Horner, cambio de base, cálculo de potencias y módulos. Versiones sencillas de factorización y primalidad, complejidad de algoritmos. Criba  de Eratóstenes. Raíces de ecuaciones: bisección, el algoritmo babilónico (Newton) para la raíz cuadrada, otras potencias. Máximo divisor común, identidad de Bézout, algoritmo de Euclides para enteros y decimales (inconmensurabilidad) y su complejidad (números de Fibonacci). Euclides extendido (Bézout constructivo). Ecuaciones diofánticas lineales, ecuaciones en congruencias, teorema chino del resto. El «pequeño» teorema de Fermat y la extensión de Euler (la función φ). Números de Carmichael. El algorimo RSA. Fracciones continuas, irracionales cuadráticos.

 

Programa:

 El Seminario se desarrollará los días martes, miércoles y jueves, el martes de 15 a 18 hs y el resto de los días de 9 a 12hs. y de 15 a 18 hs.

Acreditación: martes 6 a partir de las 14 hs. 

            Para mayor información, dirigirse al departamento de educación, al correo swelch@oma.org.ar o a norma@oma.org.ar

            Ficha de Inscripción

Seminarios y jornadas Página Principal	Olimpíada Matemática Argentina    www.oma.org.ar | info@oma.org.ar
mensajes webmaster@oma.org.ar