diff options
Diffstat (limited to 'ru-ru')
| -rw-r--r-- | ru-ru/asymptotic-notation-ru.html.markdown | 225 | ||||
| -rw-r--r-- | ru-ru/clojure-ru.html.markdown | 2 | ||||
| -rw-r--r-- | ru-ru/forth-ru.html.markdown | 240 |
3 files changed, 466 insertions, 1 deletions
diff --git a/ru-ru/asymptotic-notation-ru.html.markdown b/ru-ru/asymptotic-notation-ru.html.markdown new file mode 100644 index 00000000..73ad80ba --- /dev/null +++ b/ru-ru/asymptotic-notation-ru.html.markdown @@ -0,0 +1,225 @@ +--- +category: Algorithms & Data Structures +name: Asymptotic Notation +contributors: + - ["Jake Prather", "http://github.com/JakeHP"] + - ["Divay Prakash", "http://github.com/divayprakash"] +translators: + - ["pru-mike", "http://gihub.com/pru-mike"] +lang: ru-ru +--- + +# О-cимволика + +## Что это такое? + +О-cимволика или асимптотическая запись это система символов позволяющая оценить +время выполнения алгоритма, устанавливая зависимость времени выполнения от +увеличения объема входных данных, так же известна как оценка +сложности алгоритмов. Быстро-ли алгоритм станет невероятно медленным, когда +объем входных данных увеличится? Будет-ли алгоритм выполняться достаточно быстро, +если объем входных данных возрастет? О-символика позволяет ответить на эти +вопросы. + +## Можно-ли по-другому найти ответы на эти вопросы? + +Один способ это подсчитать число элементарных операций в зависимости от +различных объемов входных данных. Хотя это и приемлемое решение, тот объем +работы которого оно потребует, даже для простых алгоритмов, делает его +использование неоправданным. + +Другой способ это измерить какое время алгоритм потребует для завершения на +различных объемах входных данных. В тоже время, точность и относительность +(полученное время будет относиться только к той машине на которой оно +вычислено) этого метода зависит от среды выполнения: компьютерного аппаратного +обеспечения, мощности процессора и т.д. + +## Виды О-символики + +В первом разделе этого документа мы определили, что О-символика +позволяет оценивать алгоритмы в зависимости от изменения размера входных +данных. Представим что алгоритм это функция f, n размер входных данных и +f(n) время выполнения. Тогда для данного алгоритма f c размером входных +данных n получим какое-то результирующее время выполнения f(n). +Из этого можно построить график, где ось Y время выполнения, ось X размер входных +данных и точки на графике это время выполнения для заданного размера входных +данных. + +С помощью О-символики можно оценить функцию или алгоритм +несколькими различными способами. Например можно оценить алгоритм исходя +из нижней оценки, верхней оценки, тождественной оценки. Чаще всего встречается +анализ на основе верхней оценки. Как правило не используется нижняя оценка, +потому что она не подходит под планируемые условия. Отличный пример алгоритмы +сортировки, особенно добавление элементов в древовидную структуру. Нижняя оценка +большинства таких алгоритмов может быть дана как одна операция. В то время как в +большинстве случаев, добавляемые элементы должны быть отсортированы +соответствующим образом при помощи дерева, что может потребовать обхода целой +ветви. Это и есть худший случай, для которого планируется верхняя оценка. + +### Виды функций, пределы и упрощения + +``` +Логарифмическая функция - log n +Линейная функция - an + b +Квадратическая функция - an^2 + bn +c +Полиномиальная функция - an^z + . . . + an^2 + a*n^1 + a*n^0, где z константа +Экспоненциальная функция - a^n, где a константа +``` + +Приведены несколько базовых функций используемых при определении сложности в +различных оценках. Список начинается с самой медленно возрастающей функции +(логарифм, наиболее быстрое время выполнения) и следует до самой быстро +возрастающей функции (экспонента, самое медленное время выполнения). Отметим, +что в то время как 'n' или размер входных данных, возрастает в каждой из этих функций, +результат намного быстрее возрастает в квадратической, полиномиальной +и экспоненциальной по сравнению с логарифмической и линейной. + +Крайне важно понимать, что при использовании описанной далее нотации необходимо +использовать упрощенные выражения. +Это означает, что необходимо отбрасывать константы и слагаемые младших порядков, +потому что если размер входных данных (n в функции f(n) нашего примера) +увеличивается до бесконечности (в пределе), тогда слагаемые младших порядков +и константы становятся пренебрежительно малыми. Таким образом, если есть +константа например размера 2^9001 или любого другого невообразимого размера, +надо понимать, что её упрощение внесёт значительные искажения в точность +оценки. + +Т.к. нам нужны упрощенные выражения, немного скорректируем нашу таблицу... + +``` +Логарифм - log n +Линейная функция - n +Квадратическая функция - n^2 +Полиномиальная функция - n^z, где z константа +Экспонента - a^n, где a константа +``` + +### О-Большое +О-Большое, записывается как **О**, это асимптотическая запись для оценки худшего +случая или для ограничения заданой функции сверху. Это позволяет сделать +_**асимптотическую оценку верхней границы**_ скорости роста времени выполнения +алгоритма. Допустим `f(n)` время выполнения алгоритма и `g(n)` заданная временная +сложность которая проверяется для алгоритма. Тогда `f(n)` это O(g(n)), если +существуют действительные константы с (с > 0) и n<sub>0</sub>, такие +что `f(n)` <= `c g(n)` выполняется для всех n начиная с некоторого n<sub>0</sub> (n > n<sub>0</sub>). + +*Пример 1* + +``` +f(n) = 3log n + 100 +g(n) = log n +``` + +Является-ли `f(n)` O(g(n))? +Является-ли `3 log n + 100` O(log n)? +Посмотрим на определение О-Большого: + +``` +3log n + 100 <= c * log n +``` + +Существуют-ли константы c, n<sub>0</sub> такие что выражение верно для всех n > n<sub>0</sub> + +``` +3log n + 100 <= 150 * log n, n > 2 (неопределенно для n = 1) +``` + +Да! По определению О-Большого `f(n)` является O(g(n)). + +*Пример 2* + +``` +f(n) = 3 * n^2 +g(n) = n +``` + +Является-ли `f(n)` O(g(n))? +Является-ли `3 * n^2` O(n)? +Посмотрим на определение О-Большого: + +``` +3 * n^2 <= c * n +``` + +Существуют-ли константы c, n<sub>0</sub> такие что выражение верно для всех n > n<sub>0</sub>? +Нет, не существуют. `f(n)` НЕ ЯВЛЯЕТСЯ O(g(n)). + +### Омега-Большое +Омега-Большое, записывается как **Ω**, это асимптотическая запись для оценки +лучшего случая или для ограничения заданой функции снизу. Это позволяет сделать +_**асимптотическую оценку нижней границы**_ скорости роста времени выполнения +алгоритма. + +`f(n)` принадлежит Ω(g(n)), если существуют действительные константы +с (с > 0) и <sub>0</sub> (n<sub>0</sub> > 0), такие что `f(n)` >= `c g(n)` для всех n > n<sub>0</sub>. + +### Примечание + +Асимптотические оценки сделаные при помощи О-Большое и Омега-Большое могут +как быть так и не быть точными. Для того что бы обозначить что границы не +являются асимптотически точными используются записи о-малое и омега-малое. + +### О-Малое +O-Малое, записывается как **о**, это асимптотическая запись для оценки верхней +границы времени выполнения алгоритма, при условии что граница не является +асимптотически точной. + +`f(n)` является o(g(n)), если можно подобрать такие действительные константы, +что для всех c (c > 0) найдется n<sub>0</sub> (n<sub>0</sub> > 0), так +что `f(n)` < `c g(n)` выполняется для всех n (n > n<sub>0</sub>). + +Определения О-символики для О-Большое и О-Малое похожи. Главное отличие в том, +что если f(n) = O(g(n)), тогда условие f(n) <= c g(n) выполняется если _**существует**_ +константа c > 0, но если f(n) = o(g(n)), тогда условие f(n) < c g(n) выполняется +для _**всех**_ констант с > 0. + +### Омега-малое +Омега-малое, записывается как **ω**, это асимптотическая запись для оценки +верней границы времени выполнения алгоритма, при условии что граница не является +асимптотически точной. + +`f(n)` является ω(g(n)), если можно подобрать такие действительные константы, +что для всех c (c > 0) найдется n<sub>0</sub> (n<sub>0</sub> > 0), так +что `f(n)` > `c g(n)` выполняется для всех n (n > n<sub>0</sub>) + +Определения Ω-символики и ω-символики похожи. Главное отличие в том, что +если f(n) = Ω(g(n)), тогда условие f(n) >= c g(n) выполняется если _**существует**_ +константа c > 0, но если f(n) = ω(g(n)), тогда условие f(n) > c g(n) +выполняется для _**всех**_ констант с > 0. + +### Тета +Тета, записывается как **Θ**, это асимптотическая запись для оценки +_***асимптотически точной границы***_ времени выполнения алгоритма. + +`f(n)` является Θ(g(n)), если для некоторых действительных +констант c1, c2 и n<sub>0</sub> (c1 > 0, c2 > 0, n<sub>0</sub> > 0), +`c1 g(n)` < `f(n)` < `c2 g(n)` для всех n (n > n<sub>0</sub>). + +∴ `f(n)` является Θ(g(n)) означает что `f(n)` является O(g(n)) +и `f(n)` является Ω(g(n)). + +О-Большое основной инструмент для анализа сложности алгоритмов. +Так же смотрите примеры по ссылкам. + +### Заключение +Такую тему сложно изложить кратко, поэтому обязательно стоит пройти по ссылкам и +посмотреть дополнительную литературу. В них дается более глубокое описание с +определениями и примерами. + + +## Дополнительная литература + +* [Алгоритмы на Java](https://www.ozon.ru/context/detail/id/18319699/) +* [Алгоритмы. Построение и анализ](https://www.ozon.ru/context/detail/id/33769775/) + +## Ссылки + +* [Оценки времени исполнения. Cимвол O()](http://algolist.manual.ru/misc/o_n.php) +* [Асимптотический анализ и теория вероятностей](https://www.lektorium.tv/course/22903) + +## Ссылки (Eng) + +* [Algorithms, Part I](https://www.coursera.org/learn/algorithms-part1) +* [Cheatsheet 1](http://web.mit.edu/broder/Public/asymptotics-cheatsheet.pdf) +* [Cheatsheet 2](http://bigocheatsheet.com/) + diff --git a/ru-ru/clojure-ru.html.markdown b/ru-ru/clojure-ru.html.markdown index 451da312..356d1cc0 100644 --- a/ru-ru/clojure-ru.html.markdown +++ b/ru-ru/clojure-ru.html.markdown @@ -321,7 +321,7 @@ keymap ; => {:a 1, :b 2, :c 3} - оригинал не был затронут ; Также модуль может быть импортирован формой require (require 'clojure.string) -; После этого модуль становится доступе в текущем пространстве имен, +; После этого модуль становится доступен в текущем пространстве имен, ; а вызов его функций может быть осуществлен указанием полного имени функции: (clojure.string/blank? "") ; => true diff --git a/ru-ru/forth-ru.html.markdown b/ru-ru/forth-ru.html.markdown new file mode 100644 index 00000000..05316578 --- /dev/null +++ b/ru-ru/forth-ru.html.markdown @@ -0,0 +1,240 @@ +--- +language: forth +contributors: + - ["Horse M.D.", "http://github.com/HorseMD/"] +translators: + - ["Dmitrii Kuznetsov", "https://github.com/torgeek"] +filename: learnforth-ru.fs +lang: ru-ru +--- + +Форт создан Чарлзом Муром в 70-е годы. Это императивный, стековый язык программирования и среда исполнения программ. Использовался в таких проектах как Open Firmware. Продолжает применятся в проектах. Применяется в НАСА. + +Внимание: эта материал использует реализацию Форта - Gforth, но большая часть написанного будет работать в других средах. + +``` +\ Это комментарий +( Это тоже комментарий, но использыется для предоределённых слов ) + +\ --------------------------------- Прекурсор -------------------------------- + +\ Всё программирование на Форте заключается в манипулировании +\ параметрами на стеке. +5 2 3 56 76 23 65 \ ok + +\ Эти числа добавляются в стек слева направо +.s \ <7> 5 2 3 56 76 23 65 ok + +\ В Форте всё - это слова-команды или числа. Слова разделяются любым числом +\ пробелов и переходов на новую строку. Длина слова не больше 31 литеры. + +\ ---------------------------- Базовая арифметика ---------------------------- + +\ Арифметика (фактически все ключевые слова требуют данных) - это манипуляция +\ данными на стеке. +5 4 + \ ok + +\ `.` показывает верхнее значение в стеке: +. \ 9 ok + +\ Ещё примеры арифметических выражений: +6 7 * . \ 42 ok +1360 23 - . \ 1337 ok +12 12 / . \ 1 ok +13 2 mod . \ 1 ok + +99 negate . \ -99 ok +-99 abs . \ 99 ok +52 23 max . \ 52 ok +52 23 min . \ 23 ok + +\ --------------------------- Манипуляции со стеком --------------------------- + +\ Естественно, когда мы работаем со стеком, то используем +\ больше полезных методов: + +3 dup - \ дублировать верхний элемент в стеке + \ (1-й становится эквивалентным 2-му): 3 - 3 +2 5 swap / \ поменять местами верхний элемент со 2-м элементом: 5 / 2 +6 4 5 rot .s \ сменять по очереди 3-и верхних элемента: 4 5 6 +4 0 drop 2 / \ снять верхний элемент (не печатается на экране): 4 / 2 +1 2 3 nip .s \ снять второй элемент (подобно исключению элемента): 1 3 + +\ ------------------ Более продвинутые манипуляции со стеком ------------------ + +1 2 3 4 tuck \ дублировать верхний елемент стека во вторую позицию: + \ 1 2 4 3 4 ok +1 2 3 4 over \ диблировать второй елемент наверх стека: + \ 1 2 3 4 3 ok +1 2 3 4 2 roll \ *переместить* элемент в заданной позиции наверх стека: + \ 1 3 4 2 ok +1 2 3 4 2 pick \ *дублировать* элемент в заданной позиции наверх: + \ 1 2 3 4 2 ok + +\ Внимание! Обращения к стеку индексируются с нуля. + +\ --------------------------- Создание новых слов ----------------------------- + +\ Определение новых слов через уже известные. Двоеточие `:` переводит Форт +\ в режим компиляции выражения, которое заканчивается точкой с запятой `;`. +: square ( n -- n ) dup * ; \ ok +5 square . \ 25 ok + +\ Мы всегда можем посмотреть, что содержится в слове: +see square \ : square dup * ; ok + +\ -------------------------------- Зависимости -------------------------------- + +\ -1 == true, 0 == false. Однако, некоторые ненулевые значения +\ обрабатываются как true: +42 42 = \ -1 ok +12 53 = \ 0 ok + +\ `if` это компилируемое слово. `if` <stuff to do> `then` <rest of program>. +: ?>64 ( n -- n ) dup 64 > if ." Больше чем 64!" then ; +\ ok +100 ?>64 +\ Больше чем 64! ok + +\ Else: +: ?>64 ( n -- n ) dup 64 > if ." Больше чем 64!" else ." меньше чем 64!" then ; +100 ?>64 \ Больше чем 64! ok +20 ?>64 \ меньше чем 64! ok + +\ ------------------------------------ Циклы ----------------------------------- + +\ `do` это тоже компилируемое слово. +: myloop ( -- ) 5 0 do cr ." Hello!" loop ; \ ok +myloop +\ Hello! +\ Hello! +\ Hello! +\ Hello! +\ Hello! ok + +\ `do` предполагает наличие двух чисел на стеке: конечное и начальное число. + +\ Мы можем назначить в цикле переменную `i` для значения индекса: +: one-to-12 ( -- ) 12 0 do i . loop ; \ ok +one-to-12 \ 0 1 2 3 4 5 6 7 8 9 10 11 12 ok + +\ `?do` работает подобным образом, за исключением пропуска начального +\ и конечного значения индекса цикла. +: squares ( n -- ) 0 ?do i square . loop ; \ ok +10 squares \ 0 1 4 9 16 25 36 49 64 81 ok + +\ Изменение "шага" цикла проиводится командой `+loop`: +: threes ( n n -- ) ?do i . 3 +loop ; \ ok +15 0 threes \ 0 3 6 9 12 ok + +\ Запуск бесконечного цикла - `begin` <stuff to do> <flag> `until`: +: death ( -- ) begin ." Вы всё ещё здесь?" 0 until ; \ ok + +\ ---------------------------- Переменные и память ---------------------------- + +\ Используйте `variable`, что бы объявить `age` в качестве переменной. +variable age \ ok + +\ Затем мы запишем число 21 в переменную 'age' (возраст) словом `!`. +21 age ! \ ok + +\ В заключении мы можем напечатать значение переменной прочитав его словом `@`, +\ которое добавит значение на стек или использовать слово `?`, +\ что бы прочитать и распечатать в одно действие. +age @ . \ 21 ok +age ? \ 21 ok + +\ Константы объявляются аналогично, за исключем того, что мы не должны +\ беспокоиться о выделении адреса в памяти: +100 constant WATER-BOILING-POINT \ ok +WATER-BOILING-POINT . \ 100 ok + +\ ---------------------------------- Массивы ---------------------------------- + +\ Создание массива похоже на объявление переменной, но нам нужно выделить +\ больше памяти. + +\ Вы можете использовать слова `2 cells allot` для создания массива +\ размером 3 элемента: +variable mynumbers 2 cells allot \ ok + +\ Инициализировать все значения в 0 +mynumbers 3 cells erase \ ok + +\ В качестве альтернативы мы можем использовать `fill`: +mynumbers 3 cells 0 fill + +\ или мы можем пропустить все слова выше и инициализировать массив +\ нужными значениями: +create mynumbers 64 , 9001 , 1337 , \ ok (the last `,` is important!) + +\ ... что эквивалентно: + +\ Ручная запись значений по индексам ячеек: +64 mynumbers 0 cells + ! \ ok +9001 mynumbers 1 cells + ! \ ok +1337 mynumbers 2 cells + ! \ ok + +\ Чтение значений по индексу: +0 cells mynumbers + ? \ 64 ok +1 cells mynumbers + ? \ 9001 ok + +\ Мы можем просто сделать собственное слово для манипуляции массивом: +: of-arr ( n n -- n ) cells + ; \ ok +mynumbers 2 of-arr ? \ 1337 ok + +\ Которую тоже можно использовать для записи значений: +20 mynumbers 1 of-arr ! \ ok +mynumbers 1 of-arr ? \ 20 ok + +\ ------------------------------ Стек возвратов ------------------------------ + +\ Стек возвратов используется для удержания ссылки, +\ когда одно слово запускает другое, например, в цикле. + +\ Мы всегда видим это, когда используем `i`, которая возвращает дубль верхнего +\ значения стека. `i` это эквивалент `r@`. +: myloop ( -- ) 5 0 do r@ . loop ; \ ok + +\ Так же как при чтении мы можем добавить ссылку в стек возвратов и удалить её: +5 6 4 >r swap r> .s \ 6 5 4 ok + +\ Внимание: так как Форт использует стек возвратов для указателей на слово `>r` +\ следует всегда пользоваться `r>`. + +\ ---------------- Операции над числами с плавающей точкой -------------------- + +\ Многие фортовцы стараются избегать использование слов с вещественными числами. +8.3e 0.8e f+ f. \ 9.1 ok + +\ Обычно мы просто используем слово 'f', когда обращаемся к вещественным числам: +variable myfloatingvar \ ok +4.4e myfloatingvar f! \ ok +myfloatingvar f@ f. \ 4.4 ok + +\ ---------- В завершение несколько полезных замечаний и слов ----------------- + +\ Указание несуществующего слова очистит стек. Тем не менее, есть специальное +\ слово для этого: +clearstack + +\ Очистка экрана: +page + +\ Загрузка форт-файла: +\ s" forthfile.fs" included + +\ Вы можете вывести список всех слов словаря Форта (это большой список!): +words + +\ Выход из Gforth: +bye + +``` + +##Готовы к большему? + +* [Начала Форта (англ.)](http://www.forth.com/starting-forth/) +* [Простой Форт (англ.)](http://www.murphywong.net/hello/simple.htm) +* [Мышление Форта (англ.)](http://thinking-forth.sourceforge.net/) +* [Учебники Форта (рус.)](http://wiki.forth.org.ru/УчебникиФорта) |