Программирование или информатика вообще, все об алгоритмах?

40

Как аспирант, я считаю, что престижные компании (такие как Google, Facebook, Microsoft, ...) все чаще и чаще ставят вопросы об алгоритмах в свои тесты и интервью. Несколько стартапов, к которым я обращался, также спрашивали об алгоритмах. Интересно, является ли беглость алгоритмов самой важной вещью для разработчика программного обеспечения в этих компаниях?

Если ответ положительный, каков наилучший метод или ресурсы для эффективного изучения и практического применения алгоритмов? Кажется, я не заинтересован в решении, казалось бы, слишком сложных проблем, встречающихся в большинстве учебников или веб-сайтов. Хотя я легко понимаю основные алгоритмы (например, быстрая сортировка, пузырьковая сортировка, ...), мне очень трудно запомнить и использовать их позже.

Спасибо.

P / S: Если вы спросите меня, что мне нравится, это создание хорошего программного обеспечения для инновационного решения проблем пользователей. Я предполагаю, что это не обязательно означает, что программное обеспечение должно быть очень сложным.

wakandan
источник
26
Любая идея, насколько сложно для Google, чтобы позволить вам искать во всем Интернете с помощью текстового поля и кнопки?
JeffO
21
@JeffO Я даже больше не использую кнопку ;-)
maple_shaft
1
Если Google сделает это проще, все остальные поисковые сайты вообще не будут нуждаться в коде.
JeffO
Я подумал, что вопрос будет о том, как работают компьютеры, например, как работает процессор, как работает ОЗУ, как работает Wi-Fi и т. Д. Это довольно интересный вопрос, который все еще требует много исследований. Я все еще нахожу аппаратное обеспечение более удивительным, чем все гики-программисты на java или php.
Jokoon
2
Это не все об алгоритмах, но на самом деле они лежат в основе CS. Но в программировании есть гораздо больше, чем просто алгоритмы и логика (например, для поддержки кода не требуется только знание алгоритмов).
Хайлем

Ответы:

44

Алгоритмы понятны

Вот прекрасная вещь об алгоритмах: проблемное пространство, с которым они имеют дело, четко определено, т. Е. Ваши требования не только фактически известны , но обычно даже формализованы во многом как метрики для качества решения.

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

Алгоритмы - эффективный фильтр

Текущая проблема промышленности (и образования) - низкое среднее качество выпускников. Это было продемонстрировано с помощью теста FizzBuzz , который:

Напишите программу, которая будет проходить через числа от 1 до 100 и печатать «fizz», если число делится на 3, «buzz», если оно делится на 5, и само число, если оно не делится ни на одно из них.

Очевидно, что большинство выпускников Comp Sci не смогли решить эту проблему. Пожалуйста, обратите внимание, что это алгоритмический вопрос, хотя, конечно, очень простой. Учитывая это, найдя кого-то, кто может решить проблемы, описанные в Google Code Jam или Project Euler, вы уже наслаждаетесь крем-де-ла-крем.

Алгоритмы являются крошечной частью разработки программного обеспечения

Правда в том, что, как только вы работаете в отрасли, вы не будете использовать свои навыки алгоритма более 1% времени.

Прежде чем вы начнете писать код, вы должны сначала собрать и проанализировать требования. Затем вы должны синтезировать свой дизайн на их основе. Тогда вы должны реализовать дизайн. Затем необходимо сравнить реализацию с исходными требованиями, затем выполнить итерации требований, затем выполнить итерацию проекта, затем выполнить итерацию реализации и так далее.

Одним из требований является разумная производительность. Если это требование не выполняется, вы должны профилировать свою реализацию, чтобы отследить узкие места, а затем вы можете оптимизировать ее, что иногда является вопросом прямой микрооптимизации (что довольно легко сделать), но иногда - вопросом используя лучшие алгоритмы (что не всегда легко сделать потом). Следовательно:

Алгоритмы являются критическими

Чем лучше вы разбираетесь в алгоритмах, тем больше шансов, что вы все сделаете правильно с первого раза. В противном случае вы не только столкнетесь с проблемой, которую можно решить только путем реализации лучшего алгоритма, но и не сможете ее решить.
Поэтому, хотя вам почти никогда не нужен этот навык, он представляет собой единственную точку отказа в вашей методологии разработки, и если у вас нет этого навыка, вы можете только надеяться, что необходимость никогда не возникнет, или что кто-то другой подключится, чтобы исправить это для ты.

Что действительно важно, так это получить представление о сложности вычислений и о том, как сохранить ее на низком уровне, как я также объяснил в ответ на аналогичный вопрос . Или специализироваться на вещах, где это просто не важно, таких как разработка графического интерфейса, но опять же почти все ненавидят это ... по причине!

back2dos
источник
5
+1 за очень полный и умный ответ. Также печально, насколько эффективен фильтр FizzBuzz. Нет абсолютно никакого оправдания неспособности сделать это.
Адам Кроссленд
4
Я подумал, что вы должны печатать, fizzbuzzесли число делится на оба, и многие поскользнулись на нем, потому что вам нужно аккуратно оформить заказ по чекам.
Матье М.
1
1% может быть слишком высоким
конопля
1
@MatthieuM .: печать обоих является неотъемлемой частью формулировки требования. Отсутствие этого означает, что вы не проверили требования тщательно; Теперь, что я нахожу интересным, это то, что он не говорит, что вы должны печатать их в каком-то определенном порядке или даже последовательно в том же порядке ...
jmoreno
1
@ back2dos: да, но делать это в случайном порядке звучит более увлекательно ... обратите внимание, что требование, приведенное в этом ответе, не включает строки, только печать . Если вам дали тест FizzBuzz, возможно, стоит указать, что в нем есть много неустановленных предположений (опять же, это может привести к тому, что вас раскрасят как мудреца).
Jmoreno
30

В общем, программирование как работа не об алгоритмах. Вы можете потратить годы на программирование приложений CRUD, не требуя глубоких алгоритмических навыков.

Программирование как работа о:

  1. Связь:

    • Ваш исходный код является средством передачи ваших идей своим коллегам. Если никто не может прочитать / понять ваш код, это бесполезно.

    • Одинокий разработчик, который не разговаривает ни с одним другим разработчиком, вероятно, начнет делать ошибки в коде и считает, что его собственный подход является единственно приемлемым.

    • Вы должны знать, как общаться с заинтересованными сторонами, отделом контроля качества, пользователями, визуальными дизайнерами, администраторами баз данных и т. Д.

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

  2. Знание правильных инструментов: контроль версий, система отслеживания ошибок, IDE, какой язык лучше подходит для конкретной задачи и почему, как использовать анализ кода и т. Д.

  3. Широкие знания и культура: что такое функциональные языки? Как компьютеры интерпретируют код? Почему LOC - бессмысленная мера? и т.п.

  4. Глубокое знание языка, с которым вы работаете.

  5. Алгоритмы.

Информатика, с другой стороны, больше ориентирована на алгоритмы. Если вы работаете как ученый, это может не иметь ничего общего с работой разработчика, и вы будете больше работать над тем, как оптимизировать алгоритм, как преобразовать представление данных в другое и т. Д.

Арсений Мурзенко
источник
12
-1: «CRUD-приложения» - это алгоритмы. Они просто (как правило) просто. Здесь нет "благородного значения".
S.Lott
2
и исходный код - ваш единственный канал связи с компьютером, который делает именно то , что вы ему говорите (и почти никогда не делаете то, что вы хотите)
трещотка урод
5
Удивительно, насколько хорош рынок для очистки приложений CRUDdy, инженерные команды которых игнорировали (или никогда не изучали) основы алгоритмов.
JasonTrue
2
@ S.Lott: «Приложения CRUD - это алгоритмы» аналогичны «Я Америка». ;)
Джим Г.
1
@JimG: Как говорит Стивен Колберт: «Я Америка, и вы тоже». Приложения CRUD содержат, основаны, включают в себя, являются реализациями, являются реализациями, воплощают, отражают алгоритмы. Вы только жаловались, не предлагая конкретного предлога. Что сделало бы вас счастливее?
S.Lott
16

Я думаю, что вопросы об алгоритмах в интервью являются одним из основных способов, которыми компании пытаются судить о понимании кандидата основ компьютерных наук. Хотя это не единственная важная область навыков для профессионального программиста, это одна из основных компетенций хорошего программиста.

Я думаю, что причина, по которой многие крупные компании делают акцент на фундаментальных принципах КС в процессе собеседования, заключается в том, что это основной навык, который развивается в наименьшей степени после окончания учебы и перехода на работу. Практические навыки программирования, навыки проектирования, практики разработки программного обеспечения и тому подобное - это все, что в первую очередь развивается на основе опыта, в то время как основы вашего CS в первую очередь разрабатываются в процессе обучения.

Что касается практики разработки алгоритмов, Стив Йегге рекомендует «Руководство по разработке алгоритмов», предложенное Скиеной, в своем превосходном руководстве по проведению интервью как программисту .

Андрей Б
источник
4
+1: языки программирования, фреймворки, операционная система, редакторы, наборы инструментов, все они приходят и уходят, но знание того, как эффективно решать проблемы, зависит от знания основ структур данных и алгоритмов. Эти вещи остаются с нами всегда.
Адам Кроссленд
«Что касается практики разработки алгоритмов, Стив Йегге рекомендует Скиена« Руководство по разработке алгоритмов »в своем великолепном руководстве по проведению собеседований в качестве программиста». Извините, но это может быть неприменимо к человеку, который задал этот вопрос, так как он оказался аспирантом. Google / MS перешел от Skiena (для аспирантов) к заданию вопросов, которые появились на международных конкурсах студенческого программирования. (Это я точно знаю из анекдотического опыта). Книга Скиены все еще используется - но главным образом для кандидатов уровня бакалавра.
user396089
Что касается вопросов, которые появляются в соревнованиях по программированию - вы в значительной степени заскучали, если вы не видели вопрос раньше (если ваш IQ также не на 3 SD больше нормального)
user396089
11

Как успешный разработчик программного обеспечения, который самоучка и только несколько курсов по информатике в колледже, я скажу, что самые большие проблемы, стоящие сегодня перед бизнесом, - это не способность всех их программистов написать алгоритм сортировки пузырьков наиболее эффективным способом. возможный. Истинные проблемы, с которыми сталкиваются предприятия:

  • Разработчики, которые не могут быстро учиться и адаптироваться к новым доменам

  • Разработчики, которые не могут эффективно взаимодействовать с клиентами или заинтересованными сторонами

  • Разработчики, которые не могут переоценить неправильные или плохо продуманные требования бизнеса

  • Разработчики, которые не понимают, как тщательно тестировать свой код и функции

  • Разработчики, которые не могут своевременно представить значимые оценки

  • Разработчики, которые не могут создать ясную и краткую документацию

  • Разработчики, которые не могут самостоятельно начать или взять на себя ответственность за ситуацию

В девяти случаях из десяти я держу пари, что почти во всех случаях, когда разработчик терпит неудачу в компании, потому что он безнадежно терпит неудачу в одном из вышеперечисленных качеств. Забудьте о Google и Facebook, они являются исключительными случаями и имеют законную потребность в людях, которые глубоко понимают информатику.

Реальный бизнес, однако, не борется со сложностями компьютерной науки, он борется со сложностями человечества. Проблема в том, что ДЕЙСТВИТЕЛЬНО сложно проверить на вышеуказанные качества. Большую часть времени вы должны судить людей по этим качествам, основываясь на вашей интуиции. Это сложно, если у вас нет хороших навыков и интуиции, гораздо проще проверить знания алгоритма.

maple_shaft
источник
+1 Обычным и не похожим на Google компаниям нужны люди с хорошими деловыми навыками, и прежде всего для понимания того, как изобретать / применять / управлять / модифицировать процессы. Это не ошибка, что Google-подобные компании не вынашивали гибкое движение, потому что компьютерные науки не решают проблемы бизнеса.
С.Робинс
10

Я лично вижу «стандартные» алгоритмы и структуры данных как часть словаря программиста. И многие из практических проблем, с которыми вы сталкиваетесь как программист, часто имеют решение, которое (хотя бы частично) выражается в этом словаре.

Наличие этого словаря в вашем распоряжении избавляет вас от необходимости придумывать свои «собственные» решения (так сказать, заново изобретать колесо), позволяя вам работать умнее и часто быстрее.

«Кажется, я не заинтересован в решении, казалось бы, слишком сложных проблем, встречающихся в большинстве учебников или сайтов»

«Мне очень трудно запомнить и использовать их позже»

Заставь себя завершить их. Вы будете благодарить себя позже. Даже если вы не помните их в деталях (хотя с достаточной практикой вы наверняка это сделаете), возможность сказать: «Я помню, как я решал нечто похожее с использованием алгоритма X или структуры данных Y», очень поможет вам. Даже если это требует от вас поиска деталей и обновления памяти.

Барт
источник
+1 для структур данных. Они другая половина алгоритмической монеты.
Спенсер Рэтбун
9

Хотя вы не можете быть хорошим программистом, не зная своих алгоритмов, несправедливо держать в стороне другие аспекты профессии программиста. Например, строгая дисциплина и хорошее владение вашим родным языком по крайней мере так же важны для хорошего программиста, как и ваши знания алгоритмов. Не следует также недооценивать важность понимания ваших основных инструментов, таких как языки программирования, системы контроля версий, среды тестирования и так далее.

Однако, когда дело доходит до собеседований, измерение вашего понимания алгоритмов намного проще, чем измерение ваших других способностей, связанных с работой программистом. Вот почему интервьюеры часто концентрируются на вопросе об алгоритмах и обращают пристальное внимание на то, как вы объясняете их во время интервью. Не потому, что другие вещи менее важны, а потому, что трудно оценить эти вещи за 30 минут, выделенных для интервью.

dasblinkenlight
источник
1
+1 Прекрасный ответ! Проще проверить на знание алгоритма.
maple_shaft
«Ваши алгоритмы» - самоучка. Есть ли где-нибудь источник или список, в котором говорится, что эти общие алгоритмы должен знать каждый программист? Я хотел бы прочитать их. Благодарность!
Ominus
2
@Ominus Несмотря на то, что не существует общего консенсуса в отношении «джентльменского списка» алгоритмов, в большинстве случаев он будет включать в себя поиск, сортировку, обход структур данных, в которых отсутствует пространственная непрерывность (связанные списки, двоичные деревья и т. Д.), И элементарный (неверный) приложения рекурсии (рекурсивный факториал, последовательность Фибоначчи и т. д.)
dasblinkenlight
@ Ominus - я тоже самоучка, но я думаю, что «Введение в алгоритмы» - CLRS - хороший способ познакомиться с этой областью. Книга Шиены "Руководство по разработке алгоритмов" тоже хороша.
Tod
5

Да, программирование в основном связано с алгоритмами.

Но, может быть, не в том смысле, что вы думаете.

У меня создается впечатление, что мы все используем разные определения алгоритма. Если честно, на этот вопрос сложно ответить, потому что алгоритм - это неопределенный термин. Я буду использовать определение Википедии, чтобы ответить на этот вопрос:

Набор правил, который точно определяет последовательность операций.

Это сердце и душа программирования. Когда вы пишете любой код, вы просто реализуете алгоритм. Если вы пишете некоторые приложения CRUD, вы реализуете простой алгоритм. Способность придумать алгоритм для решения проблемы - вот что такое программирование. Остальные - просто детали.

Я не согласен с предыдущим постером, в котором говорилось, что глубокое понимание языка важнее понимания алгоритмов. Любой хороший программист должен уметь глубоко изучать язык, но без алгоритмов вы не сможете придумать какой-либо код самостоятельно.

Кейси Паттон
источник
С другой стороны, в математике сердце и душа могут быть алгоритмами, однако для программирования это нечто другое. Вы можете писать программное обеспечение без использования алгоритмов как таковых (возможно, не хорошего программного обеспечения), но вы не можете писать программное обеспечение без логики и абстрактного мышления. В основе, однако, речь идет о решении проблем. Поиск решения - это алгоритмический процесс, но само решение не обязательно является алгоритмом.
С.Робинс
4

Ответ полностью зависит от работы, которую вы выполняете. Некоторые поля особенно сосредоточены на алгоритмах, чем другие. Говоря с этой запиской, я имел удовольствие побеседовать с Amazon несколько раз. Несмотря на то, что позиция не имеет ничего общего с этими сложными алгоритмами, я был на гриле о том, как сделать задачу амортизированной постоянным временем.

То, что обеспечивает глубокое понимание алгоритмов, является доказательством того, что ваш потенциальный работодатель является подходящим решением проблем. Это не совсем хороший показатель (IMO) хорошего сотрудника, но некоторые работодатели используют его для проверки. Если вы подаете заявку на должность, требующую ученой степени, от вас ожидают более строгого обоснования алгоритмов.

Что (IMO) очень полезно на практике, так это не запоминать конкретные алгоритмы, а благодаря пониманию того, как работают некоторые алгоритмы, у вас в голове появляется этот маленький самородок, где вы скажете: «Я видел это раньше» или «Я знаю, что я может сделать это лучше ", что приведет к небольшому количеству исследований по решению вашей проблемы.

установка
источник
+1 за разговоры о приеме на работу для аспирантов. Некоторые компании гораздо более суетливы, когда нанимают аспирантов, чем студентов. Но, чтобы быть справедливым по отношению к ним, аспиранты также лучше оплачиваются и, как правило, набираются на более высоком уровне внутри страны.
user396089
1

Я всегда думаю, что программирование в большей степени зависит от данных, чем от алгоритмов ... но тогда какая польза от данных, если вы ничего с ними не делаете ... все эти манипуляции являются алгоритмами. На самом деле, да, программирование в значительной степени полностью основано на алгоритме.

Это может не выглядеть как математика, и большая часть алгоритмической работы, которую вы выполняете изо дня в день, очень проста, например, отправка данных между GUI и программой, но это также считается алгоритмом. Вставка элемента в список - это стандартный алгоритм вставки, который имеет свои собственные проблемы, такие как производительность и манипуляции со структурой списка.

gbjbaanb
источник
1

Только программисты, которые работают в этих компаниях, могут действительно ответить на ваш вопрос. Виды алгоритмов, о которых говорилось, например, «Введение в алгоритмы», вероятно, сыграли свою роль в 0,01% моей жизни в программировании за последние 25 лет. Когда мне нужна структура данных или сортировка, обычно поставляемые библиотеки или фреймворки имеют то, что мне нужно. Когда мне нужен супер быстрый БПФ, я нахожу что-то вроде библиотеки Intel Math, а не пишу сам. Тем не менее, я могу понять, что то, что они делают в Google, отличается от того, что я делал в своей карьере. Книга Скиены «Руководство по разработке алгоритмов» открыла глаза благодаря рассказам о войне. Вы можете сказать, что он использует алгоритмы в своей работе много.

По моему опыту работы в качестве независимого консультанта по программированию, успех пришел из трех вещей: 1. Эффективное общение с клиентами. 2. Написание работающего кода. 3. Управление Сложностью

Делать только цифры 1 и 2 недостаточно. Если код не поддерживается (кем-то кроме программистов, которые его написали), он обречен.

Номер 3 - самый сложный навык программирования для освоения. Требуется продумать архитектуру, дизайн и кодирование. Требует овладения рефакторингом. Это требует понимания принципов SOLID / DRY. Если бы мне пришлось нанимать программиста, который читал «Введение в алгоритмы» и посвятил себя овладению им, или того, кто читал «Прагматичный программист» и посвятил себя тому, чтобы быть им, я бы нанимал последнего каждый раз. (Не то чтобы они должны быть взаимоисключающими).

пройдоха
источник
1

Да.

Информатика в основном алгоритмы (в процентах).

Нет.

Но это «Наука» компьютеров. Наиболее распространенным применением компьютерных наук является разработка программного обеспечения. Программная инженерия в основном не алгоритмы. В основном это искусство творчества, стремление к совершенству и сосредоточено вокруг положительного влияния на жизнь реальных людей, которые существуют сегодня. Хотя компьютерные науки могут иметь некоторые из тех же мотивов, это далеко от разработки программного обеспечения.

Спросите штатного профессора в крупном Университете информатики, что самое важное в программировании, чтобы понять, и они, вероятно, скажут вам «алгоритмы и структуры данных»

Спросите старшего разработчика в крупной софтверной компании, что самое важное в программировании, чтобы понять, и они, вероятно, скажут вам, «учиться радовать клиентов» (подразумевается, что это понимание гибкости, мышления как клиента, своевременной доставки и постоянно, заставляя вещи работать и т. д.)

Может показаться, что это семантика, но, насколько я понимаю, эти два понятия заметно отличаются как в практике, так и в теории.

Пол Хазен
источник
1

Если бы мне пришлось выбрать одну вещь в информатике как самую важную ее часть, я бы выбрал абстракции , а не алгоритмы.

Томас Эдинг
источник
1

В компьютерных науках те концепции, которые вы изучаете, будут бесполезны до тех пор, пока вы их не покажете. Проблема представляет собой основную проблему, которую необходимо решить, поэтому алгоритм представляет собой краткое планирование того, как эта проблема будет решаться в целом. Поэтому это вызывает серьезную обеспокоенность в мире компьютерных наук.

Я думаю, что почти каждому аспекту информатики нужен алгоритм. Позвольте мне показать вам следующий список будет включать различные области информатики и какие алгоритмы они используют.

Automata

Конструкция Powerset. Алгоритм преобразования недетерминированного автомата в детерминированный автомат. Алгоритм Тодда-Кокстера. Процедура генерации смежных классов.

Искусственный интеллект

Альфа-бета. Альфа макс плюс бета мин. Широко используется в настольных играх. Ant-алгоритмы. Оптимизация муравьиных колоний - это набор алгоритмов, вдохновленный поведением муравьев для решения проблемы, поиска оптимального пути между двумя точками. DE (Дифференциальная эволюция). Решить проблему полиномиальной подгонки Чебышева. Признание саркастических предложений под надзором в онлайн-обзорах продуктов. Алгоритм, который распознает сакармы или иронию в твите или онлайн-документе. Такой алгоритм будет существенным для программирования роботов-гуманоидов.

Компьютерное зрение

Воплощение. Представьте изображение или видео меньшим. Подсчет объектов на изображении . Использует алгоритм маркировки подключенного компонента, чтобы сначала пометить каждый объект, а затем подсчитать объекты. Алгоритм О'Кэрролла. Исходя из математического преобразования зрения насекомых, этот алгоритм оценивает, как обойти избегание объектов.

Генетические алгоритмы

Они используют три оператора. выбор (выберите решение), воспроизведение (используйте выбранные решения для создания других), замена (замените решение, если лучше).

Фитнес пропорциональный выбор. Также известна как выбор колеса рулетки, это функция, используемая для выбора решений. Усечение выбора. Еще один метод выбора решений, заказанных по фитнесу. Выбор турнира. Выберите лучшее решение по виду турнира. Стохастическая универсальная выборка. Индивидуумы сопоставляются с непрерывными сегментами линии, так что сегмент каждого индивидуума по размеру равен его физической форме точно так же, как при выборе колеса рулетки.

Нейронные сети

Сеть Хопфилда. Рекуррентная искусственная нейронная сеть, служащая адресно-адресной системой памяти с двоичными пороговыми единицами. Они сходятся к стабильному состоянию. Обратное распространение. Контролируемая методика обучения используется для обучения искусственным нейронным сетям. Самоорганизующаяся карта (карта Кохонена). Нейронные сети обучаются с использованием обучения без контроля для получения низкоразмерного (2D, 3D) представления обучающих образцов. Хорошо подходит для визуализации многомерных данных.

Биоинформатика

Needleman-Wunsch. Выполняет глобальное выравнивание для двух последовательностей, для белковых или нуклеотидных последовательностей. Smith-Waterman. Вариация Рукоделия-Вунша.

компрессия

Алгоритмы сжатия без потерь

Преобразование Барроуза-Уилера. Предварительная обработка полезна для улучшения сжатия без потерь. Выкачивает. Сжатие данных используется ZIP. Дельта-кодирование. Помощь в сжатии данных, в которых часто встречаются последовательные данные. Инкрементное кодирование. Дельта-кодирование применяется к последовательностям строк. LZW. (Лемпель-Зив-Велч). Преемник LZ78. Создает таблицу перевода из данных для сжатия. Используется в графическом формате GIF. LZ77 и 78. Основа дальнейших вариаций LZ (LZW, LZSS, ...). Они оба словарные кодеры. LZMA. Коротко для цепочки-алгоритма Лемпеля-Зива-Маркова. LZO. Алгоритм сжатия данных, ориентированный на скорость. PPMПрогноз по частичному сопоставлению. Адаптивная методика статистического сжатия данных на основе контекстного моделирования и прогнозирования. Кодирование Шеннона-Фано. Создает префиксные коды на основе набора символов и их вероятностей. Усеченный двоичный файл. Энтропийное кодирование обычно используется для равномерного распределения вероятностей с конечным алфавитом. Улучшить двоичное кодирование. Длина кодирования. Первичное сжатие, которое заменяет последовательность одного и того же кода на количество вхождений. Sequitur. Инкрементальный вывод грамматики на строку. EZW (встроенный вейвлет Zerotree). Прогрессивное кодирование для сжатия изображения в битовый поток с повышением точности. Может быть сжатие с потерями также с лучшими результатами.

Энтропийное кодирование Схема кодирования, которая присваивает коды символам, чтобы согласовать длины кодов с вероятностями символов.

Кодирование Хаффмана. Простое сжатие без потерь с использованием относительных частот символов. Адаптивное кодирование Хаффмана. Метод адаптивного кодирования на основе кодирования Хаффмана. Арифметическое кодирование. Расширенное энтропийное кодирование. Диапазон кодирования. То же, что и арифметическое кодирование, но выглядит немного иначе. Одинарное кодирование. Код, представляющий число n с n единиц, за которыми следует ноль. Элиас дельта, гамма, омега кодирование. Универсальный код, кодирующий натуральные числа. Кодирование Фибоначчи. Универсальный код, который кодирует натуральные числа в двоичные кодовые слова. Кодирование Голомба. Форма энтропийного кодирования, оптимальная для алфавитов, следующих за геометрическими распределениями. Кодирование риса. Форма энтропийного кодирования, оптимальная для алфавитов, следующих за геометрическими распределениями.

Алгоритмы сжатия с потерями

Линейное прогнозирующее кодирование. Сжатие с потерями путем представления спектральной огибающей цифрового сигнала речи в сжатом виде. А-закон алгоритм. Стандартный алгоритм компандирования. Му-закон алгоритм. Стандартный алгоритм сжатия или компоновки аналогового сигнала. Фрактальная компрессия. Метод, используемый для сжатия изображений с использованием фракталов. Преобразование кодирования. Тип сжатия данных для таких данных, как аудиосигналы или фотографические изображения. Векторное квантование. Техника часто используется при сжатии данных с потерями. Вейвлет-сжатие. Форма сжатия данных хорошо подходит для сжатия изображений и аудио.

криптография

Секретный ключ (симметричное шифрование)

Используйте секретный ключ (или пару напрямую связанных ключей) для дешифрования и шифрования.

Расширенный стандарт шифрования (AES) , также известный как Rijndael. Blowfish. Разработан Шнайером как алгоритм общего назначения, предназначенный для замены стареющего DE. Стандарт шифрования данных (DES) , ранее алгоритм DE. IDEA (международный алгоритм шифрования данных) . Ранее IPES (улучшенный PES), еще одна замена для DES. Используется PGP (Pretty Good Privacy). Выполняет преобразования данных, разбитых на блоки, используя ключ. RC4 или ARC4. Потоковый шифр широко используется в таких протоколах, как SSL для интернет-трафика и WEP для беспроводных сетей. Алгоритм крошечного шифрования. Легко реализовать алгоритм блочного шифрования с использованием некоторых формул. PES (Предлагаемый стандарт шифрования). Старое имя для ИДЕИ.

Открытый ключ (асимметричное шифрование)

Используйте пару ключей, обозначенных как открытый ключ и закрытый ключ. Открытый ключ шифрует сообщение, только личный ключ позволяет расшифровать его.

DSA (алгоритм цифровой подписи). Генерация ключей с простыми и случайными числами. Был использован агентствами США, а теперь и общественным достоянием. ElGamal. Основано на Diffie-Hellman, используемом программным обеспечением GNU Privacy Guard, PGP и другими криптографическими системами. ОГА (Ривест, Шамир, Адлеман). Широко используется в протоколах электронной коммерции. Используйте простые числа. Обмен ключами Диффи-Хеллмана (Меркле) (или экспоненциальный обмен ключами). Способ и алгоритм для обмена секретом по незащищенному каналу связи. Используется RSA. NTRUEncrypt. Используйте кольца многочленов с конволюционными умножениями.

Функции дайджеста сообщений

Дайджест сообщения - это код, полученный в результате шифрования строки или данных любой длины, обработанных хеш-функцией.

MD5. Используется для проверки ISO-образов компакт-дисков или DVD-дисков. RIPEMD (Дайджест сообщения оценки примитивов RACE). Основан на принципах MD4 и аналогичен SHA-1. SHA-1 (безопасный алгоритм хеширования 1). Чаще всего используется набор связанных криптографических хеш-функций SHA. Был разработан агентством АНБ. HMAC. аутентификация сообщения с хеш-ключом. Тигр (ТТХ). Обычно используется в хеши Tiger Tree.

Криптография с использованием псевдослучайных чисел . Генераторы случайных чисел

Техники в криптографии

Разделение секретов, Разделение секретов, Разделение ключей, M из N алгоритмов.

Секретная схема обмена Шамира. Это формула, основанная на полиномиальной интерполяции. Секретная схема обмена Блекли. Имеет геометрическую природу, секрет - это точка в м-мерном пространстве.

Другие методы и расшифровка

Сумма подмножества. Учитывая набор целых чисел, любая подмножество сумма равна нулю? Используется в криптографии. Алгоритм Шора. Квантовый алгоритм способен расшифровывать код на основе асимметричных функций, таких как RSA.

Геометрия

Подарочная упаковка. Определение выпуклой оболочки множества точек. Расстояние Гилберта-Джонсона-Керти. Определение наименьшего расстояния между двумя выпуклыми фигурами. Сканирование Грэма. Определение выпуклой оболочки множества точек на плоскости. Пересечение отрезка. Поиск, пересекаются ли линии с алгоритмом стреловидности. Точка в многоугольнике. Проверяет, находится ли заданная точка в заданной. Пересечение Луч / Плоскость. * Пересечение линии / треугольника. * Частный случай пересечения луча / плоскости. Полигонизация неявных поверхностей. Приближаем неявную поверхность с полигональным представлением. Триангуляции.Метод оценки расстояния до точки от углов до других точек, расстояние которых известно.

Графики 3D Surface Tracker Technology. Процесс добавления изображений на стены в видео, в то время как скрытые поверхности принимаются во внимание. Беллмана-Форда. Вычисляет кратчайшие пути во взвешенном графе (где некоторые веса ребер могут быть отрицательными). Алгоритм Дейкстры. Вычисляет кратчайшие пути в графе с неотрицательными весами ребер. Методы возмущений. Алгоритм, который вычисляет локально кратчайшие пути в графе. Флойд-Воршалл. Решает проблему кратчайшего пути для всех пар во взвешенном ориентированном графе. Флойд на велосипеде. Находит циклы в итерациях. Джонсон. Алгоритм кратчайшего пути всех пар в разреженном взвешенном графе. Крускала.Находит минимальное остовное дерево для графа. Прима. Находит минимальное остовное дерево для графа. Также называется алгоритмом DJP , Jarník или Prim – Jarník. * Boruvka. * Находит минимальное остовное дерево для графа. Ford-Фулкерсон. Вычисляет максимальный поток на графике. Эдмондс-Карп. Реализация Форд-Фулкерсон. Неблокирующий переключатель минимального охвата. Для телефонной станции. Вудхаус-Sharp. Находит минимальное остовное дерево для графа. Весна основана. Алгоритм построения графика. Венгерский язык. Алгоритм нахождения идеального соответствия. Алгоритм раскраски. Алгоритм раскраски графа. Ближайший соседНайти ближайшего соседа. Топологическая сортировка. Сортируйте направленный ациклический граф таким образом, чтобы каждый узел был перед всеми узлами, к которым у него есть ребра (согласно направлениям). Алгоритм наименьшего общего предка Тарьяна. Вычислить наименьших общих предков для пар узлов в дереве.

Графика

Алгоритм Брезенхема. Использует переменные решения для построения прямой линии между двумя указанными точками. Пейзаж Нарисуйте трехмерный пейзаж. * Алгоритм линии DDA. * Использует математические операции с плавающей точкой для построения прямой линии между двумя указанными точками. Заливка. Заполняет связанный регион цветом. Восстановление изображения. Восстановление фото, улучшение изображений. Алгоритм линии Сяолин Ву. Линия сглаживания. Алгоритм художника. Обнаруживает видимые части трехмерного пейзажа. Трассировка лучей. Реалистичная визуализация изображений. Фонг затенение. Модель освещения и метод интерполяции в трехмерной компьютерной графике. Гуро затенение.Смоделируйте различные эффекты света и цвета на поверхности трехмерного объекта. Scanline рендеринг. Создает изображение, перемещая воображаемую линию. Глобальное освещение. Учитывает прямое освещение и отражение от других объектов. Интерполяция. Построение новых точек данных, таких как цифровой зум. Resynthesizer. Удалите объект на фотографии и восстановите фон. Используется Photoshop и The Gimp. Ресинтезатор учебник. Алгоритм наклона-перехвата. Это реализация формулы наклона-пересечения для рисования линии. Сплайн-интерполяция. Уменьшает ошибку с феноменом Рунге. Технология 3D Surface Tracker. Добавление изображений или видео на стены в видео, скрытые поверхности принимаются во внимание.

Списки, массивы и деревья

Поиск

Поиск по словарю. Смотрите прогнозный поиск. Алгоритм выбора. Находит k-й по величине элемент в списке. Алгоритм двоичного поиска. Находит элемент в отсортированном списке. Поиск в ширину. Обходит график уровень за уровнем. Поиск в глубину Обходит граф ветку за веткой. Лучший поиск в первую очередь. Обходит график в порядке вероятности важности, используя очередь с приоритетами. Дерево поиска. * Особый случай лучше первого поиска , который использует эвристические методы для повышения скорости. Поиск равномерной стоимости. Поиск по дереву, который находит маршрут с наименьшими затратами, где затраты варьируются. Прогнозный поиск.Бинарный подобный поиск, который определяет величину поискового запроса в сравнении с высокими и низкими значениями в поиске. Хеш-таблица. Свяжите ключи с элементами в несортированной коллекции, чтобы получить их за линейное время. Интерполированный поиск. Смотрите прогнозный поиск.

Сортировка

Двоичное дерево сортирует. Сортировка двоичного дерева, инкрементная, похожая на сортировку вставкой. Bogosort. Неэффективный случайный вид настольной карты. Пузырьковая сортировка. Для каждой пары индексов меняйте позиции, если они вышли из строя. Ковш сортировать. Разделите список на сегменты и отсортируйте их по отдельности. Обобщает голубиный сорт. Коктейльная сортировка (или двунаправленный пузырь, шейкер, пульсация, челнок, сортировка по счастливому часу). Вариация сортировки пузырьков, которая сортирует в обоих направлениях каждый проход по списку. Расческа Эффективное изменение пузырьковой сортировки, которое устраняет «черепахи», небольшие значения в конце списка и использует пробелы между значениями. Подсчет сортировки.Он использует диапазон чисел в списке A для создания массива B этой длины. Индексы в B используются для подсчета, сколько элементов в A имеют значение меньше, чем i. Сортировка гномов. Или интроспективный вид. Он начинается в быстрой сортировке и переключается в heapsort на определенном уровне рекурсии. Сортировка слиянием.Аналогично сортировке вставкой, за исключением того, что перемещение элемента на его место выполняется серией перестановок, как при пузырьковой сортировке. Пирамидальная сортировка. Преобразуйте список в кучу, продолжайте удалять самый большой элемент из кучи и добавляйте его в конец списка. Вид вставки. Определите место текущего элемента в списке отсортированных и вставьте его туда. Introsort. Сортируйте первую и вторую половину списка отдельно, затем объединяйте отсортированные списки. Блин сортировать. Обратные элементы некоторого префикса последовательности. Голубиная дыра. Заполните пустой массив всеми элементами массива для сортировки по порядку. Почтальон Иерархический вариант сортировки ведра, используемый почтовыми отделениями. Выберите самый маленький из оставшихся элементов, добавьте его в конец отсортированного списка. Оболочка сортировка.Quicksort. Разделите список на два, причем все элементы в первом списке располагаются перед всеми элементами во втором списке .; затем отсортируйте два списка. Часто метод выбора. Корень сортировки. Сортирует ключи, связанные с элементами, или целые числа путем обработки цифр. Выбор сортировки. Улучшает сортировку вставок с использованием пробелов между значениями. Плавная сортировка. Смотри heapsort. Стохастическая сортировка. Смотрите богосорт.

и многое другое ...

Читранк Диксит
источник
0

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

Да, информатика это все об алгоритмах. Ну ... на самом деле это немного вводит в заблуждение, потому что в информатике есть много аспектов, поэтому я перефразирую. Информатика в том виде, в каком она применяется в рабочем мире, - это преимущественно алгоритмы. Такие компании, как Google, Facebook и все эти безумные места на Уолл-стрит, нанимающие физиков и разработчиков, хотят, чтобы очень сложные задачи сводились к простой форме, которая сама по себе требует глубокого понимания математики и разработки алгоритмов.

Нет, программирование - это не только алгоритмы. Программирование - это получение спецификаций и их преобразование в код, который можно скомпилировать для исполнения.

Дополнительная часть ответа: разработка программного обеспечения - это не программирование, и все же многие, кажется, путают термины и используют их взаимозаменяемо. Программирование - это просто функция или метод, возможно, более крупного процесса разработки программного обеспечения. Разумеется, разработка программного обеспечения - это не только алгоритмы, а решение проблем с программным обеспечением и применение надежных бизнес-совместимых процессов, позволяющих эффективно решать проблемы. В то время как процессы разработки программного обеспечения - и даже программировать себя - может быть алгоритмические процессы в своей природе, это не то же самое как об алгоритмах.

S.Robins
источник