Техники и алгоритми

Techniques and algorithms

Въпреки, че в компютърната литература често не се прави разлика между "техника" и "алгоритъм", ние ще направим известно разграничение между двете.

Алгоритъм

Под алгоритъм ще разбираме последователност от стъпки, чието изпълнение води до даден желан резултат. Обикновено в информатичен смисъл алгоритмите прилагат поредица от вече-известни функции и/или операции върху входните данни, като така произвеждат желания резултат под формата на изходни данни.

Може би най-близката аналогия, която можем да дадем от реалния живот, би била рецепта. Например "алгоритъмът" за готвене на таратор би бил нещо от сорта:

1. Нарежете K краставици на дребни кубчета с размер на страната приблизително един до два милиметра
2. Посолете нарязаните кубчета краставица
3. Разбъркайте в тенджера K кофички кисело мляко (от 400-500 грама всяка)
4. Добавете K чаши вода (приблизително по 200 милилитра всяка) и разбъркайте отново
5. Добавете нарязаните краставици
6. Добавете N супени лъжици олио
7. Добавете M скилитки ситно нарязан чесън
8. Добавете 5*K ситно начупени орехи (без черупките)
9. Разбъркайте една-две минути
10. Готово!

Тук нарязването, бъркането, соленето и т.н. са действията, които прилагаме, а краставицата, киселото мляко, водата, солта и т.н. са входните данни, върху които ги прилагаме. K, N и M пък са аргументи на алгоритъма, които обикновено ни се задават чрез входните данни. Така алгоритъмът ни не създава винаги точно определно количество еднакъв таратор, ами, в зависимост от подадените входни данни, изработва различен такъв. Например, можем да направим таратора без чесън, ако подадем M = 0.

Забележете, че някои от действията, които прилагаме, могат да бъдат други алгоритми. Например можем да имаме специфичен алгоритъм за рязане на краставицата. Също така забележете, че не всичко е предварително фиксирано. Разбира се, входните данни се очаква да са различни, но също така например големината на кубчетата краставица и времето за разбъркване накрая не са конкретно специфицирани. Съществуват алгоритми, които използват случайни числа в себе си, за да постигнат по-разнообразни резултати при различни пускания. За тях ще говорим по-нататък при темите за NP-задачи.

Техника

Под техника ще разбираме нещо малко по-различно. То няма да е точно определена последователност от стъпки, които трябва да следваме за да получим някакъв резултат (както беше при алгоритъма), ами по-скоро по-обща идея, с която можем да съставим алгоритъм за конкретната задача. Да кажем, пример за това би било техниката "приготвяне на супа". В общия случай, това би било нещо от сорта на:

1. Добавете в голям съд някаква течност
2. Добавете продукти
3. Обработете по някакъв начин

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

Ако обаче специфицираме, че съдът ще е тенджера, течността ще е L литра вода, продуктите ще са едно пиле, C грама моркови, и P грама картофи, и обработката ще е варене на котлон за два часа, бихме получили алгоритъм за готвене на пилешка супа.

Допълнителни материали

1. Статия какво е алгоритъм в Wikipedia
2. "Важността на алгоритмите", статия в TopCoder

предишна тема

версия за печат

следваща тема