Увод у алгоритам бруте форце
„Подаци су нова нафта“ ово је нова мантра која влада глобалном економијом. Живимо у дигиталном свету и сваки посао се врти око података који претварају у профит и помажу индустријама да остану испред своје конкуренције. Са брзом дигитализацијом, експоненцијалним порастом пословног модела заснованог на апликацијама, сајбер-злочини представљају сталну претњу. Једна таква уобичајена активност коју хакери обављају је Бруте форце.
Бруте Форце је приступ покушају и грешци где нападачи користе програме да би испробали различите комбинације да би провалили у било коју веб локацију или систем. Они користе аутоматизирани софтвер за понављајуће генерације комбинација корисничког ИД-а и лозинки све док на крају не генеришу праву комбинацију.
Бруте-Форце Сеарцх
Брза сила претрага је најчешћи алгоритам претраживања, јер не захтева знање о домену, све што је потребно јесте опис стања, легални оператори, почетно стање и опис циљаног стања. Не побољшава перформансе и у потпуности се ослања на рачунарску моћ да испроба могуће комбинације.
Алгоритам бруте форце претражује све позиције у тексту између 0 и нм без обзира да ли се појава узорка почиње тамо или не. Након сваког покушаја, он помера шестар удесно за тачно 1 положај. Временска сложеност овог алгоритма је О (м * н). па ако тражимо н знакова у низу од м знакова, требаће н * м покушаја.
Погледајмо класичан пример путујућег продавца како би алгоритам лако разумео алгоритам.
Претпоставимо да продавац мора да прође у 10 различитих градова у некој земљи и жели да одреди све најкраће руте из свих могућих комбинација. Овде алгоритам грубе силе једноставно израчунава удаљеност између свих градова и бира најкраћи.
Други пример је покушај пробијања 5-цифрене лозинке, а тада велика груба сила може потрајати и до 10 покушаја да се кок пробије.
Бруте Форце Сорт
У техници сортирања грубе силе, листа података се скенира више пута како би се пронашао најмањи елемент на листи. Након сваке итерације по листи, она замјењује најмањи елемент на врху снопа и започиње сљедећу итерацију из другог најмањег податка на листи.
Горња изјава може бити записана у псеудо коду на следећи начин.
Овде је проблем у величини 'н', а основна операција је 'ако' тест где се подаци података упоређују у свакој итерацији. Неће бити разлике између најгорег и најбољег случаја, јер број замена је увек н-1.
Усклађивање низа грубих сила
Ако су сви знакови у обрасцу јединствени, тада се може применити подударање низа Бруте силе уз сложеност Биг О (н). где је н дужина низа. Бруте форце Усклађивање стрингова упоређује образац са субстрингом текстуалног знака по знаку све док не добије неусклађен карактер. Чим се утврди неусклађеност, преостали карактер подврста се испада и алгоритам прелази на следећу подстрану.
Нижи псеудо кодови објашњавају логику подударања низа. Овде алгоритам покушава да тражи узорак П (0… м-1) у тексту Т (0… .н-1).
овдје би најгори случај био кад се прелазак на другу подстрану не изврши до упоређивања М Тх .
Најближи пар
Изјава проблема: Да бисте пронашли две најближе тачке у скупу од н тачака у дводимензионалној картезијанској равнини. Постоји н број сценарија где се овај проблем појављује. Пример из стварног живота би био у систему контроле ваздушног саобраћаја где морате надгледати летелице које лете близу једна другој и морате сазнати најсигурнију минималну удаљеност коју ови авиони морају да одржавају.
Извор: Википедиа
Алгоритам бруте силе израчунава удаљеност између сваког различитог скупа тачака и враћа индексе тачке за коју је удаљеност најмања.
Брута сила решава овај проблем временском сложеношћу (О (н2)) где је н број тачака.
Испод псеудо-кода користи алгоритам бруталне силе да пронађе најближу тачку.
Конвексна љуска
Изјава проблема : Конвексни труп је најмањи полигон који садржи све тачке. Конвексни труп скупа с тачке најмањи је конвексни многокут који садржи с.
Конвексни труп за овај скуп тачака је конвексни полигон са врховима на П1, П5, П6, П7, П3
Линијски сегмент П1 и Пн скупа од н тачака део је конвексног трупа ако и само ако су све остале тачке скупа смјештене унутар границе полигона формиране одсеком линије.
Повезајмо то гуменом траком,
Тачка (к1, и1), (к2, и2) чини линију ак + за = ц
Када су а = и2-и1, б = к2-к1 и ц = к1 * и2 - к2 * и1 и подели равнину са осовином + за-ц 0
Дакле, морамо да проверимо ак + би-ц за остале тачке.
Груба сила решава овај проблем временском сложеношћу О (н 3 )
Исцрпна претрага
За дискретне проблеме у којима не постоји ефикасно решење, постаје неопходно тестирати свако могуће решење на начин који следи.
Исцрпна потрага је активност која на систематски начин проналази сва могућа решења проблема.
Покушајмо да решимо проблем продавца путовања (ТСП) користећи Брутеов исцрпни алгоритам претраживања.
Изјава проблема: Постоји н градова у које продавац треба да путује, он жели да открије најкраћу руту која покрива све градове.
Размишљамо о Хамилтоновом кругу да реши овај проблем. Ако постоји склоп, било која тачка може започети врхове и завршити врхове. Једном када су одабрани почетни врхови, потребан нам је само ред за преостале врхове тј. Н-1
Тада би било (н-1)! Могуће комбинације и укупни трошак за израчунавање пута би били О (н). стога би укупна временска сложеност била О (н!).
Закључак
Сада када смо стигли до краја овог водича, надам се да сте сада добили коректну представу о томе шта је Бруте Форце. Такође смо видели разне алгоритме Бруте форце који можете применити у својој апликацији.
Препоручени чланци
Ово је водич за алгоритам Бруте Форце-а. Овде смо расправљали о основним концептима алгоритма Бруте Форце. Можете и да прођете кроз друге наше предложене чланке да бисте сазнали више -
- Шта је алгоритам?
- Питања о интервјуу за алгоритам
- Увод у алгоритам
- Алгоритам у програмирању