Випадковісний або випадковісТний?
Модератор: Анатолій
Випадковісний або випадковісТний?
Ймовірність - ймовірнісний, а як бути з випадковість?
Re: Випадковісний або випадковісТний?
а в контексті? чим випадковий не годиться?
Re: Випадковісний або випадковісТний?
Випадковісний алгоритм як переклад для Randomized algorithm. Ще думав про Увипадковлений.
Випадковий алгоритм не підходить, бо це не один навмання обраний з багатьох, а це один єдиний алгоритм, що покладається на додаткову послідовність випадкових чисел, яку він отримує на вхід разом з основними даними. Його перебіг залежить від тої послідовності.
Увипадковлений мені подобається найбільше. Точно передає означення Randomized, його увипадковили.
Випадковий алгоритм не підходить, бо це не один навмання обраний з багатьох, а це один єдиний алгоритм, що покладається на додаткову послідовність випадкових чисел, яку він отримує на вхід разом з основними даними. Його перебіг залежить від тої послідовності.
Увипадковлений мені подобається найбільше. Точно передає означення Randomized, його увипадковили.
Re: Випадковісний або випадковісТний?
увипадковлений – зроблений випадковим. Ви виженете "випадкового" в двері, а він повернеться у вікно . хоча можливо (Ви дали трохи незграбне означення цього алгоритму) він саме увипадковлюваний
Щодо випадковісний/випадковістний. Однозначно "випадковісний". В мові й слів на -овістний нема.
Щодо випадковісний/випадковістний. Однозначно "випадковісний". В мові й слів на -овістний нема.
Re: Випадковісний або випадковісТний?
Ну так, його робить випадковим, ота додаткова послідовність, якщо подавати її однаковою, то алгоритм діятиме однаково, жодної внутрішньої випадковості.
Re: Випадковісний або випадковісТний?
тоді доведеться розібратися, чи він увипадковлений, чи увипадковлюваний. Швидше друге. Бо без послідовності це просто алгоритм. а специфічним він стає в якийсь момент. А щоб я міг з цим розібратися, мені потрібне детальне і точне означення його роботи. Я ж не програміст
Re: Випадковісний або випадковісТний?
з вікіпедії:
Увипадковлений алгоритм (англ. randomized algorithm) — це алгоритм, який використовує елемент випадковості як частину своєї логіки. Алгоритм зазвичай використовує рівномірно випадкові біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в середньому серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде випадкова величина визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами.
Потрібно розрізняти алгоритми, що використовують випадковий вхід для зменшення очікуваного часу виконання або об'єму використаної пам'яті, але завжди видають правильний вислід у обмежений відтинок часу, і ймовірнісні алгоритми, які, залежно від випадкового входу, можуть видати некоректний вислід (Алгоритм Монте-Карло) або зазнати невдачі в його отриманні (Алгоритм Лас-Вегасу), повідомивши про провал або через не завершення.
Re: Випадковісний або випадковісТний?
Угу, в Вікіпедію я й писав
Але як пояснення роботи алгоритму можна глянути. Якщо щось незрозуміло, то я завтра наведу приклад роботи якогось randomized алгоритму.
Але як пояснення роботи алгоритму можна глянути. Якщо щось незрозуміло, то я завтра наведу приклад роботи якогось randomized алгоритму.
Re: Випадковісний або випадковісТний?
так. це бажано "розжувати"
Re: Випадковісний або випадковісТний?
Прикладом такого алгоритму є швидке сортування.
На вхід отримуємо масив (наприклад, чисел).
Алгоритм з фіксованою опірною точкою - 1й елемент:
Розглянемо масив 54832971
1 крок:
Всі елементи більші від 5 - опірного елемента, пересуваємо ліворуч, більші праворуч - 4321 5 897. Чудово ми поділили масив навпіл. Тепер рекурсивно виконуємо те саме з кожним з підмасивів. у результаті ми отримуємо відсортований масив за час О(n*log(n)).
Але якщо на взід подати відсортований масив, тоді виходить так
12345678 - опірна точка 1. - 1 2345678, всі елементи більші ніж 1. На токому вході ми маємо час виконання O(n*n), що значно гірше.
Для уникнення подібних ситуацій на вхід алгоритму подається послідовність випадкових чисел, які він використовує для отримання номерів опірних елементів. Тобто ми чітко знаємо кожен крок алгоритму, він описаний, але завдяки додатковим вхідним даним, перебіг алгоритму для конкретного масиву наперед невідомий.
На вхід отримуємо масив (наприклад, чисел).
Алгоритм з фіксованою опірною точкою - 1й елемент:
Розглянемо масив 54832971
1 крок:
Всі елементи більші від 5 - опірного елемента, пересуваємо ліворуч, більші праворуч - 4321 5 897. Чудово ми поділили масив навпіл. Тепер рекурсивно виконуємо те саме з кожним з підмасивів. у результаті ми отримуємо відсортований масив за час О(n*log(n)).
Але якщо на взід подати відсортований масив, тоді виходить так
12345678 - опірна точка 1. - 1 2345678, всі елементи більші ніж 1. На токому вході ми маємо час виконання O(n*n), що значно гірше.
Для уникнення подібних ситуацій на вхід алгоритму подається послідовність випадкових чисел, які він використовує для отримання номерів опірних елементів. Тобто ми чітко знаємо кожен крок алгоритму, він описаний, але завдяки додатковим вхідним даним, перебіг алгоритму для конкретного масиву наперед невідомий.