Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
Кстати, почему в данном случае мы не стали применять ToExpression? Следующую задачу можно, конечно, решить при помощи Insert или Replace, но проще использовать Join. 6.11. Определите функцию, которая разделяет список длины n на началь- ный отрезок длины m и конечный отрезок длины n − m и переставляет их между собой. 6.12. Определите функцию, которая сопоставляет списку длины n список длины 2n, состоящий из элементов исходного списка, написанных сначала в прямом, а потом в обратном порядке. 6.13. Определите функцию, которая сопоставляет списку длины n список длины 2n − 1, в котором между каждыми двумя членами исходного списка вписана их сумма. Решение. Отбросим из списка последний элемент, образуем требуемый список для этого более короткого списка, а потом вольем недостающий кусочек. Для разнообразия оформим это, не применяя Last и Most к ис- ходному списку: stern[ {x }]:={x} stern[ {x ,y }]:=stern[{x,y}] =Join[stern[ {x}],{Last[stern[{x}]]+y,y}] 6.14. Определите функцию, которая сопоставляет спискам x = (x 1 , . . . , x n ) и y = (y 1 , . . . , y n ) длины n список длины 2n x♯y = (x 1 , y 1 , . . . , x n , y n ), называемый их перемешиванием. 6.15. Задайте функцию, которая разделяет список длины 2n на начало и конец, а потом перемешивает их. Основная команда вращения это RotateRight — или, что то же самое! — RotateLeft. RotateLeft[x] циклически переставить элементы списка x влево RotateLeft[x,m] циклически переставить элементы списка x влево RotateRight[x] циклически переставить элементы списка x вправо RotateRight[x,m] циклически переставить элементы списка x вправо 382 RotateRight[x,m] задает вращение списка x на m позиций вправо, а RotateLeft[x,m] — на m позиций влево. Таким образом, RotateRight[x] это просто RotateRight[x,1], а RotateRight[x,m] это то же самое, что Nest[RotateRight,x,m]. Различие между командами RotateRight и Rota- teLeft чисто психологическое. 6.16. Несколькими способами выразите RotateRight через RotateLeft. Решение. Проще всего, конечно, так RotateLeft[x,-1], но можно так RotateLeft[x,Length[x]-1]], или так Reverse[RotateLeft[Reverse[x]]]. 6.17. Несколькими способами выразите RotateRight[x,m] через Rotate- Left. 6.18. Список x длины n мыслится как соединение начального подсписка длины m и конечного подсписка длины n − m. Задайте вращение, пере- ставляющее начало и конец. Решение. Проще всего RotateLeft[x,m] или RotateRight[x,n-m]. Кроме приведенных выше, у этой задачи есть много других решений. Например, можно использовать тот факт, что вращение есть произведение двух отра- жений: Reverse[Join[Reverse[Take[x,m]],Reverse[Take[x,m-n]]]] Основные команды раздутия — или, как говорят в линейной алгебре, окаймления — это PadLeft и PadRight PadLeft[x,n, {y,z}] раздуть список x влево посредством y, z PadRight[x,n, {y,z}] раздуть список x вправо посредством y, z Вычисление PadRight[x,n, {y,z,...}] формирует список длины n, по- лучающийся из списка x дорисовыванием циклически повторяющихся эле- ментов y, z, . . . . Важнейший нюанс состоит в том, что элементы y, z, . . . начинают расходоваться не с позиции Length[x]+1, а с позиции 1, ины- ми словами, для списка x длины m первые m элементов y, z, . . . остаются невидимыми. Поэтому эта команда удобнее всего в одном из следующих случаев. • Раздутие посредством одного элемента, в формате PadRight[x,n,y]. По умолчанию y = 0, так что PadRight[x,n] дорисовывает к списку x длины m справа n − m нулей. • Раздутие пустого списка PadRight[{},n,{y,z,...}], иными словами, с самого начала формируемого списка циклически повторяются элементы списка (y, z, . . . ) 6.19. Составьте список (1, −1, 1, −1, . . . ) длины 2n. Решение. Мы это уже делали многими разными способами, используя Table, Join и Flatten, но теперь проще всего так PadRight[ {},2*n,{1,-1}]. 383 6.20. Составьте список (a, b, c, a, b, c, . . . ) длины n. 6.21. Задайте число 1.73 . . . 3, где количество троек равно n. Решение. Скажем, так N[FromDigits[ {PadRight[{1,7},n+2,3],1}]] 6.22. Сформируйте список (a, b, x, y, z, x, y, z, . . . ), где группа (x, y, z) по- вторена n раз. Решение. Как мы уже предупреждали, вычисление PadRight[ {a,b},3*n+2,{x,y,z}] не даст правильного результата. Например, вычисление PadRight[ {a,b},11,{x,y,z}] дает {a,b,z,x,y,z,x,y,z,x,y}, а вовсе не {a,b,x,y,z,x,y,z,x,y,z}, как хотелось бы. Нужный результат можно, конечно, получить посредством PadRight[ {a,b},3*n+2,RotateRight[{x,y,z},2]] Однако, чтобы не вычислять в каждом случае нужный сдвиг, гораздо удоб- нее обращаться к PadRight в одном из следующих форматов: Join[ {a,b},PadRight[{},3*n,{x,y,z}]] Flatten[PadRight[ {a,b},n+2,{{x,y,z}}],1] Снова различие между PadRight и PadLeft не мериторическое, а чисто психологическое. Ясно, что раздутие влево PadLeft[x,n, {y,z,...}] это в точности раздутие вправо, но считая с конца и в отрицательном направ- лении, PadRight[x,-n, {y,z,...}]. 7. Вложенные списки. 164 Список, элементы которого сами являются списками, называется вло- женным списком = nested list. В языке Mathematica вложенные спис- ки являются основным инструментом для моделирования математических структур. Матрицы, тензоры, деревья, отображения, отношения, графы, и многое другое — все это моделируется вложенными списками. В частности, мы уже много раз пользовались тем фактом, что матрица в языке Mathematica записывается как вложенный список, составленный из строк этой матрицы. Скажем, {{a,b,c},{d,e,f},{g,h,i}} изображает матрицу a b c d e f g h i . В этом параграфе мы изучим основные приемы работы со списками, связанные с изменением уровней вложенности, а именно, • команды выравнивания, которые убирают уровни вложенности; • команды разбиения, которые добавляют уровни вложенности; 164 What bird has done yesterday, man may do next year, be it fly, be it moult, be it hatch, be it nest. c James Joyce, Finnegan’s wake 384 • команды транспонирования, которые переставляют уровни вложен- ности. В частности, в применении к матрицам, выравнивание превращает матри- цы в строки, разбиение превращает строки в матрицы, а транспонирование восстанавливает симметрию между строками и столбцами. Основные команды выравнивания в системе это Flatten и FlattenAt. Flatten[x] выровнять список x Flatten[x,m] выровнять список x до уровня m FlattenAt[x,i] выровнять только i-ю позицию Команда Flatten[x] производит полное выравнивание списка, убирая все внутренние скобки. Иными словами, эта команда эффективно превра- щает любой вложенный список в линейный. Обычно, при этом исчеза- ет большая часть нужной структуры, поэтому гораздо чаще применяются команды частичного выравнивания Flatten[x,m], убирающие только m верхних уровней вложенности. Такая необходимость связана с тем, что как команды формирования списков, так и многие команды применения функций к спискам, в частности, Outer, создают лишние уровни вложен- ности. С другой стороны, мощнейший метод работы со списками состоит в том, чтобы искусственно создать лишние уровни вложенности. Особен- но часто используется команда Flatten[list,1], убирающая один лишний вложенный уровень в list, а именно, верхний. Гораздо избирательнее действует команда FlattenAt, которая убирает только один уровень вложенности и только у i-й части списка. 7.1. Задайте функцию, которая врисовывает после i-го элемента списка x элементы u, v, w Решение. Если с использованием FlattenAt, то так FlattenAt[Insert[x, {u,v,w},i+1],i+1] 7.2. Выразите функцию Flatten в терминах FlattenAt. 7.3. Выразите функцию FlattenAt в терминах Flatten. Указание. Используйте MapAt. Основные команды разбиения это Partition и Split. Функция Parti- tion может использоваться в связи с задачами линейной алгебры (генера- ция матриц и списков матриц). Здесь мы об этом лишь вскользь упоми- наем, но не будем обсуждать весьма деликатные детали, связанные с ее параметрами. Partition[x,m] разбить список x на списки длины m Partition[x,m,d] разбить список x на списки длины m со сдвигом d Split[x] разбить список x на списки одинаковых элементов Split[x,test] разбить список x по критерию 385 7.4. Задайте функцию, порождающую по списку список пар его соседних элементов. Решение. Ну конечно, просто Partition[x,2,1]. 7.5. То же, считая, что список циклический, ными словами, после послед- него элемента снова идет первый. Решение. На самом деле, так: Partition[x,2,1, {1,1}]. Впрочем, это как раз одна из тех деталей, которые мы договорились не обсуждать. По- этому воспользуйтесь Append. 7.6. Породите список {{{{a,b},{c,d}},{{e,f},{g,h}}},{{{i,j},{k,l}},{{m,n},{o,p}}}} Решение. Например, так Nest[Partition[#,2]&,ToExpression[CharacterRange["a","p"]],3] 7.7. А теперь уберите в списке из предыдущей задачи нижний уровень вложенности. Решение. Мы знаем, что команда Flatten[x,1] убирает верхний уровень вложенности, иными словами, превращает этот список в список {{{a,b},{c,d}},{{e,f},{g,h}},{{i,j},{k,l}},{{m,n},{o,p}}} Напрашивающаяся идея состоит в том, чтобы переставить верхний и ниж- ний уровень, убрать верхний уровень и снова переставить верхний и ниж- ний уровень. Реализовать эту идею можно, но это совсем не так просто, как кажется — To tell between Murphy's and Guinness is sure not a task for beguinness. Даже при правильной перестановке уровней элементы внутри самых глубоких списков окажутся переставленными по сравнению с тем, что получается при применении выравнивания к нижнему уровню! Правильное решение состоит в том, чтобы селективно применить Flat- ten при помощи Map, на самом нижнем уровне, примерно так Map[Flatten,x, {-3}] Откуда здесь берется −3? Ну, уровень −1 — это атомы, которые не имеют дальнейшей структуры, и применять к ним Flatten нельзя. Уровень −2 — это линейные списки, в которых нет внутренних скобок, и применять к ним Flatten бессмысленно. Применение же этой команды к списку из предыдущей задачи возвращает {{{a,b,c,d},{e,f,g,h}},{{i,j,k,l},{m,n,o,p}}}, как и задумывалось. К спискам, содержащим большое количество повторений, часто приме- няется метод сжатия, называемый RunLengthEncode, когда список заменя- ется на список пар, состоящих из элемента и количества ее повторений в серии. 7.8. Реализуйте функцию RunLengthEncode. Решение. Проще всего, конечно, с помощтю функции Split: RunLengthEncode[x ]:=Map[ {First[#],Length[#]}&,Split[x]] 386 Чаще всего встречающийся элемент списка называется модой. 7.9. Задайте функцию, сопоставляющую списку список его мод. Однако, в действительности, команда Split служит не для того, чтобы разбивать список на одинаковые элементы, а для того, чтобы разбивать его на серии эквивалентных элементов. При этом эквивалентность может либо вызываться по имени — по умолчанию это SameQ — либо задаваться непосредственно в теле функции Split в формате анонимной функции от двух переменных blabla[#1,#2]&. 7.10. Разбейте список натуральных чисел на последовательные фрагмен- ты, состоящие из чисел одинаковой четности. Решение. Проще всего так Split[x,Mod[#1-#2,2]==0&] Перестановка уровней списка осуществляется командой Transpose, ко- торую не следует путать с командой Reverse, переставляющей начало и конец линейного списка. Reverse[x] инвертировать список x Transpose[x] транспонировать список x Transpose[x,perm] переставить уровни вложенности списка x По умолчанию команда Transpose переставляет два верхних уровня вло- женности списков. Таким образом, например, команда Transpose, приме- ненная к списку матриц будет переставлять строки этих матриц между собой, а вовсе не транспонировать сами эти матрицы. В Модуле 1 мы реа- лизовали команду, которая транспонирует каждую из матриц списка, при помощи Map. 7.11. Задайте функцию, которая транспонирует каждую из матриц списка непосредственно при помощи Transpose. 7.12. Задайте функцию, которая переставляет верхний уровень вложен- ности списка с нижним, оставляя на месте все остальные. 7.13. Задайте функцию, которая транспонирует два нижних уровня вло- женности списка. Чрезвычайно эффективная стратегия работы со списками — основная стратегия, которой придерживаются опытные пользователи — состоит в следующем: • создать дополнительные уровни вложенности, • выполнить операции над образовавшимися короткими спис- ками, • снова убрать лишние уровни вложенности. 7.14. Определите команду, переставляющую четные и нечетные позиции списка. Решение. Конечно, это можно исполнить совсем тупо, скажем, так 387 interchange[x ]:=Table[If[OddQ[i],x[[i+1]],x[[i-1]]], {i,1,Length[x]}] Однако, понимающий человек задаст ту же функцию так: interchange[x ]:=Flatten[Map[Reverse,Partition[x,2]],1] Кстати, задание первой функции содержит серьезную ошибку, в чем легко убедиться попытавшись вычислить interchange[ToExpression[CharacterRange["a","z"]]] 8. Деревья. 165,166,167 Важнейшей нелинейной структурой при работе с данными, выражени- ями и алгоритмами являются деревья. Укорененное дерево = rooted tree представляет собой следующую рекуррентно определяемую матема- тическую структуру: • конечное множество вершин X, • в случае X 6= ∅, выделенную точку x ∈ X, называемую корнем дерева X. • разбиение всех остальных вершин на m попарно непересекающихся множеств X 1 , . . . , X m , каждое из которых в свою очередь снабжено струк- турой укорененного дерева. Корни x 1 , . . . , x m укорененных деревьев X 1 , . . . , X m называются детьми корня x, по отношению к ним x является родителем. По отношению друг к другу дети одного и того же родителя называются сиблингами. Эта тер- минология не является общепринятой, часто сиблинги называются также братьями или сестрами, etc., как указано в следующей таблице: parent mother father родитель child daughter son ребенок sibling sister brother сиблинг ancestor предок descendant потомок В дальнейшем для краткости укорененные деревья называются просто деревьями. Рассмотрим следующие способы задания деревьев посред- ством вложенных списков: • Список с отступами: за каждой вершиной указывается список еe поддеревьев. • Для каждой вершины указывается ее родитель. • Для каждой вершины указывается список ее предков. 165 И произрастил Господь Бог из земли всякое дерево, приятное на вид и хорошее для пищи, и дерево жизни посреди рая, и дерево познания добра и зла. Бытие 166 Устроил себе сады и рощи, и насадил в них всякие плодовитые дерева. Екклесиаст 167 Как известно, деревья появились на третий день сотворения мира и на протяжении веков очень широко применялись. c Дональд Кнут Искусство программирования 388 • Для каждой вершины указывается список ее детей. • Для каждой вершины указывается список ее потомков. • Для каждой вершины указываются ее старший ребенок и непосред- ственно следующий сиблинг. • Для каждой вершины указываются ее младший ребенок и непосред- ственно предшествующий сиблинг. В следующих задачах предполагается решение для каждого из описан- ных выше представлений деревьев. 8.1. Задайте функцию, указывающую корень дерева. 8.2. Задайте функцию, указывающую для каждой вершины ее родителя. 8.3. Задайте функцию, указывающую для каждой вершины всех ее пред- ков. 8.4. Задайте функцию, указывающую для каждой вершины ее старшего ребенка. 8.5. Задайте функцию, указывающую для каждой вершины ее младшего ребенка. 8.6. Задайте функцию, указывающую для каждой вершины список ее де- тей. 8.7. Задайте функцию, указывающую для каждой вершины непосред- ственно предшествующего ей сибллинга. 8.8. Задайте функцию, указывающую для каждой вершины непосред- ственно следующего за ней сиблинга. 8.9. Задайте функцию, указывающую для каждой вершины список ее младших сиблингов. 8.10. Задайте функцию, указывающую для каждой вершины список ее старших сиблингов. 8.11. Задайте функцию, указывающую для каждой вершины список всех ее сиблингов. 8.12. Задайте функцию, указывающую для каждой вершины список всех ее потомков. 8.13. Задайте функцию, возвращающую m-ю генерацию (= уровень) де- рева. 8.14. Задайте функцию, возвращающую множество листов дерева. Теперь, вооружившись функциями, определенными в этих задачах, вы можете справиться со следующей общей задачей. 8.15. Задайте функции, преобразующие каждое из перечисленных выше представлений, во каждое из остальных. 389 9. Порядок и сортировка. A crusader's wife slipped from the garrison And had an affair with a Saracen. She was not oversexed, Or jealous or vexed, She just wanted to make a comparison. 168 Задача сортировки в простейшей постановке состоит в следующем. Имеется список {{x1,y1},{x2,y2},...,{xn,yn}} состоящий из записей x 1 , . . . , x n и ключей y 1 , . . . , y n . Требуется располо- жить этот список в порядке возрастания ключей. В дальнейшем мы обычно делаем два упрощающих предположения: • записи совпадают с ключами, иными словами, происходит сортировка списка {x1,x2,...,xn}; • среди ключей нет повторяющихся, иными словами, x i 6= x j при i 6= j. Оба эти предположения являются чисто техническими, никак не влияют на сложность задачи сортировки и введены исключительно для упроще- ния обозначений. Все излагаемые далее алгоритмы работают и без этих предположений. Более того, некоторые из них являются устойчивыми, в том смысле, что они не меняют порядка записей с одинаковым ключом, по отношению к исходному списку. В Mathematica имеются внутренняя команда, осуществляющая сорти- ровку, Sort. Команда OrderedQ[x] является сокращением для Sort[x]==x. Order[x,y] сравнение x и y Sort[x] сортировка списка x Sort[x,crit] сортировка списка x по критерию crit OrderedQ[x] тест упорядоченности x Сортировка осуществляется в соответствии с внутренним порядком, заданным на множестве всех выражений, подробнее по этому поводу см. Модуль 2 Основы синтаксиса . Функция Order[x,y] возвращает +1, если x предшествует y относительно внутреннего порядка, −1, если x сле- дует за y, и 0, если они равны. Вот что достаточно знать о внутреннем порядке начинающему: • числа предшествуют буквам; • для вещественных чисел используется обычный порядок; • комплексные числа сортируются по вещественной части, а при равен- стве вещественных частей — по абсолютной величине мнимой части (по- дробнее см. Модуль 1); 168 В сборнике Лимерики по-русски этот лимерик переведен так: Чернобровая дева из Азии/ Отдалась молодцу ашкеназии./ Ей не то, чтобы мало/ От своих попадало,/ Но хотелось ей разнообразии. — К сожалению, при этом потеряно ключевое слово comparison. 390 • для символов и выражений используется обычный алфавитный поря- док; • строчные буквы предшествуют прописным; • короткие выражения предшествуют длинным. В случае, когда мы хотим осуществить сортировку в соответствии с по- рядком, отличающимся от внутреннего порядка, применяется сортиров- ка по критерию Sort[x,crit]. Например, применение Sort[x,Greater] или, что то же самое, Sort[x,#>#2&], отсортирует список чисел не в по- рядке возрастания, а в порядке убывания. 9.1. Отсортируйте список натуральных чисел по числу делителей. Решение. Напрашивающееся решение Sort[Range[10],Length[Divisors[#1]] Reverse[Sort[Range[20], Length[Divisors[#1]]>Length[Divisors[#2]]&]] 9.2. Отсортируйте список пар по второму элементу. Решение. В зависимости от того, что мы под этим понимаем. Если мы хотим отсортировать пары лексикографически, но с обратным порядком индексов, то так newsort[x ]:=Sort[x,OrderedQ[ {Reverse[#1],Reverse[#2]}]&] Хотя можно применить трюк с двойным применением Reverse — в части, посвященной перестановкам, мы будем постоянно пользоваться этим трю- ком, как с Reverse, так и с Transpose: newsort[x ]:=Map[Reverse,Sort[Map[Reverse,x]]] Если же мы хотим просто переставить пары в порядке возрастания второго элемента, вообще не обращая внимания на первый элемент, то так: newsort[x ]:=Sort[x,OrderedQ[ {Last[#1],Last[#2]}]&] 9.3. Отсортируйте элементы вложенного списка по возрастанию первых m элементов Решение. Если мы уверены, что все элементы действительно длиннее, чем m, то так: inisort[x ,m ]:=Sort[x,OrderedQ[ {Take[#1,m],Take[#2,m]}]&] В противном случае нужно вначале раздуть более короткие элементы впра- во посредством -Infinity. По умолчанию порядок на вложенных списках таков: вначале списки сортируются по длине, а потом списки данной длины сортируются лекси- кографически. Иными словами, применяется не чисто лексикографический порядок Lex, а LengthLex. 9.4. Задайте функцию, сортирующую вложенные списки чисто лексико- графически, не обращая внимания на длину. 391 9.5. Упорядочите числа от 1 до n лексикографически. Указание. Тот, кто читал Модуль 1, знает, что для этого достаточно превратить число в список цифр. По умолчанию Sort вообще не обращает внимания на глубину вложен- ного списка, иными словами, список {{x,y,z}} имеющий длину 1, предше- ствует списку {x,y}, имеющему длину 2. 9.6. Задайте функцию, сортирующую вложенные списки по глубине, а внутри данной глубины в обычном порядке. 9.7. Задайте функцию, сортирующую вложенные списки по глубине, а внутри данной глубины чисто лексикографически. Функция порядковой статистики Ordering является дополнительной к Sort. Вызванная без параметров, она возвращает позиции элементов спис- ка Sort[x] в исходном списке x. Для списка x, являющегося перестановкой Range[n], значение Ordering[x] это просто обратная перестановка. В случае списков с повторяющимися элементами функция Ordering возвра- щает позицию первого такого элемента. Как и функция Sort, она может указывать позиции при сортировке по критерию, но первым параметром для нее является отсечка по количеству элементов. Поэтому при задании критерия как второго параметра необходимо явно указывать дефолтное значение первого параметра, All. Ordering[x] положение элементов Sort[x] в x Ordering[x,n] положение первых n элементов Sort[x] в x Ordering[x,All,crit] положение элементов Sort[x,crit] в x Вот как, примерно, используется функция Ordering. 9.8. Найдите положение m-го по порядку элемента в списке x. Решение. Для этого нужно вспомнить, как выделяются части и уровни выражений. В данном случае, Ordering[x, {m}]. 9.9. Задайте функцию, которая сортирует список в соответствии со зна- чениями функции f на элементах этого списка. Решение. Вот решение из книги Вольфрама sortBy[list ,f ]:=list[[Ordering[Map[f,list]]]] 10. Простая сортировка. 169 Примерно 400 страниц книги Кнута 170 посвящено детальному изложе- нию нескольких десятков алгоритмов сортировки, с доказательством их корректности, вычислением среднего и худшего времени их работы, деталя- ми практической реализации и пр. Ясно, что мы не можем конкурировать 169 Always glad to share my ignorance — I've got plenty. 170 Кнут Д. Искусство программирования. Том 3. Сортировка и поиск М. – СПб – Киев: Вильямс, 2000. 822 с. 392 с Кнутом, да это и не нужно, так как большинство наиболее тонких алго- ритмов внешней сортировки, разработанных в то время, когда списки ключей не помещались оперативную память, имеют сегодня чисто истори- ческое и рекреативное значение. Если не работают обычные алгоритмы внутренней сортировки, рецепт здесь один — buy a larger and faster computer. В этом и следующем двух пунктах мы опишем и сравним некоторые простейшие алгоритмы сортировки. В действительности количество шагов алгоритма сортировки мало что говорит о его качестве. Во многих случаях нужно минимизировать другие параметры. • Количество сравнений. Ключи не обязаны быть числами, если клю- чи сами являются словами, строками, стрингами, их сравнение может быть в высшей степени нетривиальным. • Количество перестановок. Размер записей может быть очень велик. В этих случаях нужно минимизировать количество перемещений. Сортировка, в которой на каждом шаге происходит сравнение и пере- становка двух элементов, называется простой сортировкой. Вот три популярных общих метода простой сортировки, выполняющие сортировку в среднем за время O(n 2 ). • Простая обменная сортировка = сортировка перестановкой: на каждом шаге переставляются два элемента x и y образующие инверсию, т.е. такие, что x предшествует y, но x > y. • Простая сортировка выбором: выбирается минимальный среди неотсортированных элементов, и ставится на последнее место среди отсор- тированных. • Простая сортировка вставкой: берется первый среди неотсортиро- ванных элементов и вставляется на нужное место среди отсортированных. Существует много различных вариантов организации вычислений. На- пример, при обменной сортировке можно начинать либо с самого левого, либо с самого правого элемента, который меньше предыдущего, и продол- жать двигать его влево, пока при этом происходит уменьшение количества инверсий. После этого можно либо возвратиться к началу или концу спис- ка, либо — лучше!! — продолжать двигаться в том же направлении по списку в поиске еще одного элемента, который меньше предыдущего. С другой стороны, можно начать с самого левого или самого правого эле- мента, который больше следующего, и продолжать двигать его вправо, по- ка при этом происходит уменьшение количества инверсий. При примене- нии первой процедуры из списка {4,3,5,1,2} за один проход получится {1,4,3,5,2}. При применении второй первой тонет 4, в результате чего получается {3,4,5,1,2}, после чего начинает тонуть 5 и, окончательно, за один полный проход мы придем к {3,4,1,2,5}. За еще один полный проход получится {3,1,2,4,5} и т.д. Для наглядности эту ситуацию описывают так, как будто список расположен вертикально и маленькие = легкие эле- менты поднимаются, а большие = тяжелые — опускаются. 393 10.1. Реализуйте простую обменную сортировку полнопроходным мето- дом пузырька: на каждом шаге самый нижний элемент, меньший чем предыдущий, начинает всплывать, и всплывает, пока не наталкивается на меньший элемент, после этого начинает всплывать следующий элемент, меньший, чем предыдущий и т.д. Дойдя до начала списка, мы возвра- щаемся к его концу и делаем следующий проход. Решение. Вот один шаг рекурсивного алгоритма, в стилистике сурового минимализма: bubble[ {}]:={}; bubble[{x }]:={x}; bubble[x ]:=If[OrderedQ[Last[x],Last[Most[x]]], Append[bubble[Append[Most[Most[x]],Last[x]]], Last[Most[x]]], Append[bubble[Most[x]],Last[x]]] Вот тот же шаг в процедурном жанре: bubble[x ]:=Block[ {i,y=x},For[i=Length[x],i>1,i--, If[y[[i]] Return[y]] После этого остается лишь положить bubblesort[x ]:=FixedPoint[bubble,x] 10.2. Реализуйте простую обменную сортировку методом пузырька в сле- дующем варианте: на каждом шаге самый нижний элемент, меньший чем предыдущий, начинает всплывать, и всплывает, пока не наталкивается на меньший элемент, после чего мы снова возвращаемся к концу списка. 10.3. Реализуйте простую обменную сортировку полнопроходным методом пузырька в варианте, когда всплытие пузырьков начинается сверху, а не снизу. 10.4. Если метод пузырька сортирует список длины 100 за 0.2 секунды, то сколько времени ему понадобится, чтобы отсортировать список длины 500? А теперь проведите эксперимент. 10.5. Реализуйте простую обменную сортировку полнопроходным мето- дом грузика: на каждом шаге самый верхний элемент, больший, чем сле- дующий, начинает тонуть, и тонет, пока не наталкивается на больший эле- мент. После этого начинает тонуть следующий элемент и т.д. Дойдя до конца списка, мы возвращаемся к его началу и делаем следующий проход. Решение. Если без фантазии, то bubble 7→plummet, Last7→First, Most7→Rest, Append7→Prepend. И, конечно, не забудьте заменить неравенство в тесте на противоположное — или переставить исходы в If. 10.6. Реализуйте простую обменную сортировку методом грузика в сле- дующем варианте: на каждом шаге самый верхний элемент, больший, чем 394 следующий, начинает тонуть, и тонет, пока не наталкивается на больший элемент, после чего мы снова возвращаемся к началу списка. 10.7. Реализуйте простую обменную сортировку методом шейкера: на нечетных шагах всплывает пузырек, на четных — тонет грузик. Во сколько раз — и почему — этот метод лучше двух предыдущих? 10.8. Реализуйте алгоритм простой случайной сортировки: два слу- чайно выбранных элемента x i и x j , i < j, списка x переставляются, если x i > x j 10.9. Экспериментально оцените, сколько раз следует применить случай- ную сортировку, чтобы список длины n оказался отсортированным с веро- ятностью 90%. 10.10. Реализуйте простую сортировку выбором для списков без повторе- ний. Решение. Если без рекурсии, то, например, так: selectsort[x ]:=Block[ {y={},z=x,w}, Nest[(w=Min[#];y=Append[y,w];z=DeleteCases[z,w])&, z,Length[x]-1];Return[y]] Здесь y обозначает отсортированную, а z — неотсортированную часть x. Зачем мы ввели локальную переменную w? Кстати, что произойдет здесь, если список x содержит повторения? 10.11. Реализуйте рекурсивный алгоритм простой сортировки с выбором максимума вместо минимума. 10.12. Задайте функцию, которая за время O(log(n)) ставит элемент y на нужное место в отсортированном списке x длины n. Решение. Например, обычным методом деления пополам: locate[ {},y ]:={y}; locate[ {x },y ]:=If[OrderedQ[{x,y}],{x,y},{y,x}] locate[x ,y ]:=Block[ {n=Length[x],l=Floor[n/2]}, If[OrderedQ[ {y,x[[l]]}], Join[locate[Take[x,l],y],Take[x,l-n]], Join[Take[x,l],locate[Take[x,l-n],y]]]] Первые две строки задают начальное условие, а остальные строки — ре- куррентную процедуру, которая вызывает функцию locate либо для пер- вой, либо для второй половиеы списка. Переменные l и n задекларирова- ны в качестве локальных переменных не столько для того, чтобы вычис- лять Length и Ceiling один раз, сколько для того, чтобы сократить текст. При последовательном сравнении y с элементами списка x стартуя с его начала или конца в худшем случае понадобится n сравнений, а вовсе не log 2 (n) + константа. 10.13. Реализуйте простую сортировку вставкой для списков без повторе- ний. 395 11. Быстрая сортировка. 171 Ни один из методов простой сортировки не может дать в сред- нем время лучше, чем O(n 2 ). Чтобы получить лучшее время, необходи- мо работать не с индивидуальными элементами, а с подсписками. Вот два простейших метода коллективной сортировки, достаточные для большин- ства практических целей. • сортировка с убывающим смещением: алгоритм Шелла и его варианты в худшем случае дают время O(n 1.5 ). • сортировка разделением: алгоритм Хоара = быстрая сортировка = quicksort дает время O(n ln(n)) в среднем, а его версии, использующие нелинейную структуру, такие, как пирамидальная сортировка = сортиров- ка кучками = heapsort — даже в худшем случае. При небольших n, скажем n ≤ 1024, удобно применять алгоритм Шел- ла 172 . Чтобы объяснить, в чем он состоит, полезно вначале вспомнить про- стейший случай сортировки слиянием, который предложил фон Нейман в 1945 году 173 11.1. Даны два непересекающихся отсортированных списка x и y. Задать функцию, сортирующую Join[x,y] за время O(n), где n — максимум длин x и y. Решение. Если полностью соблюдать симметрию между x и y, то, напри- мер, так onion[x , {}]:=x; onion[{},y ]:=y; onion[x ,y ]:=If[First[x] Prepend[onion[x,Rest[y]],First[y]]] В простейшем варианте алгоритм Шелла можно описать так: • На первом шаге упорядочиваются пары {x i , x ⌊n/2⌋+i }. • На втором шаге упорядочиваются четверки {x i , x ⌊n/4⌋+i , x ⌊n/2⌋+i , x ⌊3n/4⌋+i }. • На третьем шаге упорядочиваются восьмерки {x i , x ⌊n/8⌋+i , x ⌊n/4⌋+i , x ⌊3n/8⌋+i , x ⌊n/2⌋+i , x ⌊5n/8⌋+i , x ⌊3n/4⌋+i x ⌊7n/8⌋+i , }. И так далее. Преимущество этого алгоритма по сравнению с простой сор- тировкой состоит в том, что здесь сохраняется структура, возникшая на предыдущих шагах. А именно, на каждом шаге в каждом блоке происхо- дит слияние двух упорядоченных списков одинаковой длины, а мы знаем, 171 Hoare's Law of Large Problems: Inside every large problem there is a small problem struggling to get out. 172 D.L.Shell, A high-speed sorting procedure. — Comm. Ass. Comp. Mach., 1959, vol.2, N.7, p.30–32. 173 J. von Neumann, Collected Works, vol.5, MacMillan, N.Y., 1963, p.196–214. 396 что эта операция может быть осуществлена за линейное время. Деталь- ный анализ этого алгоритма проведен в упомянутой выше книге Кнута 174 , стр.102–115, где в частности, доказан (нетривиальный!) результат Папер- ного и Стасевича, утверждающий, что в худшем случае сложность этого алгоритма равна O(n 1.5 ). 11.2. Реализуйте алгоритм сортировки Шелла. В действительности, конечно, здесь можно брать любую убывающую последовательность смещений, последнее из которых равно 1, совсем не обязательно последовательность bn/2c, bn/4c, bn/8c, . . . , 2, 1. Более того, известно, что некоторые другие последовательности смещений в среднем дают лучший результат, чем приведенная выше последовательность. 11.3. Реализуйте алгоритм сортировки Шелла для другой последователь- ности смещений. Указание. Начать нужно, конечно, с алгоритма слияния более чем двух отсортированных списков. Однако, для больших n алгоритм Шелла заведомо проигрывает алго- ритмам сортировки разделением. Самый старинный этих алгоритмов, ал- горитм Хоара, названный самим автором quicksort 175 , по-детски прост. На каждом шаге этого алгоритма выбирается пивот 176 . После этого сорти- руемый список разделяется на два подсписка: элементы, меньшие пивота, и элементы, не меньшие пивота, к каждому из которых отдельно применя- ется quicksort. Сам Хоар выбирал в качестве пивота больший из первого и последнего элемента. 11.4. Реализуйте алгоритм Хоара. Решение. Прежде всего, выберем пивот: pivot[x ]:=If[First[x]>Last[x],First[x],Last[x]] А теперь определим рекуррентную процедуру quicksort[ {}]={}; quicksort[{x }]:={x}; quicksort[x ]:=Join[quicksort[Select[x,# quicksort[Select[x,#>=pivot[x]&]]] 11.5. Убедитесь, что уже в этом самом примитивном варианте quicksort во много десятков раз эффективнее простой сортировки. Сравните время сортировки списков длины 500 или 1000 и максимальную длину списка, который можно отсортировать за 10 секунд. 11.6. Напишите итеративную программу, реализующую quicksort. 174 Кнут Д. Искусство программирования. Том 3. Сортировка и поиск М. – СПб – Киев: Вильямс, 2000. 822 с. 175 C.A.R.Hoare, Quicksort, Computer J., 1962, vol.5, N.1, p.10–15. 176 В компьютерной литературе используется несколько десятков различных перево- дов термина pivot на русский: опорный элемент, ведущий элемент, средний элемент, главный элемент, центральный элемент, . . . Это разнообразие побудило нас вообще от- казаться от перевода. 397 Алгоритм Хоара в среднем производит сортировку за время O(n ln(n)), но при неудачном выборе пивота в худшем случае получается время O(n 2 ). Ясно, что алгоритм Хоара работает тем лучше, чем ближе длина каждого из двух получающихся списков к половине длины исходного списка, иными словами, чем ближе пивот к медиане. 11.7. Определить медиану списка из трех элементов Решение. По любому, хотя бы так: medi[ {x ,y ,z }]:=If[x 11.8. Реализуйте quicksort в следующем варианте. На каждом шаге в качестве пивота выбирается медиана трех случайных элементов списка x. 11.9. Напишите программу сортировки, которая переключается между quicksort и алгоритмом Шелла как только длина n неотсортированного фрагмента становистя ≤ 1000. Имеются более эффективные, чем quicksort алгоритмы сортировки, ко- торые вводят на списке дополнительную нелинейную структуру, использу- ют дополнительную память (скажем, строят вспомогательные массивы ука- зателей или запоминают результаты предыдущих сравнений), используют случайность. Однако, все эти усовершенствования сказываются только на времени сортировки худшего случая и на константах, порядок скорости алгоритма в среднем O(n log(n)) не улучшается. 12. Порядковая статистика. 177 Задача порядковой статистики состоит в следующем: дан список x длины n и целое число m, 1 ≤ m ≤ n, требуется найти элемент y, который стоит на m-м месте в отсортированном списке x. Мы уже упоминали функцию Ordering, которая решает эту задачу в следующей форме: она указывает позицию такого элемента y в исходном списке. 12.1. Определите функцию, решающую задачу порядковой статистики. Решение. Скажем, так orderstat[x ,m ]:=x[[Ordering[x, {m}]]] Правда, при этом ответ получается в формате {y}. Частными случаями этой задачи являются задача нахождения миниму- ма – при m = 1, максимума – при m = n и медианы – при m = (n + 1)/2, для списков нечетной длины 178 . Все эти функции имплементированы в системе. Max[x] максимум списка x Min[x] минимум списка x Median[x] медиана списка x Mean[x] среднее арифметическое списка x 177 The IQ of the group is the lowest IQ of a member of the group divided by the number of people in the group. 178 Для числовых списков четной длины медианой часто называют среднее арифме- тическое n/2-го и (n/2 + 1)-го элементов отсортированного списка. 398 Кроме того, можно ставить обратную задачу, найти позицию элемента y в отсортированном списке. Очевидно, что для того, чтобы найти максимум и минимум списка до- статочно произвести O(n) операций. 12.2. Найдите минимум списка, не пользуясь командами Min и Max. Решение. Процедурное решение очевидно: minimum[]=Infinity; minimum[x ]:=Block[ {y=Infinity,n=Length[x],i}, For[i=n,i>=1,i--,If[x[[i]] minimum[ {}]=Infinity; minimum[{x }]:=x minimum[x ]:=If[First[x] 12.3. Найдите максимум списка, не пользуясь командами Min и Max. Гораздо менее очевидно, что для того, чтобы найти медиану списка, до- статочно O(n) операций. 12.4. Найдите медиану списка, не пользуясь командой Median. Указание. Делением списка на две или, лучше на три части. С использованием команды Sort решение задач порядковой статистики тривиально. 12.5. Найдите m-й элемент отсортированного списка и положение элемента y в отсортированном списке. Решение. Да уж, тут высшего образования не надо: Sort[x][[m]] и Position[Sort[x],y]. Настоящая проблема состоит, естественно, в том, чтобы сделать это не сортируя список. 12.6. Напишите программу, которая за время O(n) ищет элемент, следу- ющий за y в списке, получающемся из x после сортировки. 12.7. Напишите программу, которая за время O(n) ищет элемент, предше- ствующий y в списке, получающемся из x после сортировки. 12.8. Напишите программу, которая за время O(n) ищет элемент, стоящий на m-м месте в списке, получающемся из x после сортировки. 12.9. Напишите программу, которая за время O(n) ищет позицию элемента y в списке, получающемся из x после сортировки. В действительности в системе и в пакете Statistics`DataManipulation` имплементированы многие другие функции порядковой статистики такие, как Quantile, BinCounts, RangeCounts, CategoryCounts, BinLists, Range- Lists, CategoryLists, и т.д. В общем случае скорость сортировки O(n ln(n)) асимптотически неулучшаема. Это утверждение, однако, перестает быть верным, если 399 нам — как это часто бывает! — известна априорная информация о стро- ении и вероятностном распределении ключей, например, если ключи яв- ляются последовательными натуральными числами, имеют естественную структуру прямого произведения или копроизведения и т.д. При подхо- дящих дополнительных предположениях сложность сортировки мало отличается от сложности порядковой статистики и извест- ны алгоритмы сложности O(n). • Сортировка зачерпыванием = bucketsort ≈ карманная сорти- ровка = binsort: распределение ключей • Поразрядная сортировка: используется, когда ключ состоит из нескольких полей, например, сортировка игральных карт по масти и рангу, сортировка дат по году, месяцу и числу. • Сортировка слиянием: в случае, когда список состоит из небольшо- го количества уже отсортированных фрагментов. 12.10. Напишите программу, которая сортирует трехзначные числа вна- чале по первой цифре, потом по второй, и, наконец, по третьей. “А свиного сала не покупаете?” сказала хозяйка, следуя за ним. “Почему не покупать? Покупаю, только после.” Николай Гоголь, Мертвые души § 3. Функции I have yet to see any problem, however complicated, which if you looked at it in the right way, did not become still more complicated. Paul Anderson To criticize mathematics for its abstraction is to miss the point entirely. Abstraction is what makes mathematics work. If you concentrate too closely on too limited an application of a mathematical idea, you rob the mathematician of his most important tools: analogy, generality, and simplicity. Mathematics is the ultimate in technology transfer. |