Алгоритми/Увод

Ова књига покрива технике за пројектовање и анализу алгоритама. Алгоритамске технике укључују: "завади, па владај", "бектрекинг", динамичко програмирање, "похлепи алгоритми" и претраживање успоном. Било који решиви проблем у општем смислу има бар један од следећих типова алгоритама:

очигледан начин
медотичан начин
паметан начин; и
чудесан начин

Први, од свих основних нивоа, "очигледно" решење би можда покушао да исцрпљујуће претражује одговор. Интуитивно, очигледно решење је оно које настаје једноставно ако сте упознати са програмским језиком и основним техникама решавања проблема. Други ниво је методичан ниво и он је кључ ове књиге: након разумевања материјала који је приказан овде, моћи ћете да на методичан начин да претворите већину очигледних алгоритама у боље представљен алгоритам.

Трећи ниво, паметан ниво, захтева више разумевања елемената који су укључени у проблем и разумевање њихових особина, или чак редефинисање алгоритма (на пример, нумерички алгоритми искоришћавају математичка својства која нису очигледна). Паметан алгоритам је можда тежак за разумевање, јер није очигледно да је тачан, или је тежак за разумевање, јер се заправо извршава брже него што би изгледало то што захтева.

Четврти и последњи ниво алгоритамског решења је чудесан ниво: он је резервисан за ретке случајеве где је продоран резултат веома не-интуитивно решење. Природно, сваки од ова четири нивоа је релативан и неки паметни алгоритми су такође обухваћени у овој књизи. Почнимо.

Предуслови

Како бисте разумели метерију која је приказана у овој књизи, морате знати програмски језик довољно добро да можете преведете псеудокод у овој књизи у радно решење. Такође треба да знате основе о следећим структурама података: низовима, стековима, редовима, уланчаним листама, стаблу, хипу или реду са приоритетом, раздвојеним скуповима и графовима. Осим тога, требало би да знате основне алгоритме као што су бинарна претрага, алгориам сортирања (merge sort, heap sort, insertion sort и други) и претраживање-прво-у-ширину или претраживање-прво-у-дубину. Ако нисте упознати ни са једним од ових предуслова, требало би прво да погледате материју у књизи Структуре Података.

Када је ефикасност битна?

Не захтева сваки проблем најефикасније могуће решење. За наше намене, термин ефикасан се бави временом и/или простором за које је потребно да обави задатак. Кад су и време и простор обилни и јефтини, онда се можда не исплати плаћање програмера да проведе дан радећи да томе да програм постане бржи. Међутим, ево неких случаја где је ефикасност битна:

Када су ресурси ограничени, промена у алгоритму може да направи велику уштеду и допусти да се ограничене машине (као што су мобилни телефони, уграђени системи и сензор мрежа) протежу на границама могућности.
Када је податак јако велик, ефикасније решење може означавати разлику између завршавања задатка у два дана уместо у две недеље. Пример укључује физику, генетику, веб претраживање, масивне онлајн продавнице и мрежно анализирање саобраћаја.
Апликације које раде у реалном времену: овај термин се, уствари, односи на прорачуне који дају временску гаранцију, наспрам значења речи "брзо". Међутим, квалитет може само да расте даље бирајући примерени алгоритам.
Рачунско скупи послови, као што је динамика флуида, парцијална диференцијална питања, VLSI дизајн и анализирање криптограма се некад само могу размотрити када решење буде нађено довоњно ефикасно.

Када се потпрограм често користи, време проведено на ефикаснијој имплементацији може да допринесе корист за сваку апликацију која користи потпрограм. Примери укључују сортирање, претраживање, генерисање псеудослучајног броја, кернел операције (не треба мешати са оперативним системом кернел), упити база података и графике.

In short, it's important to save time when you do not have any time to spare. When is efficiency unimportant? Examples of these cases include prototypes that are used only a few times, cases where the input is small, when simplicity and ease of maintenance is more important, when the area concerned is not the bottle neck, or when there's another process or area in the code that would benefit far more from efficient design and attention to the algorithm(s).

Укратко, битно је уштедети време, када немате времена за губљење. Када је битна ефикасност? Примери ових случајева укључују прототипе који се користе само неколико пута, када је улаз врло мали, када је једноставност одржавања битнија, када посматрана област није "уско грло" или када када постоји други процес или област у коду где би било много више користи од ефикасног пројектовања и пажње на алгоритам (алгоритме).

Смислити алгоритам

Пошто претпостављамо да имате неко знање о неком програмском језику, почнимо са питањем како бисмо превели идеју у алгоритам. Претпоставимо да желите да напишете функцију која узима стринг као улазни податак и исти тај стринг са малим словима као излазни податак:

// tolower -- функција која преводи сва алфабетска велика слова, у неком низу карактера str, у мала слова

function tolower(string str): string

Шта вам прво пада на памет када размишљате како бисте решили овај проблем? Можда нека од ова два разматрања:

Сваки карактер у str се мора размотрити
Потребна је функција која пребацује један карактер у мало слово

Прва тачка је "очигледна", јер карактер који треба да буде претворен у мало слово се може налазити било где у стрингу. Друга тачка произилази из прве јер, онда када размотримо сваки карактер, морамо нешто и урадити са њим. Постоји много начина да се напише tolower функција за карактере:

Постоји пар начина да имплементирате ову функцију, који укључују следеће:

погледати c у табели -- индексирани карактер у низу карактера који има верзију малог слова за сваки карактер.

проверити да ли је c у опсегу 'A' ≤ c ≤ 'Z' и онда му додати нумерички офсет.

Ове технике зависе од кода карактера. (Као проблем поделе, можда је табела боље решење, јер је јасније да треба променити само један део кода.)

Међутим када је такав подпрограм имплементиран, имплементација нашег оригиналног проблема одмах следи:

function tolower(string str): string
  let result := ""
  for-each c in str:
    result.append(tolower(c))
  repeat
  return result
end

Петља је резултат наше способности да преведемо "сваки карактер треба размотрити" у наш нативни програмски језик. Да позив функције tolower треба бити у телу петље, постаје очигледно. Овде смо решили да почнемо са празним стрингом и да додамо карактере на крај стринга.

Сада претпоставимо да желите да напишете функцију која пореди два стринга тако што тестира да ли су исти, занемарујући да ли су слова мала или велика:

// equal-ignore-case -- враћа true ако су стрингови s и t једнаки, без обзира на то да ли су слова мала или велика

function equal-ignore-case(string s, string t): boolean

Ове идеје вам можда падну на памет:

Сваки карактер у стрингу s и t ће се морати размотрити
Једна петља која ће пролазити кроз оба стринга би то решила
Али таква петља би требало да припази прво да ли су стрингови исте дужине
Ако стрингови нису истих дужина, онда не могу бити једнаки, јер игнорисање величине слова не утиче на то колико је стринг дугачак
tolower потпрограм за карактере се може поново искористити и пореди ће само мала слова

Функција коју смо размотрили би изгледала отприлике овако:

function equal-ignore-case(string s[1..n], string t[1..m]): boolean
  if n != m:
    return false               \if they aren't the same length, they aren't equal\
  fi
  
  for i := 1 to n:
    if tolower(s[i]) != tolower(t[i]):
      return false
    fi
  repeat
  return true
end

Или, ако сте разматрали проблем у смислу функционалне декомпозиције уместо итерација, функција би изгледала овако:

function equal-ignore-case(string s, string t): boolean
  return tolower(s).equals(tolower(t))
end

Алтернативно, можда сматрате да ни један од ових решења није добољно ефикасан и да бисте више волели да алгоритам направи један пролаз кроз s или t. Ове две имплементације изнад захтевају два пролаза: прва верзија рачуна дужину стринга и онда пореди карактере, док друга верзија рачуна да ли је карактер мало или велико слово у стрингу и онда пореди резултате. (Приметите да је за пар стрингова такође могуће да се њихова дужина израчуна пре другог пролаза, али то такође има недостатака понекад.) Можете замислити колико сличних потпрогорама који тестирају јендакост стрингова који не само да игноришу мала и велика слова, већ и акценте, могу бити написани.

Већ сад можда можете да увидите како се пише псеудокод. Псеудокод није намењен да буде прави програмски језик: апстрахује детаље које бисте морали да садржите у било ком прорамском језику. На пример, језик не преузима генеричке типове или динамичне у односу на статичке типове: идеја је да буде јасно да сте наменили и да не буде много тешко да га преведе на свој нативни језик. (Међутим, тако радећи, морате да донсете неке одлуке што се тиче пројектовања које ограничавају имплементацију у један конкретан тип форме податка.)

Нема ничег посебног у техникама које смо користили како бисмо решили једноставан проблем стринга: можда сте пронашли боље или елегантније решење у програмском језику који сте изабрали. У овој књизи смо истражили опште технике алгоритама како бисмо проширили ваше знање. Можда нећете одмах успети да неки нативни алгоритам направите ефикаснијим, али након разумевања материје ове књиге ћете моћи да методично нађете различита решења и, што је још битније, моћи ћете да питате себе више питања о свом програму. Постављање питања може бити једнако битно као и одговарање на питања, јер постављање добрих питања вам може помоћи да реформулишете проблем и да размишљате инвентивно.

Разумевање алгоритма

Програмери треба одлично да разумеју вишеструко-слојевите абстракције. На пример, погледајте следећи код:

function foo(integer a):
  if (a / 2) * 2 == a:
     print "The value " a " is even."
  fi
end

Depending on the programming task, you may think on the layer of hardware, on down to the level of processor branch-prediction or the cache.

Да бисте разумели овај пример, морате да знате да дељење целих бројева користи скраћивање и да ако је if-услов тачан, онда је последњи значајан бит у a нула (што значи да a мора да буде паран). Такође, код користи исписивање стринга API и сам по себи је дефиниција функције која се користи различите модуле. У зависности од задатка, можете размишљати ??

Често је разумевање бинарног система је од пресудног значаја, али многи модерни језици имају абстракције довољно далеке од хардвера тако да ови нижи нивои нису потребни. Негде се абстракције заустављају: многи програмери не морају да мисле о логичким капијама, нити су физика и електроника потребне. Ипак, битан део програмирања је вишеструко-слојевити начин размишљања.

Али удаљавањем од комјутерских програма према алгоритмима захтева још један слој: математику. Програм може да искористи својства бинарне репрезентације. Алгоритам може да искористи и својства теорије скупова и других математичких структура. Баш као што бинарни систем није експлицитно у програму, ни математичка својства коришћена у алгоритму нису експлицитна.

Типично, када је алгоритам упознат, дискусија (одвојена од кода) је потребна да објасни математику која се користи у алгоритму. На пример, да бисте заиста разумели "похлепи" алгоритам (као што је Дајкстрин алгоритам) морате да разумете математичка својства која показују да је "похлепи" алгоритам валидан за све случајеве. На неки начин, можете посматрати математику као посебну врсту потпрограма који алгоритам позива. Али овај "потпрограм" није показан у коду зато што нема шта да се позива. Док читате ову књигу, покушајте да посматрате математику као имплицитан потпрограм.

Преглед техника

Подели, па владај: Многи проблеми, посебно када је улазни податак дат у низу, се може решити тако што поделимо проблем у мање делове, решимо те мање делове рекурзивно (владај) и онда комбинујемо резултате у један резултат. Примери укључују сортирање спајањем и алгоритам брзог сортирања.

Рандомизација: Технике рандомизације су битне за све више и више апликација. Ово поглавље показује неке класичне алгоритме који користе случајне бројеве.

Бектрекинг: Скоро сваки проблем може да се формулише као бектрекинг алгоритам. Код бектрекинг алгоритама, треба узети у обзир све могуће изборе како би решили проблем и рекурзивно решили потпроблеме под претпоставци да је избор донет. Скуп свих рекурзивних позива генерише стабло у ком се сваки скуп избора се узима у обзир узастопно. Стога, ако решење постоји, оно ће се у своје време наћи.
Бектрекинг је генерално неефикасан, насилна техника, али постоје оптимизације које могу бити извршене да смање и дубину стабла и број грана. Техника се зове бектрекинг, јер након што је први лист посећен, алгоритам се враћа назад и позива стек (поништавање избора који не воде ка успеху) и онда наставити на доњу грану. Да би решили проблем техникама бектрекинг-а, проблем треба да има форму "само-сличности", тако да мањи примерак проблема (након што је донешена одлука) мора да личи на оригиналан проблем. Обично, проблеми могу бити уопштени да би постали само-слични.

Динамичко програмирање: Динамичко програмирање је оптимизациона техника за бектрекинг алгоритме. Када потпроблеми треба да се реше брзо (нпр. када има пуно дупликата грана у бектрекинг алгоритму) време може бити запамћено тако што се реши прво сваки проблем (од доле-па на горе, од најмањег до највћих) и тако што се складиште решења сваког потпроблема у табелу. Тако, сваки потпроблем може бити посећен и решен једном уместо брзо. "Програмирање" у називу ове технике долази од програмирања у смислу уписивања у табелу; на пример, програмирање телевизије је прављење табеле емисија које ће се емитовати и када ће се емитовати.

"Похлепни" алгортми: Похлепи алгоритам може бити користан када се зна довољно информација о могућим изборима. Најбољи избор се може одредити без обзира на све могуће изборе. Типично, похлепни алгоритам нису тешки за писање, али се тешко доказују да су тачни.

Претраживање успоном: Последња техника коју само истражили је претраживање успоном. Основна идеја је да се почне са лошем решењем и да се брзо примени оптимизација за решење док не постане оптималан или се не испуни неки други услов. Битан случај претраживања успоном је мрежни проток. Упркос имена, мрежни проток је користан за многе проблеме који описују односе, тако да нису само за рачунарске мреже. Многи слични проблеми се могу решити коришћењем мрежне протоке.

Алгоритми и примери кодова

Први ниво (најлакши)

1. Пронаћи максимум: са алгоритмом и више различитих програмских језика

2. Пронаћи минимум: са алгоритмом и више различитих програмских језика

3. Пронаћи средњу вредност: са алгоритмом и више различитих програмских језика

4. Пронаћи стање: са алгоритмом и више различитих програмских језика

5. Пронаћи тотал: са алгоритмом и више различитих програмских језика

6. Рачунање: са алгоритмом и више различитих програмских језика

Други ниво

1. Разговор са рачунаром Ниво 1: са алгоритмом и више различитих програмских језика 2. Сортитање - bublle sort: са алгоритмом и више различитих програмских језика

Трећи ниво

1. Разговор са рачунаром Ниво 2: са алгоритмом и више различитих програмских језика

Четврти ниво

1. Разговор са рачунаром Ниво 3: са алгоритмом и више различитих програмских језика 2. Пронаћи приближан максимум: са алгоритмом и више различитих програмских језика

Пети ниво

1. Quicksort