| dbo:abstract
|
- في علم الحاسوب، الخوارزمية الفورية (online algorithm) هي التي تقوم بمعالجة المدخلات (أو البيانات) عن طريق إدراجها عنصر تلو الأخر بطريقة تسلسلية، أي أن ترتيب المدخلات يكون على حسب ظهورها بشكل فوري إلى الخوارزمية، دون أن تكون جميع المدخلات متاحة منذ البداية. على النقيض من ذلك، يتم إعطاء الخوارزمية الغير فورية مدخلات المشكلة بأكملها من البداية، وعلى الخوارزمية أن تجد الحل المناسب للمشكلة الكاملة. في أبحاث العمليات، يسمى المجال الذي يتم فيه دراسة وتطوير الخوارزميات . لنأخذ على سبيل المقارنة خوارزميتين الترتيب بالإنتقاء والإدراج: الترتيب بالانتقاء يوجد العنصر الأقل قيمة من الباقي الغير المصنف ويضعه في أول القائمة، هذا الأمر يتطلب الوصول إلى جميع العناصر بأكملها؛ مما يجعل هذه الخوارزمية غير فورية. من ناحية أخرى، الترتيب بالإدراج يأخذ بعين الاعتبار عنصر واحد فقط في كل تكرار. وفي كل تكرار، الخوارزمية تزيل عنصرًا واحدًا من البيانات المتاحة وتجد الموقع الذي ينتمي إليه ضمن القائمة المصنفة. وبذلك الخوارزمية تنتج حلاً جزئيًا دون النظر إلى العناصر المستقبلية في كل تكرار، مما يجعل هذه الخوارزمية فورية. لاحظ أن الترتيب بالإدراج يعطي النتيجة المثلى، أي قائمة عناصر مرتبة بشكل صحيح تماماً. ولكن بالنسبة للعديد من المسائل الرياضية، لا يمكن أن تجاري الخوارزميات الفورية أداء الخوارزميات الغير فورية. إذا كانت النسبة بين أداء الخوارزمية الفورية ونظيرتها الغير الفورية (المثلى) محدودة بثابت، فإن الخوارزمية الفورية تعتبر تنافسية. ليس لكل خوارمية غير فورية نظير فعال (تنافسي) فوري. (ar)
- Ein Online-Algorithmus ist ein Lösungsverfahren für Probleme, bei denen zuBeginn des Berechnungsvorgangs nicht alle Eingabedaten verfügbar sind. Bei vielen algorithmisch lösbaren Problemen in der Informatik sind die vollständigen Eingabedaten vor der Ausführung des jeweiligen Algorithmus bekannt. Anhand dieser Daten wird eine Lösung berechnet und ausgegeben. Solche Probleme werden Offline-Probleme genannt. Bei Online-Problemen hingegen werden die Eingabedaten zur Zeit der Ausführung des Algorithmus laufend ergänzt. Anders formuliert: Bestimmte Informationen stehen erst dann zur Verfügung, wenn bestimmte andere Daten bereits vorliegen – und können auch erst dann zur Lösung des Problems berücksichtigt werden. Der Algorithmus kann keine Annahmen über die vollständigen Daten treffen. Wesentlich ist, dass der Algorithmus schon Entscheidungen treffen muss, bevor die Daten vollständig vorliegen. Und zwar üblicherweise mehrfach. Diese Entscheidungen können sich „im Nachhinein“ als unglücklich oder schlecht herausstellen, aber entweder nicht mehr oder nur mit zusätzlichen Kosten zurückgenommen werden. Ein Beispiel für ein Online-Problem ist die Suche nach einem kürzesten Weg ineinem Graphen, wobei der Graph anfangs unbekannt ist und Informationen über die Knoten und Kanten erst beim „Betreten“ eines Knotens erhalten werden.Eine optimale Lösung kann nur mit vollständiger Information, welche das Besuchen aller Knoten voraussetzt,erreicht werden. Sehr ähnlich ist auch die Bewegung eines autonomen Roboters in einerunerkundeten Umgebung oder die Navigation eines Spiders im World Wide Web. In manchen Fällen funktionieren Anwendungen des maschinellen Lernensebenfalls online; das System lernt während seiner „Arbeit“. Vom theoretischen Gesichtspunkt untersucht man die sogenannte Kompetitivität von Online-Algorithmen. Dabei handelt es sich im Wesentlichen um das Verhältnis von Kosten einer Lösung des Onlinealgorithmus zu denen einer optimalen Lösung (die man mit vorheriger Kenntnis der vollständigen Daten errechnen könnte) im schlechtesten Fall (über alle möglichen Sequenzen von schrittweise eintreffenden Informationen). Je nach Problem sind hier unterschiedliche Güten erreichbar. Diese Notation ist eng verwandt mit der der Approximationsgüte von Approximationsalgorithmen. (de)
- En informatique, un algorithme en ligne, parfois aussi appelé algorithme incrémental, est un algorithme qui reçoit un flux de données en entrée, et qui doit prendre des décisions au fur et à mesure. Un cadre classique est celui dans lequel l'algorithme doit répondre à des requêtes les unes après les autres, sans connaître les requêtes à venir. Il s'oppose au concept d'algorithme hors ligne qui reçoit d'un seul coup les données qu'il a à considérer, et prend ses décisions en fonction de cette entrée. Quand il est question d'apprentissage automatique, on parle parfois d'algorithme d'apprentissage incrémental. Quand la mémoire est la contrainte importante, on parle plutôt d'algorithme de fouille de flots de données. (fr)
- In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand. In operations research, the area in which online algorithms are developed is called online optimization. As an example, consider the sorting algorithms selection sort and insertion sort: selection sort repeatedly selects the minimum element from the unsorted remainder and places it at the front, which requires access to the entire input; it is thus an offline algorithm. On the other hand, insertion sort considers one input element per iteration and produces a partial solution without considering future elements. Thus insertion sort is an online algorithm. Note that the final result of an insertion sort is optimum, i.e., a correctly sorted list. For many problems, online algorithms cannot match the performance of offline algorithms. If the ratio between the performance of an online algorithm and an optimal offline algorithm is bounded, the online algorithm is called competitive. Not every offline algorithm has an efficient online counterpart. (en)
- In informatica, con la locuzione algoritmo online si intende un algoritmo, per la risoluzione di un problema, che deve fornire dei risultati pur non avendo a disposizione, inizialmente, alcuni dei dati in ingresso. Più precisamente, l'algoritmo riceve in ingresso una generica sequenza σ di input di cui, per ogni termine σi, deve fornire una risposta o prendere una decisione, basandosi solo sugli input ricevuti fino a tale istante, σj con j ≤ i. A questa tipologia si contrappone la definizione di algoritmo offline che designa i classici algoritmi, i quali possiedono tutti i dati d'ingresso fin dall'inizio dell'elaborazione, ovvero tutta la sequenza σ. (it)
- オンラインアルゴリズム（英: Online algorithm）は、入力全体を最初からアクセス可能にしなくても、先頭から順に処理していけるアルゴリズムを指す。これに対して、オフラインアルゴリズム（英: Offline algorithm）は、問題を解くのに最初からデータ全体へのアクセスが必要なバッチ処理型アルゴリズムを指す。例えば、挿入ソートはオンラインアルゴリズムで、選択ソートはオフラインアルゴリズムである。 また、時系列データをリアルタイムに処理して未来を予測するようなアルゴリズムを特に「オンラインアルゴリズム」と呼ぶ場合もあり、その場合単に入力を蓄積せずに逐次的に処理するアルゴリズムを「ストリームアルゴリズム」と呼ぶ。 例として、有限な連結グラフにおける最短経路問題を考えてみよう。ひとつのノードが入力され、そこから次の連結されたノードが辿れるようなデータ形式の場合、単純かつ完全な探索をしないと問題が解けないのは明らかである。そこで、オンラインアルゴリズムの性能と理想的なオフラインアルゴリズムの性能（全てのデータが最初からわかっている状態）とを比較する Competitive Analysis という手法が新たに生まれた。 オンラインアルゴリズムは、データをあらかじめすべて用意したり、読みだしたりする必要がなく、少量のデータを逐次読み込んで処理を行うことが可能である。そのため、すべてのデータを保持しておくのが難しいような大規模データ（ビッグデータ）を扱う状況や、時々刻々とデータが与えられる状況においてよく用いられる。また未来のデータに依拠せず、その時点までに得られたデータだけに依拠し、かつ逐次型で処理を行う特徴がある。 (ja)
- 전산학에서 온라인 알고리즘(online algorithm)이란 시작할 때 모든 입력 정보를 가지고 있지 않고, 입력을 차례로 받아들이면서 처리하는 알고리즘을 말한다. 이와는 반대로, 오프라인 알고리즘은 풀고자 하는 문제의 모든 데이터를 가지고 시작해야만 문제를 해결할 수 있다. 일례로, 선택 정렬은 정렬을 하기 전에 모든 데이터가 주어져야만 한다. 온라인 알고리즘은 기계 학습 분야에서 많이 연구된다. (ko)
- In de informatica is een online-algoritme een algoritme waarbij de invoer niet geheel bekend hoeft te zijn wanneer het algoritme begint. Dit staat tegenover een offline-algoritme waarbij de gehele invoer bekend moet zijn voordat het algoritme kan beginnen. Zo kan insertion sort bijvoorbeeld geïmplementeerd worden als een online-algoritme terwijl dat bij selection sort niet mogelijk is (bij selection sort moet de lijst geheel bekend zijn, bij insertion sort niet). Bij online-algoritmen kan het zijn dat het antwoord niet optimaal is aangezien niet alle informatie van tevoren bekend is. (nl)
- Algorytm online – szczególny rodzaj algorytmu, który nie zna danych wejściowych od początku w całości, lecz otrzymuje je w partiach (turach). Po każdej turze algorytm musi podać częściową odpowiedź. Problemy rozwiązywane przez algorytmy online nazywa się problemami online. Naturalnymi przykładami są przydział czasu lub pamięci procesora (scheduling) – ponieważ na ogół nie wiadomo, jakie procesy będą w przyszłości żądać zasobów, konieczne jest przydzielanie ich tylko na podstawie obecnej sytuacji. Bardziej matematycznym przykładem jest kolorowanie grafu online – startując od grafu pustego, w każdej turze dodaje się pojedynczy wierzchołek ze wszystkimi krawędziami. Zadaniem algorytmu jest wybrać dla niego kolor tak, aby kolorowanie było dopuszczalne i kolorów było możliwie najmniej. Algorytmami online nazywa się też te algorytmy klasyczne, które nie potrzebują czytać całych danych wejściowych, lecz mogą je przetwarzać na bieżąco. Takimi algorytmami są np. algorytm KMP dopasowania wzorca, czy algorytm Ukkonena konstrukcji drzewa sufiksowego. (pl)
- (англ. online algorithm) — алгоритми, що може обробляти дані в міру їх надходження, не маючи загального доступу до всіх даних з самого початку. На відміну від нього, офлайн алгоритм (англ. offline algorithm) може працювати з усіма даними від самого початку. Розділ в дослідженні операцій, який займається розробкою онлайн алгоритмів називається . Для прикладу розглянемо два алгоритми сортування: сортування вибором та сортування вставкою. Сортування вибором послідовно вибирає мінімальний елемент з невідсортованого залишку та розміщує його спереду, що потребує доступу до всіх входових даних; тобто, це буде офлайн алгоритм. На відміну від нього, сортування вставкою за одну ітерацію бере один входовий елемент і отримує частковий розв'язок без урахування майбутніх елементів. Таким чином, сортування вставкою — це онлайн алгоритм. Зверніть увагу, що кінцевий результат сортування вставкою є оптимальним, тобто, це правильно відсортований список. Для багатьох задач онлайн алгоритми не можуть мати таку ж швидкодію, як офлайн алгоритми. Якщо співвідношення швидкодії онлайн алгоритму до оптимального офлайн-алгоритму є обмеженим, то онлайн алгоритм називається конкурентним. Очевидно, що не кожен офлайн алгоритм має ефективний онлайн відповідник. (uk)
- 在電腦科學中，線上演算法是一種處理輸入資料的獨特形式，其演算過程中並不要求所有輸入資料在演算法開始運始之一刻即完備，反而可對逐步輸入的資料加以處理並在輸入完最後一項資料之後輸出運算結果。與之相對的稱為離線演算法，則假設輸入資料在運算開始前已完備。舉例：選擇排序是離線演算法，而插入排序則為線上演算法。 注意：插入排序始终生成一个最优的结果，也就是说一个正确排序的列表。然而对于很多问题，線上演算法的性能比不上离线算法（即无法取得最优的结果）。如果对于同一个问题的在线算法和最优化的离线算法的性能比率是有界的，那么这个在线算法被称作是competitive。 并非所有在线算法都有与之对应的离线算法。 (zh)
|
| rdfs:comment
|
- 전산학에서 온라인 알고리즘(online algorithm)이란 시작할 때 모든 입력 정보를 가지고 있지 않고, 입력을 차례로 받아들이면서 처리하는 알고리즘을 말한다. 이와는 반대로, 오프라인 알고리즘은 풀고자 하는 문제의 모든 데이터를 가지고 시작해야만 문제를 해결할 수 있다. 일례로, 선택 정렬은 정렬을 하기 전에 모든 데이터가 주어져야만 한다. 온라인 알고리즘은 기계 학습 분야에서 많이 연구된다. (ko)
- In de informatica is een online-algoritme een algoritme waarbij de invoer niet geheel bekend hoeft te zijn wanneer het algoritme begint. Dit staat tegenover een offline-algoritme waarbij de gehele invoer bekend moet zijn voordat het algoritme kan beginnen. Zo kan insertion sort bijvoorbeeld geïmplementeerd worden als een online-algoritme terwijl dat bij selection sort niet mogelijk is (bij selection sort moet de lijst geheel bekend zijn, bij insertion sort niet). Bij online-algoritmen kan het zijn dat het antwoord niet optimaal is aangezien niet alle informatie van tevoren bekend is. (nl)
- 在電腦科學中，線上演算法是一種處理輸入資料的獨特形式，其演算過程中並不要求所有輸入資料在演算法開始運始之一刻即完備，反而可對逐步輸入的資料加以處理並在輸入完最後一項資料之後輸出運算結果。與之相對的稱為離線演算法，則假設輸入資料在運算開始前已完備。舉例：選擇排序是離線演算法，而插入排序則為線上演算法。 注意：插入排序始终生成一个最优的结果，也就是说一个正确排序的列表。然而对于很多问题，線上演算法的性能比不上离线算法（即无法取得最优的结果）。如果对于同一个问题的在线算法和最优化的离线算法的性能比率是有界的，那么这个在线算法被称作是competitive。 并非所有在线算法都有与之对应的离线算法。 (zh)
- في علم الحاسوب، الخوارزمية الفورية (online algorithm) هي التي تقوم بمعالجة المدخلات (أو البيانات) عن طريق إدراجها عنصر تلو الأخر بطريقة تسلسلية، أي أن ترتيب المدخلات يكون على حسب ظهورها بشكل فوري إلى الخوارزمية، دون أن تكون جميع المدخلات متاحة منذ البداية. على النقيض من ذلك، يتم إعطاء الخوارزمية الغير فورية مدخلات المشكلة بأكملها من البداية، وعلى الخوارزمية أن تجد الحل المناسب للمشكلة الكاملة. في أبحاث العمليات، يسمى المجال الذي يتم فيه دراسة وتطوير الخوارزميات . ليس لكل خوارمية غير فورية نظير فعال (تنافسي) فوري. (ar)
- Ein Online-Algorithmus ist ein Lösungsverfahren für Probleme, bei denen zuBeginn des Berechnungsvorgangs nicht alle Eingabedaten verfügbar sind. Bei vielen algorithmisch lösbaren Problemen in der Informatik sind die vollständigen Eingabedaten vor der Ausführung des jeweiligen Algorithmus bekannt. Anhand dieser Daten wird eine Lösung berechnet und ausgegeben. Solche Probleme werden Offline-Probleme genannt. Sehr ähnlich ist auch die Bewegung eines autonomen Roboters in einerunerkundeten Umgebung oder die Navigation eines Spiders im World Wide Web. (de)
- In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start. In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand. In operations research, the area in which online algorithms are developed is called online optimization. Not every offline algorithm has an efficient online counterpart. (en)
- En informatique, un algorithme en ligne, parfois aussi appelé algorithme incrémental, est un algorithme qui reçoit un flux de données en entrée, et qui doit prendre des décisions au fur et à mesure. Un cadre classique est celui dans lequel l'algorithme doit répondre à des requêtes les unes après les autres, sans connaître les requêtes à venir. Il s'oppose au concept d'algorithme hors ligne qui reçoit d'un seul coup les données qu'il a à considérer, et prend ses décisions en fonction de cette entrée. (fr)
- In informatica, con la locuzione algoritmo online si intende un algoritmo, per la risoluzione di un problema, che deve fornire dei risultati pur non avendo a disposizione, inizialmente, alcuni dei dati in ingresso. Più precisamente, l'algoritmo riceve in ingresso una generica sequenza σ di input di cui, per ogni termine σi, deve fornire una risposta o prendere una decisione, basandosi solo sugli input ricevuti fino a tale istante, σj con j ≤ i. (it)
- オンラインアルゴリズム（英: Online algorithm）は、入力全体を最初からアクセス可能にしなくても、先頭から順に処理していけるアルゴリズムを指す。これに対して、オフラインアルゴリズム（英: Offline algorithm）は、問題を解くのに最初からデータ全体へのアクセスが必要なバッチ処理型アルゴリズムを指す。例えば、挿入ソートはオンラインアルゴリズムで、選択ソートはオフラインアルゴリズムである。 また、時系列データをリアルタイムに処理して未来を予測するようなアルゴリズムを特に「オンラインアルゴリズム」と呼ぶ場合もあり、その場合単に入力を蓄積せずに逐次的に処理するアルゴリズムを「ストリームアルゴリズム」と呼ぶ。 例として、有限な連結グラフにおける最短経路問題を考えてみよう。ひとつのノードが入力され、そこから次の連結されたノードが辿れるようなデータ形式の場合、単純かつ完全な探索をしないと問題が解けないのは明らかである。そこで、オンラインアルゴリズムの性能と理想的なオフラインアルゴリズムの性能（全てのデータが最初からわかっている状態）とを比較する Competitive Analysis という手法が新たに生まれた。 (ja)
- Algorytm online – szczególny rodzaj algorytmu, który nie zna danych wejściowych od początku w całości, lecz otrzymuje je w partiach (turach). Po każdej turze algorytm musi podać częściową odpowiedź. Problemy rozwiązywane przez algorytmy online nazywa się problemami online. Naturalnymi przykładami są przydział czasu lub pamięci procesora (scheduling) – ponieważ na ogół nie wiadomo, jakie procesy będą w przyszłości żądać zasobów, konieczne jest przydzielanie ich tylko na podstawie obecnej sytuacji. (pl)
- (англ. online algorithm) — алгоритми, що може обробляти дані в міру їх надходження, не маючи загального доступу до всіх даних з самого початку. На відміну від нього, офлайн алгоритм (англ. offline algorithm) може працювати з усіма даними від самого початку. Розділ в дослідженні операцій, який займається розробкою онлайн алгоритмів називається . Очевидно, що не кожен офлайн алгоритм має ефективний онлайн відповідник. (uk)
|
