как да бъда инженер по алгоритми


Отговор 1:

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

Ако искате да станете гуру в алгоритмите, тогава трябва да научите за района до степен, че можете да го научите. В края на краищата гуру означава учител или майстор и нищо не ви помага да овладеете предмет като преподаването му. Препоръчвам да започнете от малко. Изберете алгоритъм или няколко свързани алгоритми (може би някои алгоритми за сортиране) и се опитайте да ги научите на някого. По този начин ще получите по-задълбочено разбиране на тези алгоритми. Разбира се, трябва да обяснявате не само алгоритмите, но защо работят и колко бързо работят (т.е. асимптотичен анализ). Може да се спънете наоколо, но това е ОК; много хора, които станаха добри учители, в началото не бяха гладки като коприна. Продължавайте да се опитвате, докато не успеете да обясните добре алгоритмите; в този момент ще ги разберете.

След това опитайте отново с различни алгоритми. Направете това няколко пъти, докато стигнете до точката, в която наистина сте уверени в разбирането си за алгоритмите. В този момент ще разберете дали разбирате алгоритмите. След като разберете дали наистина разбирате материала, ще бъдете на път да станете гуру.

Но това не е всичко. Също така би трябвало да можете сами да измислите алгоритми. Тъй като ме помолихте конкретно да отговоря на въпроса ви, ще предположа, че сте запознати

Въведение в алгоритмите

. За третото издание направихме обществено достъпни отговори за избрани упражнения и проблеми; можете да ги намерите

тук.

Опитайте да решите тези упражнения и проблеми, без да надниквате в нашите решения. След това сравнете вашите решения с нашите.

Желая ви успех да станете гуру алгоритми!


Отговор 2:

Ако прецените

Таксономия на Блум

в Когнитивния домейн ще разберете, че извеждането на алгоритми изисква "

синтез

. "

Синтез

е второто най-високо ниво в таксономията, което означава, че естествено идва след всичко преди него:

Знание

,

Разбиране

,

Приложение

, и

Анализ

.

В момента изглеждате добре в постигането на знания и постигането на разбиране. Изглежда, че можете да приложите наученото. Все още обаче имате две нива на още по-висше обучение, за да решавате алгоритмични / програмни проблеми. Трябва да използвате анализ и след това да работите за синтез.

Какво включва анализът? Според Уикипедия изисква да започнете да „разбивате информацията на части, като идентифицирате мотиви или причини“. Направили ли сте това с обединяване на сортиране? Знаете ли защо многократно разделяме оригиналния списък на две части? Обмисляли ли сте защо действията на сортиране на сливане водят до време на изпълнение O (nlgn)? Разбирате ли защо трябва да обединявате всеки под-списък заедно в групи от по двама? Анализирали ли сте какви свойства са верни във всяка точка от алгоритъма? Знаете ли защо тези свойства трябва да са верни? Уикипедия казва, че при анализа трябва да вземете предвид елементи, взаимоотношения и организационни принципи. След като анализирате нещо, ще бъдете по-подготвени за синтез.

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

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

Така че, когато сте придобили цялата тази информация, се връщате към проблема за сортиране на обединяването. След като го анализирате, ще разберете, че силата на сортирането на сливанията се крие във факта, че можете да обединявате списъци, като сравнявате два елемента наведнъж по линеен начин. С промяната в изискванията вече не можете да сравнявате два елемента наведнъж по линеен начин. Вместо това трябва да сравнявате k елемента наведнъж. Тогава се питате как мога да намеря минимума от k елемента за линейно или почти линейно време? Добре, че научихте миналия месец, че минималните бинарни купчини могат да направят точно това, от което се нуждаете. Тогава питате, от какво се нуждая минималната стойност? Първият елемент във всеки от списъците thek. Така че, ако съхраняваме първата стойност от всеки списък в минимална двоична купчина, можем просто да извадим минималната. След това се връщаме към това, което е направило двупосочното сортиране, след като е намерило минимума. Той го вмъкна в списък и след това премести курсора в списъка, от който идва минималната стойност. Как се превежда това за нас? Можем да добавим минимума към масива с резултати. Знаем от кой под-списък сме извлекли минимума, но какво означава напредването на показалеца в този списък? Това означава, че нов номер сега е в предната част на списъка, което означава, че нов номер трябва да бъде в нашата минимална купчина. Затова поставяме следващото число в купчината и повтаряме. Изглежда, че тази основна идея ще работи и всеки път, когато направим k-way сливане на списък с n елемента, отнема O (nlgk) време.

Както можете да видите, след като имате голям корпус от знания за домейн, ще бъдете готови да синтезирате. Вашият ум ще прави връзки между различни алгоритми и структури от данни, които познавате. Ще започнете да свързвате ограничения и модели и парадигми. Рядко някой произвежда майсторска работа, без да се учи от великите преди него. Погледнете към великите умове на поколението преди нас. Прочетете писанията на Knuth, Dijkstra, Rabin и др. Оценете това, което са направили за полето ... и след това се вдъхновете.

И накрая, огромен компонент на обучението за решаване на алгоритми е да вярвате в себе си.

Късмет!


Отговор 3:

За мен има 3 етапа на разбиране:

  • изобщо не познавайки темата
  • познаване на темата
  • разбиране на темата

Звучи достатъчно просто, нали? Проблемът е, че повечето хора само бегло познават темата. Те имат размита представа какво означава понятие, но не го разбират истински.

Ефектът на Дънинг-Крюгер работи по следния начин: „Колкото по-опитни сте, колкото повече практика сте приложили, толкова повече опит имате, толкова по-добре можете да се сравнявате с другите. Докато се стремите да се усъвършенствате, започвате да разбирате по-добре къде имате нужда от работа. Започвате да виждате сложността и нюанса; вие откривате майстори на вашия занаят и се сравнявате с тях и виждате къде ви липсва.

От друга страна, колкото по-малко сте квалифицирани, толкова по-малко практика сте приложили и колкото по-малко опит имате, толкова по-лошо се сравнявате с другите по определени задачи. "

И така, как можете да бъдете „истински софтуерен инженер“ или „гуру в алгоритмите“?

Първо се запознавате с темата. Запознайте се с темата. Поздравления, вече сте на стъпка 2. Сега разберете темата и я разбийте. Вижте къде вашите знания имат дупки. Най-лесният начин да направите това е да отговорите на въпроси, защото това по същество е същото като да тествате себе си.

Обикновено повтаряте през тези 3 етапа на разбиране, защото щом схванете идеята, това трябва да ви отведе до още няколко концепции, за които или не сте чували, или имате слабо разбиране.

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

По принцип, за да се подобрите в нещо, трябва да видите къде вашите умения не достигат. В края на краищата, там се усъвършенствате. Dunning-Kruger се съгласява с това - образованието е колкото да научиш това, което не знаеш, толкова и да добавиш към това, което правиш. Благодаря за A2A.


Отговор 4:

Вярвам, че изучаването на алгоритми в изолация от реални проблеми е скучно. Същото като изучаването на математика, без да я прилагате. Мисля, че най-добрият начин да опознаете много алгоритми би бил да напишете собствената си операционна система от нулата. Това е много работа и изисква известни технически познания за хардуера, но ще ви държи мотивирани.

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

За съжаление има много малко книги за приложните знания. Това важи както за математиката, така и за компютърните науки. Ще ви е трудно да разберете какъв алгоритъм ви е необходим за решаване на проблем от реалния свят, ако разглеждате книга, която категоризира алгоритмите по тяхно име, а не по проблема, който те решават. Също така е трудно да се намери книга, която описва само най-често използваните алгоритми. Тъй като има толкова много алгоритми, човек би искал да научи най-използвания от много области на приложение, преди да реши да се специализира само в някои области.

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

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


Отговор 5:

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

Но само да добавя едно нещо ... Трябва да предложа да започнете с курсовете на Станфорд Алгоритми Проектиране и анализ I и II (връзки по-долу) на курсовете, преподавани от Тим ​​Roughgarden. Той е невероятно да разбива нещата за вас.

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

А сега как се отнася до това да си истински софтуерен инженер. Истината е, че има и други неща, в които бихте предпочели да инвестирате, за да станете „истински“ софтуерен инженер. И не бих казал, че владеенето на алгоритми до степен да бъдеш гуру е един от тях, поне не в общия случай. Странното е, че обикновено е по-важно като умение за интервюиране, отколкото на работа. И все пак колко голяма дълбочина на знанията за алгоритъма всъщност се изисква за вас като софтуерен инженер ще зависи от вашия домейн / проблемно пространство.

https://www.coursera.org/course/algo

https://www.coursera.org/course/algo2

Късмет!


Отговор 6:

Голяма O-нотация.

Big-O алгоритъм сложност измама лист

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

Докато увеличавате броя на елементите от данни в набора от данни, които искате да обработите, всеки елемент ще има някаква функция, която описва колко повече време се нуждае и различна функция за това колко повече пространство се нуждае.

Ако нуждите се мащабират линейно с броя на елементите, това е O (n).

Някои алгоритми са очевидно по-лоши от други по отношение на използването на ресурси. Например никой не използва Bubble Sort, за да сортира масив от неща, защото най-лошият резултат на сортиране на балон е O (n ^ 2).

Сортиране на мехурчета

За разлика от тях, Quicksort в същия масив отнема само O (n log (n)).

Структурите на данните също оказват голямо влияние върху това кои алгоритми са достъпни за вас. Например: Времето, необходимо за намиране на нещо в масив с помощта на линейно търсене, е O (n), ако трябва да проверите всеки елемент, за да видите дали е правилният. Вмъкването на нови неща в сортиран масив означава намиране на мястото за вмъкването му и преместване на всичко нагоре в позиция, така че да е и O (n).

От друга страна, можете да сортирате масива за O (n log (n)) и след това да използвате двоично търсене върху него, за да получите търсене в O (log (n)) време.

Но ако имате повече елементи, отколкото вашият масив може да побере? В C ще трябва да направите по-голям масив и да копирате всички елементи в новия масив. Времевото наказание там е O (n).

Ако съхранявате нещата много често, можете да използвате единично свързан списък, където времето за вмъкване е O (1), което означава, че можете да вмъкнете елемент в сортиран ред за същия период от време, независимо дали има много малко или много много елементи са в свързания списък. В свързания списък времето за търсене е O (n) точно като масив.

Ако обаче търсите много често структурата си на данни, може да помислите за използване на двоично дърво за търсене. Бинарните дървета за търсене отнемат само O (log (n), за да се вмъкнат в структурата на данните и отнема само O (log (n)) време, за да намерят нещо.

Компромисът между тези структури от данни е пространство:

  • Масивът съдържа само данните, които трябва да съхраните.
  • Единично свързан списък се нуждае от един указател на възел, който да сочи към следващия възел.
  • Бинарното дърво за търсене се нуждае от два указателя на възел в допълнение към данните (елемент от данни се съхранява във всеки възел)

Така че, като изберете по-бърза структура от данни в сложността на времето (бинарното дърво за търсене), вие консумирате повече памет (сложност на пространството) за същото количество елементи от данни, с които работите.

Всеки път, когато научите нов алгоритъм, можете да използвате Big-O нотация, за да прецените неговите достойнства и недостатъци, за да можете да знаете кой да изберете за вашия дизайн.

Последното съображение е, че някои алгоритми с изключително добра сложност във времето и пространството могат да бъдат трудни за разбиране, което от своя страна може да доведе до грешки при изпълнението. Тези алгоритми се прилагат най-добре веднъж, като се използва език, който поддържа шаблони, за да можете да ги тествате напълно и след това да ги съхранявате в библиотека, където няма да се налага да ги редактирате твърде често.


Отговор 7:

Това са несвързани въпроси. :) Каквото и да имате предвид под „истински софтуерен инженер“, това няма нищо общо с „гуру в алгоритмите“.

Ако „истинският софтуерен инженер“ е „професионален софтуерен инженер“, тогава е просто. Професионалистът е човек, който получава пари за работата си, така че просто трябва да си намерите програмист и сте „професионален софтуерен инженер“.

Ако имате предвид „компетентен софтуерен инженер, който дава висококачествени резултати“, тогава е по-сложно. Трябва да научите и внедрите подходящи практики за софтуерно инженерство (изработка на софтуер) като обмислен модулен дизайн (прилагане на подходящи дизайнерски модели или каквото има смисъл за задачата), тестване, документиране, преглед на кода и така нататък. Освен това трябва да станете компетентни на „ниво по-горе“, например трябва да разберете цялостната архитектура на продукта, заетостта и техническите ограничения, жизнения цикъл и управлението на продукта.

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


Отговор 8:

Ако наистина искате да бъдете гуру на алгоритми - тогава в крайна сметка трябва да „пресъздадете колелото“. Знам, че това звучи налудничаво, но ако "само" подготвяте книги и отблъсквате нечия идеология, тогава всичко, което правите ефективно, се превръща в рупор за някой друг.

Първо трябва наистина да разберете приложенията на алгоритъма - което е просто измислен термин за уравнение, което решава нещата. Така че, няма да станете гуру в алгоритмите, но повече, ще се превърнете в решаване на проблеми в дадена област, която може да бъде приложена с помощта на алгоритми.

Второ, трябва да намерите поле, което всъщност наистина „върши“ вашите интереси. След това трябва да поддържате метапознание в това поле до точка, в която наистина да разбирате проблемите, които наистина трябва да бъдат решени. След това трябва да възприемете уменията, които сте научили от "не преоткриване на колелото" и да надградите върху тях, за да "преоткриете колелото". В този момент ще сте овладели достатъчно този клон на тази тема, за да бъдете считани за „господар / гуру“, където вашите мисли по темата ще бъдат добре уважавани и приети.

В противен случай просто ще сте момче, отговарящо на въпрос в Quora, хаха.

Благодаря

Брандън Б.


Отговор 9:

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

Ако искате да бъдете добър програмист, научавате концепции, а не код. Мога да намеря всеки алгоритъм, който искам, вече доста усъвършенстван с помощта на Google или StackOverflow и просто да го пусна и да го използвам. Отнема около 10 секунди. Познаването на концепцията, която стои зад ЗАЩО я използвате и как да определите КОГА и КЪДЕ и по-важното кога и къде НЕ да се използва, е това, върху което трябва да се фокусирате върху ученето.

Това прави добрия програмист ... способността му да използва информацията и знанията и да ги прилага във всички ситуации, като разпознава ситуации, в които ще бъде полезна, а не научава някакъв код, който можете да намерите за 10 секунди онлайн.


Отговор 10:

След като прочетох над 5 книги за алгоритъма, все още се чувствам слаб в много под-области на алгоритъма.

След това един ден взех книга с име и не мога да спра да го чета, той е толкова добре организиран, след като прочетох и кодирах над 80% от него, открих, че нивото на алгоритъма ми се подобрява значително, поне за общите алгоритми.

Така че, предлагам на всеки да вземе тази книга, въпреки че името й е за интервю, но всъщност става дума главно за алгоритъм от моя гледна точка.

BTW:

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

Отговор 11:

Тъй като не се считам за гуру в алгоритмите, а просто за много любопитен и усърден софтуерен инженер, ще ви препоръчам книга, която препоръчвам и на други и която открих за златно съкровище (не по-малко от това). Книгата е: „въведение в алгоритмите - творчески подход“ от Уди Манбер. Страхотна книга е да вземете и да се научите да решавате проблеми и да проектирате алгоритми. Причината, поради която толкова много обичам тази книга, е методологичният подход, който е необходим за преподаване на алгоритми, който разчита до голяма степен на „математическата индукция“. Повечето книги и учители използват индукция като средство за доказване на коректността на алгоритмите. Уди Манбер използва математическата индукция като средство за тяхното конструиране. За мен това беше революционен начин за разглеждане на дизайна на алгоритмите. Затова настоятелно препоръчвам да вземете тази книга, ако искате да подобрите уменията си за решаване на проблеми и способностите за алгоритмичен дизайн. Въпреки че не мога да ви обещая, че ще станете „гуру“, мога да ви обещая, че определено ще станете много по-опитен решаващ проблем, отколкото сте били (преди да го прочетете).