Think logarithmically!

We discuss here a number of algorithmic topics which we use in our teaching and in learning of mathematics and informatics to illustrate and document the power of logarithm in designing very efficient algorithms and computations – logarithmic thinking is one of the most important key competencies for solving real world practical problems. We demonstrate also how to introduce logarithm independently of mathematical formalism using a conceptual model for reducing a problem size by at least half. It is quite surprising that the idea, which leads to logarithm, is present in Euclid’s algorithm described almost 2000 years before John Napier invented logarithm.

Metadaten
Verfasserangaben:	Maciej M. Sysło, Anna Beata Kwiatkowska
URN:	urn:nbn:de:kobv:517-opus4-82923
ISSN:	1868-0844
ISSN:	2191-1940
Titel des übergeordneten Werks (Englisch):	KEYCIT 2014 - Key Competencies in Informatics and ICT
Verlag:	Universitätsverlag Potsdam
Verlagsort:	Potsdam
Publikationstyp:	Wissenschaftlicher Artikel
Sprache:	Englisch
Erscheinungsjahr:	2015
Veröffentlichende Institution:	Universität Potsdam
Datum der Freischaltung:	27.10.2015
Freies Schlagwort / Tag:	Euclid’s algorithm; Fibonacci numbers; Logarithm; binary representation; binary search; complexity; divide and conquer; exponentiation
Ausgabe:	7
Erste Seite:	371
Letzte Seite:	380
Organisationseinheiten:	Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science
DDC-Klassifikation:	0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Publikationsweg:	Open Access
Sammlung(en):	Universität Potsdam / Schriftenreihen / Commentarii informaticae didacticae (CID) / CID (2015) 07
	Universität Potsdam / Schriftenreihen / Commentarii informaticae didacticae (CID) / CID (2015) 07 / Short Papers
Lizenz (Deutsch):	Creative Commons - Namensnennung, Nicht kommerziell, Keine Bearbeitung 3.0 Deutschland