Випадковісний або випадковісТний?

Питання та відповіді щодо української мови

Модератор: Анатолій

Yola
Повідомлень: 166
З нами з: Чет квітня 28, 2011 9:25 am

Випадковісний або випадковісТний?

Повідомлення Yola »

Ймовірність - ймовірнісний, а як бути з випадковість?
Кувалда
Редактор
Повідомлень: 5809
З нами з: Сер травня 27, 2009 8:33 pm

Re: Випадковісний або випадковісТний?

Повідомлення Кувалда »

а в контексті? чим випадковий не годиться?
Yola
Повідомлень: 166
З нами з: Чет квітня 28, 2011 9:25 am

Re: Випадковісний або випадковісТний?

Повідомлення Yola »

Випадковісний алгоритм як переклад для Randomized algorithm. Ще думав про Увипадковлений.

Випадковий алгоритм не підходить, бо це не один навмання обраний з багатьох, а це один єдиний алгоритм, що покладається на додаткову послідовність випадкових чисел, яку він отримує на вхід разом з основними даними. Його перебіг залежить від тої послідовності.

Увипадковлений мені подобається найбільше. Точно передає означення Randomized, його увипадковили.
Кувалда
Редактор
Повідомлень: 5809
З нами з: Сер травня 27, 2009 8:33 pm

Re: Випадковісний або випадковісТний?

Повідомлення Кувалда »

увипадковлений – зроблений випадковим. Ви виженете "випадкового" в двері, а він повернеться у вікно ;). хоча можливо (Ви дали трохи незграбне означення цього алгоритму) він саме увипадковлюваний ;)
Щодо випадковісний/випадковістний. Однозначно "випадковісний". В мові й слів на -овістний нема.
Yola
Повідомлень: 166
З нами з: Чет квітня 28, 2011 9:25 am

Re: Випадковісний або випадковісТний?

Повідомлення Yola »

Ну так, його робить випадковим, ота додаткова послідовність, якщо подавати її однаковою, то алгоритм діятиме однаково, жодної внутрішньої випадковості.
Кувалда
Редактор
Повідомлень: 5809
З нами з: Сер травня 27, 2009 8:33 pm

Re: Випадковісний або випадковісТний?

Повідомлення Кувалда »

тоді доведеться розібратися, чи він увипадковлений, чи увипадковлюваний. Швидше друге. Бо без послідовності це просто алгоритм. а специфічним він стає в якийсь момент. А щоб я міг з цим розібратися, мені потрібне детальне і точне означення його роботи. Я ж не програміст ;)
Andriy
Адміністратор сайту
Повідомлень: 3777
З нами з: Сер травня 27, 2009 8:23 pm

Re: Випадковісний або випадковісТний?

Повідомлення Andriy »

з вікіпедії:
Увипадковлений алгоритм (англ. randomized algorithm) — це алгоритм, який використовує елемент випадковості як частину своєї логіки. Алгоритм зазвичай використовує рівномірно випадкові біти як допоміжний вхід для спрямування своєї поведінки в надії досягнення хорошої швидкодії в середньому серед усіх можливих виборів випадкових бітів. Формально, швидкодією алгоритму буде випадкова величина визначена випадковими бітами; отже або швидкодія, або вихід (або і те, і те) є випадковими величинами.

Потрібно розрізняти алгоритми, що використовують випадковий вхід для зменшення очікуваного часу виконання або об'єму використаної пам'яті, але завжди видають правильний вислід у обмежений відтинок часу, і ймовірнісні алгоритми, які, залежно від випадкового входу, можуть видати некоректний вислід (Алгоритм Монте-Карло) або зазнати невдачі в його отриманні (Алгоритм Лас-Вегасу), повідомивши про провал або через не завершення.
Yola
Повідомлень: 166
З нами з: Чет квітня 28, 2011 9:25 am

Re: Випадковісний або випадковісТний?

Повідомлення Yola »

Угу, в Вікіпедію я й писав :lol:

Але як пояснення роботи алгоритму можна глянути. Якщо щось незрозуміло, то я завтра наведу приклад роботи якогось randomized алгоритму.
Кувалда
Редактор
Повідомлень: 5809
З нами з: Сер травня 27, 2009 8:33 pm

Re: Випадковісний або випадковісТний?

Повідомлення Кувалда »

так. це бажано "розжувати" :D
Yola
Повідомлень: 166
З нами з: Чет квітня 28, 2011 9:25 am

Re: Випадковісний або випадковісТний?

Повідомлення Yola »

Прикладом такого алгоритму є швидке сортування.

На вхід отримуємо масив (наприклад, чисел).

Алгоритм з фіксованою опірною точкою - 1й елемент:
Розглянемо масив 54832971
1 крок:
Всі елементи більші від 5 - опірного елемента, пересуваємо ліворуч, більші праворуч - 4321 5 897. Чудово ми поділили масив навпіл. Тепер рекурсивно виконуємо те саме з кожним з підмасивів. у результаті ми отримуємо відсортований масив за час О(n*log(n)).

Але якщо на взід подати відсортований масив, тоді виходить так
12345678 - опірна точка 1. - 1 2345678, всі елементи більші ніж 1. На токому вході ми маємо час виконання O(n*n), що значно гірше.

Для уникнення подібних ситуацій на вхід алгоритму подається послідовність випадкових чисел, які він використовує для отримання номерів опірних елементів. Тобто ми чітко знаємо кожен крок алгоритму, він описаний, але завдяки додатковим вхідним даним, перебіг алгоритму для конкретного масиву наперед невідомий.
Відповісти

Повернутись до “Мовні консультації”