#алгоритм
Какие Алгоритмы Стоит Изучать? Вот, чем я руководствовался, задавая этот вопрос: Почти любой работодатель хочет увидеть хорошую алгоритмическую "базу". Так же эта "база" нужна и на практике. Но, какой должна быть эта "база"? Какие алгоритмы изучать? Да, можно набросится на бесконечное множество всех алгоритмов и изучать их. Но их слишком много,что бы реализовывать их программно. Поэтому, на реализацию забивать приходится. Мне этот путь не нравится. Думаю не только мне. Попытался найти в интернете подобные списки, но нашел лишь советы людей - "Кто знает, что вам пригодится?", "мне хватает знания сортировки пузырьком" и так далее. Читать разнообразные книжки, такие, как Кнута.. Там опять же много алгоритмов. Пробежаться и забыть не хочется- хочется, что бы знания остались. А осваивать все-во первых долго, во вторых многие из этих алгоритмов представляют лишь теоретический интерес и на практике не применяются.
Ответы
Ответ 1
Полный список, конечно, составить невозможно, поэтому пробегусь по тому, что мне кажется важным. Сложность алгоритмов. Вы должны знать O-нотацию и уметь сходу оценивать O-сложность алгоритма хотя бы для простых случаев. Структуры данных! Не только простые структуры, типа массива, но и сложные: вы должны представлять себе, что происходит при добавлении элемента в красно-чёрное дерево (std::map из C++), и понимать, почему добавление в него быстрое. Сортировки. Простые (надо знать и понимать недостатки и достоинства пузырьковой сортировки) и сложные (понимать хотя бы quicksort, и уметь на пальцах объяснить его идею). Алгоритмы работы с деревьями: например, различные их обходы. Поиск в графе: в ширину и в глубину, алгоритм Дейкстры и A*. Бинарный поиск в отсортированном массиве, конечно. Математика! Матричные алгоритмы (детерминант, решение системы линейных уравнений не через детерминанты), преобразование между системами счисления (включая смешанные). Работа с рекуррентными последовательностями: вычисление степени и n-ого числа Фибоначчи за логарифмическое время. Мне ещё пригодились когда-то нахождение выпуклой оболочки и векторные трюки (типа расстояния между скрещивающимися прямыми через векторное произведение), но они нужны всё-таки реже. Базы данных важны. Вы должны представлять себе, как выполняются JOIN'ы и какая «стоимость» материализации того или иного VIEW. Вы должны понимать, как строятся индексы, сколько они «стоят», и как они помогают. (В терминах O-нотации.) Анализ игр может пригодится. Например, построение множества выигрышных позиций «с хвоста».Ответ 2
Большинство работодателей которых интересует "алгоритмическая база" на самом деле были латентными извращенцами, которые хотели показать, давая вам кривую олимпиадную задачу, как необозримо круты они, и как малы и латексны все вокруг)) С вопросами оплаты и карьерного роста потом тоже были проблемы. На самом деле львиную долю народа интересует в нанимаемых программистах три вещи: умение быстро доучиваться и творчески решать задачи; умение писать качественный код - то есть не содержащий багов, не содержащий ошибок в безопасности, не содержащих глупых ошибок, которые снижают быстродействие; умение приспосабливать к работе в команде. Алгоритмы - хорошо. Но общее понимание, что такое сортировка, что такое индексирование, как лучше хранить данные, чтоб это было оптимально по затратам и доступности, как лучше построить цикл (какие действия нужны внутри, а какие можно вынести вне), какие могут быть ошибки в данном коде, и как их нужно экранировать и обработать. Какие данные могут подсунуть пользователи на вход по дури, а какие по злому умыслу - и как максимально обезопасить код от ошибок внешних данных. Вот это с точки зрения хорошего программиста важнее. Алгоритмы как таковые вам понадобятся в трех случаях: вы трудоустраиваетесь в иностранную контору, где анализируется квалификация вцелом - но тесты обычно построены так, чтоб понимать, понимаете ли вы в общем о чем это - ну и дочитали ли вы Кнута, Седжвика, Вирта, Страуструпа до конца); вы трудоустраиваетесь в контору, которая пишет низкоуровневый софт, вот тут как раз вы можете нарваться на то, что многие из алгоритмов, которые "представляют лишь теоретический интерес и на практике не применяются", ещё живи и здравствуют; вы устраиваетесь в контору, которая пишет софт для моделирования, графики и 3Д движки)) Кстати, как утверждают знакомые, работающие в последней категории знание физики вцелом, предметной области, а также алгебры, геометрии, матанализа и умение щелкать пятиэтажые уравнения (причем правильно) - им нужно гораздо чаще, чем Кнут. Диверсификация знаний и навыков, как по мне, так же полезна, как и доходов ;)Ответ 3
По совету @VladD преобразовал комментарий к его ответу тоже в ответ. Я бы добавил: Понимание компиляции-интерпретации-линковки (тут же (кроме линковки) сидят регулярные выражения и тоже надо бы понимать как их алгоритмы устроены). Представление о работе с дисками (теперь еще и с флэшем). В этом плане полезно знать как работает внешняя сортировка. Еще на эту же тему - когда индексный доступ к данным в базе полезен, а когда наоборот, только замедляет выполнение запроса. Ну и как LAN (TCP/UDP/ICMP и т.п.) работает. Тут в первую очередь надо познакомится с сокетами. Еще одна модная теперь тема это потоки (threads) и соответственно синхронизация доступа к памяти. Тут же вспомним о процессах и алгоритмах межпроцессного взаимодействия. К алгоритмам напрямую не относится, но желательны определенные познания в области современных архитектур компьютеров. Прежде всего конвейеризация исполнения команд, предвыборка команд и данных, внеочередное исполнение, кэши процессора и проблема когерентности кэшей в SMP и NUMA архитектурах, порядок величин времени задержек при обращении к кэшу и RAM, а также организация виртуальной памяти (разделение функций между аппаратурой (MMU, TLB) и ОС), принципы обработки прерываний (тоже, что делает железо, а что ОС). (если еще что-то хорошее (или о чем спрашивали меня или спрашивал я) вспомню, то буду добавлять сюда)
Комментариев нет:
Отправить комментарий