A short Introduction to Algorithm Engineering CSSS2009

Algorithm Engineering

Erwin P. Stoschek

erwins@

A short introduction to Algorithm

Engineering

Talks for students of the CQU College of Computer Science

Disclaimer

The teaching material in this folder is only intended to use in the

abovementioned talks “A short introduction to Algorithm

Engineering”

Algorithm is

a well-defined structured procedure

- to solve a problem class in a finite number of steps,

- to describe a class of time-discrete terminating processes

exactly or in sufficient approximation.

Algorithm Engineering is

- part of the human problem solving technologies in all sciences

and engineering, but also in the daily life,

- mathematics and logic based, computer (processor and implementation, today and tomorrow) oriented algorithm design in the run up to software engineering (application and system

software),

- computer oriented design of correct, efficient, robust,

modular, extensible, (at least in parts) reusable algorithms

- taking the simplest, shortest way (simple, but hard to achieve),

- using the most suitable tools (problem – tool resonance,

creative and efficient formula manipulation is an important part of algorithm design, of all mathematics based problem solving methods),

Algorithm Engineering

- saving brain power,

- with the goal to provide so the basis for efficient, low-cost

and high-quality software,

more general: for successful high-tech, high-performance, high-

powered, high-quality but low-cost industrial products, esp. in

the high-tech and in IT field.

Simpler expressed: how to solve problems in sciences and

engineering mathematics based and computing oriented step by

step in the simplest and most efficient way (scoutics)? That means

also, creativity plays a great role:

- “Ability to produce something new through imaginative skill,

whether a new solution to a problem, a new method or device, or a new artistic object or form.”

(Britannica)

- “Creativity, it has been said, consists largely of re-arranging

what we know in order to find out what we do not know.”

(George Kneller)

The design of algorithms practices and challenges strategic,

tactical, flexible, networked, synergetic-oriented, and dialectic

thinking in general as well as all problem-solving skills.

Mission statement

The intension for the planned talks on Algorithm Engineering

for students of the CQU College of Computer Science is not to

give the (n+1)th textbook or reference book on algorithms.

My plan is

● to present you some highlights (in my opinion) from my own

teaching and research work in this field and

● to discuss through them some basic principles, approaches, and methods of engineering-oriented design of algorithms down to the smallest details, to the grassroots;

Algorithm Engineering

● to put up for discussion some interesting unsolved and open

problems as well as some Algorithm Engineering born or based application ideas in the area of engineering and business (no

turnkey solutions, but promising grid positions);

● to show: algorithm-oriented thinking is an essential part of all

engineering and natural sciences.

Outline

1* More about Algorithm, Algorithm Engineering, etc.

2* Creative and efficient formula manipulation is an important part of algorithm design, of all mathematics based problem solving

methods. Necessary algorithmic finger exercises. Examples

3* A problem-oriented 2D/3D notation system (2D shortened

determinant, 3D data cylinder) for applications in

computational geometry.

The “problem – tool resonance” is a central issue for a

successful systematic extension strategy of a promising initial

solution.

Computational geometry: description, calculation and

computer-aided handling of geometric objects using the tools of algebra, calculus and algorithm engineering; application fields:

computer-aided design, pattern and image generation and

processing (transformation, manipulation, encoding, evaluation, recognition, etc).

4* The extended Differential Calculus quotient rule, applications

and beyond

5* The algorithm system Signa in silico®(AsSis), mimicking

aspects of biological gene expression, generates a broad variety

of computer graphics. The achievable pattern diversity is in

many respect comparable with the biodiversity.

Application fields of AsSis include

* computer graphics per se

* computer-based design of decors for wallpapers, textiles,

Algorithm Engineering

ceramics, etc., book and advertisement graphics

* styling ideas for technical products

and beyond:

* data mining

* efficient approximate solution of engineering relevant field

equations :

generation of 2D and 3D electromagnetic field patterns (esp.

“metamaterials – negative refraction index – electromagnetic

field invisibility”), aerodynamic and hydrodynamic field

patterns (water waves stealth oil platforms?), gravitational

field patterns)

* AsSis pattern controlled and displayed modulation of

electric and magnetic fields for manipulation of biomolecules

and biomolecular processes (food, beverage and drug

treatment, selection and breeding).

Structure generation algorithms like AsSis build a bridge

between science, arts, and technology - between abstract,

beautiful, and useful.

6* Some Algorithm Engineering born or based

application ideas in the area of engineering and business (no

turnkey solutions, but promising grid positions).

An offer for the winter semester 2009/2010.

6.1* Niche application of artificial neural net algorithms for

special prediction problems.

A neural network success story? A hot potato!

UK Epagogix Ltd. presented via a The New Yorker interview 2006 a neural network prediction system for the movie box-

office success of a screenplay.

A breakthrough in this field or a lucky goal or …?

But Epagogix has successors:

Algorithm Engineering

Critical discussion!!

6.2* Noise in physical, technical, biological, social, economic,

and computational systems and processes is often

considered as suppressible and removable “rubbish”. But this noise contains more useful information about them then

normally assumed.

However, the main difficulty consists of the extraction (with a single sensor or a sensor array), decoding, processing, and

displaying of this information, it is essentially a data mining

problem, an algorithmic problem, their solutions are a basis

for the design of a smart analysis software tool covering many types of noise, f.e. specialized on early diagnosis of small

changes (as early symptoms for damages, defective functions,

diseases, etc.) in systems and processes (esp. objects exposed

to extreme load) in comparision with their normal state,

normal dynamics etc.

The analysis of the noise generated by physical, technical, biological, economic, social, algorithmic etc. systems with

suitable algorithmic tools provides important information

about state, dynamics, and structure of these systems.

6.3* Advanced Samadhi (Floating, Isolation) tank technology

for highest and outstanding demands in the fields of

* relaxation, stress alleviation, medical applications

* enhancement of creativity and problem solving ability.

. Single tank design, coupled tank design (biofeedback,

resonance effects, brainstorming, ring of creativity power, ). Samadhi tanks of good and very good quality and standard features (relaxation, stress alleviation, etc.) are worldwide on the market. You can find them in private houses and fitness centers. The gap and the need in the international market lies in the upper price and outstanding demand range (relaxation+ stress alleviation + enhancement of creativity and problem solving ability) basing on the newest scientific knowledge and professionally equipped with the newest custom software and

Algorithm Engineering

high-tech electronics. A science, innovation, high-quality and export oriented engineering project, involving bioengineering, Algorithm Engineering, computer science and information technology, but also a hot potato! The potential clientele for such “Rolls Royce” versions are tycoons, top manager,

businessmen, scientists, artists, writers, adventurer.

References

- /Samadhi%20Tank

- /Isolation%20Tank

- /wiki/Isolation_tank

-

- http://www.floatation-tanks.co.uk

- /float.htm

- /cs/floatationtankfl/index.htm

- S. Zweifel. John C. Lilly. Rausch der Tiefe. http://www.spiegel.de/wissenschaft/mensch/0,1518,422301,00.html

- J.C. Lilly, E.J. Gold. Tanks for the Memories: Floatation

Tank Talks. Gateway Books and Tapes 2000

- M. Hutchison. The Book of Floating: Exploring the Private

Sea. Gateway Books and Tapes 2003

Warm water (shower, bathtub, Samadhi tank, thermal spring, warm rain) is an efficient catalyst for creativity!

Brainstorming in a thermal spring basin!

Water: * place of origin and catalyst of life

* information memory substrate?

6.4* Quantum computing, quantum IT, etc.

A dream or a future basic technology?

An attempt of a state-of-the-art and a look into the future

* Physical background

* Basic ideas

* First realizations, research groups worldwide

* QC algorithms and algorithm design

* Quantum information transmission

* Quantum computers are able to break many of the

cryptocodes in use today (f.e. public key ciphers) via

Algorithm Engineering

semiprime factoring.

* Using quantum phenomena one can implement new safe

communication systems which can always detect

eavesdropping.

* Interaction between information transmission, processing,

and storing in classical integrated semiconductor circuits

(in classical computers, automatic control, etc.) and

quantum information processes (hardware and algorithms)

is currently nearly terra incognita!

* Quantum viruses and trojans! in classical integrated

semiconductor circuits – an IT nightmare!

* Quantum energetics

- Biological photosynthesis – high efficient energy

conversion basing on quantum effects

- Vacuum energy transport?, the Hotta approach.

* Supraluminar or not – this is the question.

6.5* * Top engineering is

find new ways,

go new ways nobody has gone them before,

adventure, challenge, risk.

* The feasible

- has ever been made,

- is always made,

- and will always be made, too.

* “Turning yesterday’s science fiction into tomorrows

reality.” http://www.mse.gatech.edu

6.6* More

Algorithm Engineering

1* More about Algorithm, Algorithm Engineering, etc.

Deterministic Algorithm

Intuitive definition

Well-defined, detailed, unambiguous, and without any creative skills by machine processor executable procedure

for solving a solvable problem class or for approximating a

solution of this problem class

step by step,

consisting of a finite sequence of statements (instructions),

to be performed in a well-established, terminating order

regarding a control structure consisting of three elementary

building blocks (tripod)

- sequence

- selection

- loop (repetition)

that transforms an input sequence (instance of the problem)

in a finite sequence of steps

into an output or an output sequence

(algorithmic process).

The design of this procedure is determined by the

implementation technology (sequential, sequential-parallel,

distributed, parallel, .. processing).

The representation of an algorithm requires a formal notation

system (natural languages, graphic systems, mathematical

notations, structograms, pseudocodes, programming

languages, ..).

An algorithm must be noticable as a finite text in such a

notation system.

Features of a “good” algorithm:

Algorithm Engineering

- correct

The algorithm halts for every arranged input instance with the

correct (and accurate) output. It gives for the same input

instance always the same output.

- efficient

The algorithm terminates for every arranged input instance

with a minimal consumption of processor resources

(computational time, memory capacity, communication

bandwidth,..).

- modular, robust, extensible, particularly reusable.

Short:

Well-defined structured procedure to solve a problem class in a

finite number of steps.

With the addition of nondeterministic, probabilistic, evolution quantum-theoretical, .. elements into the algorithm design

toolbox we obtain the possibility to design nondeterministic

algorithms with gradually or completely higher capability and

efficiency: probabilistic, heuristic, genetic, quantum, ..

algorithms.

you can find a collection of intuitive definitions of algorithm from the leading

international encyclopediae.

Algorithm Engineering is

part of the human problem solving technologies in sciences,

engineering, but also in the daily life

The French philosopher and mathematician Rene Descartes

published

in 1637 a fundamental treatise about this subject, the “ Discourse

on the Method of Rightly Conducting the Reason in the Search for Truth in the Sciences”. It is one of the most influential works in the European history of sciences. It is a method which gives a solid

Algorithm Engineering

platform from which all modern natural sciences could evolve.

Descartes started his line of reasoning by doubting everything:

- “The first was never to accept anything for true which I did not

clearly know to be such; that is to say, carefully to avoid

precipitancy and prejudice, and to comprise nothing more in my judgement than what was presented to my mind so clearly and

distinctly as to exclude all ground of doubt.

- The second, to divide each of the difficulties under examination into as many parts as possible, and as might be necessary for its adequate solution.

- The third, to conduct my thoughts in such order that, by

commencing with objects the simplest and easiest to know, I

might ascend by little and little, and, as it were, step by step, to

the knowledge of the more complex; assigning in thought a

certain order even to those objects which in their own nature do

not stand in a relation of antecedence and sequence.

- And the last, in every case to make enumerations so complete,

and reviews so general, that I might be assured that nothing was

omitted.” mathematics and logic based, computer (processor and

implementation, today and tomorrow) oriented algorithm

design (problem solving technology) in the run up to software

engineering (application and system software)

computer oriented design of correct, efficient, robust,

modular, extensible, (at least in parts) reusable algorithms

- taking the simplest, shortest way (simple - but hard to achieve, scoutics)),

- using the most suitable tools (problem – tool resonance,

creative and efficient formula manipulation is an important part of algorithm design, of all mathematics based problem solving methods),

- saving brain power

Algorithm Engineering

with the goal to provide so the basis for efficient, low-cost

and high-quality software,

more general: for successful high-tech, high-performance, high- powered, high-quality but low-cost industrial products, esp. in the high-tech and in IT field.

Have in your algorithm engineering tool box:

- a broad range of accessible, free and innovative linkable

knowledge (mathematics, algorithmics, engineering,

natural and life sciences, philosophy (esp. dialectics),

history of sciences, literature, daily life: catch as catch can!),

- professional experience and feeling,

- patient persistence (never give up),

- tireless imagination,

- enthusiasm,

- creativity, ability to think out of the box, to find new

low-cost, high-quality solutions, to find “blue ocean”

solutions, to doubt about the achieved result and to search

for better solutions.

- How we can improve, accelerate, tune the creativity, this is

one of the key problems of engineering, a brainware problem. For further reading:

- T. Kelley, J. Littman. The Art of Innovation.

London 2002 , ISBN 0007102933

- C. Kim, R. Mauborgne. Blue Ocean Strategy: How to Create

Uncontested Market Space and Make Competition Irrelevant.

Harvard 2005 , ISBN 1591396190

- J.M. Lesinski. Bill Gates.

First Avenue Editions 2006 , ISBN-13: 978-0822570271

- D. Dearlove. Business. The Richard Branson Way.

Wiley 2007 , ISBN 978-1-841-12764-4

Recommended algorithmics books

Algorithm Engineering

- The classic work on Computer Programming Algorithms!

D.E. Knuth. The Art of Computer Programming, Volumes 1 – 3 Addison-Wesley Professional; 2 edition (1998)

- The classic MIT textbook

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein.

Introduction to Algorithms.

The MIT Press; 2 edition (2001)

- The reference book, survey of the state of the art

M.J. Atallah (ed). Algorithms and Theory of Computation Handbook.

CRC; 1 edition (1998)

2 edition (2009): Foundations of Algorithms and Theory of Computation.

2* Creative and efficient formula manipulation is an important part of algorithm design, of all mathematics based problem solving methods. Necessary algorithmic finger exercises. Examples

2.1 An ubiquitous simple example

From taxi to take-off. A story about the first

take-off of the young dragon Carl Friedrich Gauss

Problem

Add the natural numbers from 1 to 10 (100) as efficiently as possible.

Classical solution

((((((((1 + 2) + 3) + 4) + 5 ) + 6) + 7) + 8) + 9) + 10 (1) ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓

3 6 10 15 21 28 36 45 55

Efficient solution (for this special case!) by suitable “tuning up” (tune up = make small changes to an engine so that it works as

Algorithm Engineering

well as possible), here: creative exhausting of the freedom given by the commutative and the associative laws of addition, creative bracketing:

(1+10) + (2 + 9) + (3 + 8) + (4 + 7) + (5 + 6) = 5*11 = 55 (2) ↓ ↓ ↓ ↓ ↓

11 11 11 11 11

Colorencoding, of opposite pairs → invariant!!!

Efficient solution for 1 to 100:

(1 + 100) + (2 + 99) + (3 + 98) + .. + (50 + 51) = 50*101 = 5050 ↓ ↓ ↓ ↓

101 101 101 101 (3)

A similar pairing approach to find the efficient solution by creative exhausting of the freedom given by the commutative and the associative laws of addition, creative bracketing is

s10 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10

s10 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1

-----------------------------------------------------------------------------------2s10 11 +11 +11 +11 +11 +11 +11+11 +11 +11 = 10*11 = 110

1 s10 *10*11 = 55 2

1 general solution sn i = *n*(n+1) . (4;5) 2i=1

2.2 But how about other natural number sums, f.e.

i; i; i; (-1)n-iim; ... ?23m

i=1i=1i=1i=1nnnnn

Algorithm Engineering

2.3 Horner’s problem, Horner’s algorithm (rule) and beyond Given a polynomial in x of order n with constant coefficients ai pn(x)= aixn-i ; x, ai ¡ (95)

i=0n

f.e

n=4 ® p4(x)=a0x4+a1x3+a2x2+a3x+a4 (96) Find a procedure to calculate

* the value of pn(x) for given values of the coefficients ai and of the variable x in a computationally most efficient way

(minimal number of multiplications; all additions and

subtractions with relatively small numbers)

* and simultaneously the value of p’n(x) in the same way Solution

● Horner’s calculation idea:

Transformation of equ. (96)/(95) by repeated application of the distributive law of multiplication into a 4/n-fold

parenthesized nested expression with only 4/n multiplications, creative bracketing:

p4(x) ((((a0) x a1) x a2) x a3) x a4 h0 h1 h0 x a h2 h1 x a2

h3 h2 x a3 h4 h3 x a4 p4(x)

(97) ● Equ. (97) → Horner’s algorithm (rule):

h0 = a0 initialization (98)

Algorithm Engineering

hi 1 = hi* x + ai+1; i = 0(1)n-1 recursion equ. (99) pn(x) = hn result (100) ● How we can calculate simultaneously the value of p’n(x) in the same way?

Look at the following table for n = 4:

By introducing a second iteration variable g for p’n(x) we get the extended Horner’s algorithm:

h0 = a0 ; g0 = 0 initialization (101) hi+1=hi*x+ai+1gi+1=gi*x+hi ; i=0(1)n-1

(102) pn(x)=hn ; p'

n(x)=gn results (103)

Horner’s algorithm, extended form (pn(x) || p’n(x)),

computer science notation: coupled recursion equations

Algorithm Engineering

(A3) ● Application of (A3) Newton’s method, an efficient (quadratically converging) iterative procedure for finding

approximations to the zeros of

a differentiable real-valued

function f(x), especially of a

polynomial pn(x) equ. (95) using the recursion formula f(x) x := x - / . (104) f(x)

It can also be used to find a minimum or maximum of f(x) by finding of zeros of the first derivative of f(x).

2.4 A walk to the and around the extended Euclidean algorithm

1. We start with a simple example

Given: a=1272, b=684

Find gcd(a,b) via factorization of a and b into primes. (For large a and b very computing time expensive!)

Solution:

Algorithm Engineering

1272 pi i 23 31 190 571

684 pi i 22 32 191 570

gcd(1272,684)= pimin( i, i) 22 31 190 570 12

i 1i 1 i 1

= greatest reduction factor of 1272106 12106 the fraction 68457 1257

2. To find gcd(1272,684) without factorization of 1272 and 684 1272into primes, we transfer the ordinary fraction step by step 684

into a simple continued fraction using the key formula x div(x,y) y rest(x,y) ; x,y

x int() x mod yy

12721 684 588588 rest(1272,684) 1 684684684

div(1272,684)

1111 1 1 6841 588 9696 rest(684,588)1 588588588

div(684,588)

Algorithm Engineering

1 1

1111 1 1 5886 96 12126 969696

1 1 1 1 rest(588,96) div(588,96)

111 1 1 1 6 6 961212

111 1 111 1 6 6 rest(96,12) 8 8 gcd(1272,684) 1212stop 0

Summary

2.1 Simple continued fraction representation of the ordinary

1272 fraction 684

127211272 1 scf() 1; 1, 6, 8 6846841 6 8

2.2 Terminating way from (a,b) to gcd(a,b) step by step without factorization into primes, from large to small numbers: 1272,684 684,588 588,96 96,12 12,0 a b gcd(a,b) 0 stop

Algorithm Engineering

In algorithmic notation: Euclidean algorithm, basic form,

2.3 2.1 and 2.2 in algorithm notation: Extended EA

Algorithm Engineering

gcd(1272,684) 12; scf [1,1,6,8] 684

EA, matrix representation of

u a * initialization u: a; v: b : v b * recursion equation u,v : v,rest u,v

vv u : v rest(u,v) u div(u,v) v

1 0 u 1 div(u,v) v

* result and

termination condition

gcd(a,b) u : 0 v

For our example a= 1272; b=684 we have then the following execution record

1 u 0 u i : v 1 div(u,v) v

1272 0 684

684 01 1272 1 : 588 1 1 684

Algorithm Engineering

588 02 : 96 1

96 03 : 12 1

12 04 : 0 11 684 01 01 1272 1 588 1 1 1 1 684 1 588 01 01 01 1272 6 96 1 6 1 1 1 1 684 1 96 01 01 01 01 1272 1 6 1 1 1 1 684 8 12 1 8

7 13 1272 = 684 57106 This shows: there is a linear matrix equation (transformation) gcd(a,b) m11m12 a a ; abs(det) 1 0 m21m22 b b

can be caculated recursively together with u,v

10 : initialization 01 1 0 : recursion equation 1 div(u,v) : w for v 0 result

本文来源：https://www.bwwdw.com/article/1nk1.html