Началото...

[ptj]

Първо ще направя едно отклонение с пример за практическа задача:

В далечната 1989 година срещнах една доста интересна задача в конкурс за програмиране на списание "Компътър за вас". Тя гласеше:

От първите [tex]n[/tex] числа на Фибоначи да се намерят тези номера [tex]k[/tex], за които съответното число на Фибоначи е точен квадрат на естествено число. Програмата трябваше да намира решение при зададено естествено [tex]100000 \le k \le1000000[/tex] в рамките на 2 астрономически часа.

За по-малките по това време в България персоналните компютри бяха още на DOS.3.3 (прародител на Windows), Интернет не съществуваше, а аз имах късмета да изпробвам [tex]PC-2[/tex] (версия на IBM с процесор Intel 80386). Той беше истинска революция за времето си, но даже и неговите възможности бяха ограничени ( тактова чистота 16-33 MHz).

На практика това означаваше, че всички "хамалски" алгоритми гърмяха. Тогава започнах анализ на лист, с идеята да намеря определени закономерности, които по-късно да вкарам в подходяща рамка (програма). За мой късмет открих периодичност в остатъците на числата на Фибоначи по даден модул. Приложих същата идея и към редицата с точните квадрати на естествените числа. Накрая остана да комбинирам резултатите по подходящ модул. Експериментирах с динамично решето и успях с използването на не повече от 10 модула (между 2 и 37), да покажа несъществуването (в редицата на Фибоначи на други точни квадрати), освен 144. Реализираната програма работеше 13 секунди за [tex]k=1000000[/tex].

Защо дадох този пример:
Защото имаме задача, за която стандартните алгоритми (варианти на пълно изчерпване на случаите) работят за неприемливо дълго време, т.е. след определени граници задачата може да стане неизчислима за тях. За нейното решаване използвах друг алгоритъм, в който същественото бе, че използва съвсем други връзки между отделните елементарни факти в процеца на намиране решение на поставения проблем.

Казано с други думи, повишаването на бързодествието (производителността) не се дължеше на някой метод за оптимизиране на вече съществуващи алгоритми (имащи ограничени възможности).

...
(По-късно ще продължа.)