Эти термины использовались в моем учебнике по структурам данных, но объяснение было очень кратким и неясным. Я думаю, что ему есть что знать, с каким знанием алгоритм на каждом этапе вычислений.
PS - Пожалуйста, не ссылайтесь на страницу wikipedia, я уже прочитал ее и все еще ищу уточнения. Объяснение, как будто мне двенадцать лет и/или пример, было бы намного более полезным.
Что именно вы не понимаете при просмотре страницы Википедии?
В информатике онлайн-алгоритм - это тот, который может обрабатывать его вводятся по частям последовательно, т.е. в том порядке, в котором вход подается в алгоритм, без ввода всего входа доступный с самого начала. Напротив, предоставляется автономный алгоритм все данные задачи с самого начала и требуется для вывода ответ, который решает проблему. (Например, сортировка сортировки требует, чтобы весь список был указан, прежде чем он сможет его сортировать, в то время как inserting сортировать нет.)
Позвольте мне остановиться выше:
В автономном алгоритме требуется вся информация перед запуском алгоритма. В примере Википедии сортировка сортировки отключена, так как шаг 1 - Find the minimum value in the list. Для этого вам необходимо иметь весь список - иначе , как вы могли бы узнать, что такое минимальное значение? Вы не можете.
Вставка сортировки, напротив, находится в режиме онлайн, потому что ей не нужно ничего знать о том, какие значения будут сортироваться, и запрашивается информация ПОКАЖЕТ, когда алгоритм запущен. Проще говоря, он может захватывать новые значения на каждой итерации.
Подумайте о следующих примерах (для четырехлетних детей!). Дэвид просит вас решить две проблемы.
В первой проблеме он говорит:
"Я собираюсь дать вам два шара разных масс, и вам нужно бросьте их в то же время с башни.. просто чтобы убедиться, что Галилео был прав. Вы не можете использовать часы, мы просто увидим это."
Если бы я дал вам только один мяч, вы, вероятно, посмотрели бы на меня и задались вопросом, что вы должны делать. В конце концов, инструкции были довольно ясными. Вам нужны оба шара в начале проблемы. Это алгоритм офлайн.
Для второй проблемы Дэвид говорит
"Ладно, все прошло хорошо, но теперь мне нужно, чтобы вы пошли вперед и пару шаров по полю".
Я иду вперед и даю вам первый мяч. Вы пинаете его. Затем я даю вам второй мяч, и вы это пинаете. Я мог бы также дать вам третий и четвертый мяч (без вас, даже зная, что я собираюсь отдать их вам). Это пример алгоритма онлайн. На самом деле, вы можете бить шары весь день.
Надеюсь, это было ясно: D
Онлайн-алгоритм обрабатывает входные данные только по частям и не знает о фактическом размере ввода в начале алгоритма.
Часто используемым примером является планирование: у вас есть набор машин и неизвестная рабочая нагрузка. Каждая машина имеет определенную скорость. Вы хотите как можно быстрее очистить рабочую нагрузку. Но так как вы не знаете все входы с самого начала (вы можете часто видеть только следующее в очереди), вы можете только оценить, какая машина лучше всего подходит для текущего ввода. Это может привести к неоптимальному распределению рабочей нагрузки, поскольку вы не можете делать какие-либо предположения о своих входных данных.
С другой стороны, автономный алгоритм работает только с полными входными данными. Вся рабочая нагрузка должна быть известна до того, как алгоритм начнет обрабатывать данные.
Workload: 1. Unit (Weight: 1) 2. Unit (Weight: 1) 3. Unit (Weight: 3) Machines: 1. Machine (1 weight/hour) 2. Machine (2 weights/hour) Possible result (Online): 1. Unit -> 2. Machine // 2. Machine has now a workload of 30 minutes 2. Unit -> 2. Machine // 2. Machine has now a workload of one hour either 3. Unit -> 1. Machine // 1. Machine has now a workload of three hours or 3. Unit -> 2. Machine // 1. Machine has now a workload of 2.5 hours ==> the work is done after 2.5 hours Possible result (Offline): 1. Unit -> 1. Machine // 1. Machine has now a workload of one hour 2. Unit -> 1. Machine // 1. Machine has now a workload of two hours 3. Unit -> 2. Machine // 2. Machine has now a workload of 1.5 hours ==> the work is done after 2 hours
Обратите внимание, что лучший результат в автономном алгоритме возможен только потому, что мы не используем лучшую машину с самого начала. Мы уже знаем, что будет тяжелый блок (блок 3), поэтому этот блок должен обрабатываться самой быстрой машиной.
Автономный алгоритм знает все о своих входных данных в момент его вызова. С другой стороны, онлайн-алгоритм может получить детали или все его входные данные во время работы.
алгоритм называется онлайн, если он не знать данные, которые он будет выполнять на заранее. В автономном алгоритме можно увидеть все данные заранее.
Он-лайн алгоритм - это тот, который получает последовательность запросов и выполняет немедленное действие в ответ на каждый запрос.
Напротив, автономный алгоритм выполняет действие после выполнения всех запросов.
Этот документ Ричарда Карпа дает больше информации о онлайновых автономных алгоритмах.
Мы можем различать автономные и онлайн-алгоритмы на основе доступности входов до обработки алгоритма.
Offline Algorithm: Вся входная информация доступна для алгоритма и обрабатывается одновременно алгоритмом. С полным набором входных данных алгоритм находит способ эффективно обрабатывать входы и получать оптимальное решение.
Онлайн-алгоритм: Входы поступают на лету, то есть вся входная информация недоступна для алгоритма одновременно, а часть по частям как последовательность или по времени. При наличии ввода алгоритм должен принять немедленное решение без каких-либо знаний о будущей входной информации. В этом процессе алгоритм создает последовательность решений, которые будут влиять на конечное качество ее общей производительности.
Например: Маршрутизация в сети связи:
Пакеты данных из разных источников поступают на ближайший маршрутизатор. С маршрутизатором подключено более одной линии связи. Когда новый пакет данных поступает на маршрутизатор, маршрутизатор должен немедленно решить, к какой ссылке должен быть отправлен пакет данных. (Предположим, что все ссылки перенаправлены в пункт назначения, все полосы пропускания каналов одинаковы, все ссылки являются частью кратчайшего пути к месту назначения). Здесь задача состоит в том, чтобы назначить каждый входящий пакет данных одной из ссылок, не зная будущих пакетов данных таким образом, чтобы загрузка каждой ссылки была сбалансирована. Никакие ссылки не должны быть перегружены. Это проблема балансировки нагрузки.
Здесь планировщик, реализованный в маршрутизаторе, не имеет представления о будущих пакетах данных, но он должен принять решение о планировании для каждого входящего пакета данных. В отличие от него автономный планировщик имеет полное знание всех входящих пакетов данных, тогда он эффективно назначает пакеты данных различным ссылкам и может оптимально сбалансировать нагрузку между различными ссылками.
Проблема с Cache Miss: В компьютерной системе кеш - это блок памяти, используемый для предотвращения несоответствия скорости между более быстрым процессором и самой медленной первичной памятью. Цель использования кеша состоит в том, чтобы минимизировать среднее время доступа, сохраняя некоторые часто просматриваемые страницы в кеше. Предполагается, что эти страницы могут быть запрошены процессором в ближайшем будущем. Как правило, когда запрос страницы обрабатывается процессором, страница выводится из первичной или вторичной памяти, а копия страницы хранится в кэш-памяти. Предположим, что кеш заполнен, тогда алгоритм, реализованный в кеше, должен принять немедленное решение о замене блока кэша без знания будущих запросов страницы. Возникает вопрос: какой блок кеша нужно заменить? (В худшем случае может случиться, что вы замените блок кэша и в самый следующий момент - запрос процессора для замещенного блока кэша). Таким образом, алгоритм должен быть сконструирован таким образом, чтобы он принимал немедленное решение о поступлении входящего запроса без предварительного знания всей последовательности запросов. Этот тип алгоритмов известен как АЛГОРИТМ ONLINE