svetasmirnova | Recent Entries

ansible-playbook ругается если его запускать из директории с правами 777. К сожалению только так монтируется мой огромный WiFi внешний диск, где я храню файлы курсов и всякое большое. С курсами решается в два этапа:

Из директории курса: export ANSIBLE_CONFIG=`pwd`/ansible.cfg
Скопировать приватный ключ куда-то с нормальными правами и поправить все конфиги на абсолютный путь

Опять превысила квоту на корпоративном IMAP-сервере, делаю бэкап при помощи программы imapdump.pl и скриптика:


#!/bin/bash

imapdump.pl -d  -f /dir/to/store/emails -S "host:port/username/password" -m folder/subfolder

Эта программа сохраняет файлы в формате *.eml, но без расширений. Расширения добавляю скриптиком:


for i in `ls ./*`; do mv "$i" "$i.eml"; done

И затем создаю mbox file при помощи eml2mbox.rb:


eml2mbox.rb  /dir/to/store/emails

Почту можно читать mutt-ом:


mutt -f /dir/to/store/emails/folder

Часть 1. Reduction.

Что это такое: понятно из названия. Писать пометки по заданию смысла нет: всё решает опыт и немножко сообразительности.

Часть 2. Linear programming.

Задачи, которые могут быть решены при помощи Linear programming. Википедия опять рулит:

Linear programs are problems that can be expressed in canonical form:

$\begin{align}<br />& \text{maximize} && \mathbf{c}^\mathrm{T} \mathbf{x}\\<br />& \text{subject to} && A \mathbf{x} \leq \mathbf{b} \\<br />& \text{and} && \mathbf{x} \ge \mathbf{0}<br />\end{align}$

Какая переменная может войти в базис следующей? Те, которые вида 1 x xN и единственные в столбце - это уже базис, соответственно нужно выбирать из оставшихся с положительным коэффециэнтом.
Кто кандидат на покидание базиса? Подробно есть здесь Вкратце: делим правый столбец на коэффециэнты того, кто "входит", строка с меньшим получившимся значением - кандидат на выбывание.

Часть 1. Regular Expressions

The set of states that the NFA could be in after reading defined character sequence. Тут нужно перечислить, в которые можно попасть. Например, для выражения ((a*b)*) после прочтения a можно попасть только в b, а после прочтения b можно попасть и в конец выражения, и вернуться к скобке перед a и оттуда в a или в b.
Edges in the epsilon-transition digraph. Тут всё просто, но после нескольких пропущенных пришлось рисовать на бумажке.

Часть 2. Data Compression.

Huffman trie. Здесь было непонятно как построить trie, если все ноды повторяются уникальное количество раз, например: 1, 2, 3, 4, 5. Понимания добавила картинка из Wikipedia. Вкратце смысл такой: 1 и 2 составляют первую пару с суммой 3, 3 и 4 - вторую с суммой 7, но так как 5 < 7, то 5 образует пару с (1 и 2).
Expanding LZW. Здесь у меня возникла сложность с добавлением в словарь более, чем двухбуквенных последовательностей, особенно если они шли в паре с двухбуквенными. Какую вырать и какой по счёту? Наверное, опять-таки лучшее объяснение в Wikipedia
LZW compression. Те же проблемы, что и в предыдущем пункте, то же решение.

Knuth-Morris-Pratt DFA. Первоначально это задание мне показалось самым простым: нужно для каждой буквы пометить состояние, на которое нужно перемещаться на следующем шаге. Но оно же оказалось и самым сложным, потому что я пыталась делать его в уме и таким образом пропускала некоторые состояния. В результате несколько вариантов запорола. Помогло выписывать пройденный путь отдельной строкой: A B B A и т.п. В таком случае очень легко сравнить с искомой строкой и вероятность ошибки меньше.
Boyer-Moore algorithm. Для выполнения этого задания мне пригодился текстовый редактор: первая строка - текст, в котором искать, вторая строка - первый шаг, третья - второй и т.п. Пробелами располагаем где требуется: если знак в исходном тексте, находящийся на той же позиции, что и последний знак строки, которую мы ищем, совпадает с последним знаком - сдвигаем на одну позицию; совпадает с другим знаком в строке - совмещаем с последним нахождением этого знака; ни с чем не совпадает - сдвигаем всю строку на её длину.
Rabin-Karp hash function. Тут тоже всё элементарно: нужно воспользоваться формулой из слайдов. (((previous_reminder - first_sign_of_prev_sequence*( (R*num_symbols) % Q) ) * R + last_sign_of_cur_sequence) % Q + Q) % Q, где R - порядок

Multiway trie Что это такое - интуитивно понятно, повторяться не буду. Задание тоже проблем не вызвало: нужно построить trie и посчитать вообще все ненулевые ноды, то есть с каким-то контентом, неважно, есть ли у них ненулевые линки или нет.
Ternary search trie тоже интуитивно понятно. Единственное, формулировка вопроса вызвала непонимание с первого раза. "What are the depths of the nodes corresponding to the last characters in the 7 strings (in the order the strings were inserted)?" обозначает, что нужно перечислить глубину до последнего знака для каждой из строк, а я почему-то сначала единственную максимальную посчитала. Корень имеет глубину 0, поэтому если первая строка - "АБВ", го глубина "В" будет 2, а не 3.

Для решения обоих заданий пришлось рисовать на бумажке. Эффективного электронного способа сделать тоже самое не обнаружила.

Неделя 4 - это последняя неделя, посвящённая проекту №1: критическое ревью первой главы книги Daniel Coyle "The Talent Code".

Вкратце идея главы в том, что одного таланта недостаточно для успеха и нужно много работать, чтобы достичь его. С этой мыслью не поспоришь, да и пословица "без труда не вытащишь и рыбки из пруда" нам всем знакома с детства.

Автор приводит несколько примеров, когда кто-то тренирует какой-либо приём, например, футбольный финт с мячом, снова и снова, через сотни неудач, до тех пор, пока не получается.

На первый взгляд эта идея мне не показалась спорной. Честно говоря, я её пропустила как что-то очевидное. Однако на этой неделе мы должны были оценивать ревью других учеников и один (одна) из них заострил(-а) внимание на этом моменте.

Так вот: при работе мозгами нифига не работает. Я когда пишу что-то и возникает мёртвая точка, например, не могу придумать дизайн программы, не могу устранить баг, не могу найти способ найти баг и т.п. помогает встать и пойти поделать что-то другое, желательно физическое: в спортзал, погулять. Без отвлечения и другого взгляда на проблему решения не найти.

Такой вот итог недели 4, вроде бы напрямую с курсом не связанный.

LSD (least significant digit) sort очень простой. Допустим, что строки одинаковой длины и сортируем сначала по последнему знаку, затем по предпоследнему и так до конца. Задание сложностей не вызвало.
MST (most significant digit) sort. Аналогично предыдущему, но сортировать, начиная с первого знака. В задании просили результат после третьей итерации. Я зачем-то сортировала весь набор строк, а нужно-то: весь набор строк (1 итерация), затем первый отсортированный subarray (2 итерация), далее новый получившийся первый subarray (3 итерация).
3-way radix quicksort. Тут я читинговала и использовала программу: после ручной сортировки в прошом курсе мне несколько ночей наборы цифр снились.

Алгоритм Ford-Fulkerson-а дался мне тяжело. Я его поняла только после того, как нашла вот этот applet

Касательно задания нужно выбирать edges с максимальной (capacity - flow) и не идти по тем, где (capacity - flow) == 0. Если таких в нужном направлении нет, выбирать обратное.

В mincut же попадают все vertex-ы, от которых можно уйти с ненулевым (capacity - flow).

Часть 1. Minimum Spanning Trees.

Всё очень просто.

Kruskal's algorithm - проходить edges в порядке возрастания и добавлять, если не возникает циклов.
Prim's algorithm - всё тоже самое, но плясать от построенного дерева.

Единственная сложность в задании - не ошибиться в записи промежуточных ответов. К счастью, графическое представление графов сделано в ASCII, поэтому я просто копировала в текстовый файл и помечала пройденный edge ~~крестиками~~ буквой Х.

Часть 2. Shortest Paths.

Здесь для записи промежуточных ответов было удобно пользоваться LibreOffice Calc.

Dijkstra's algorithm - всё просто, relax a vertex, выбираем vertex с наименьшей дистанцией, relax его и так до победного.
Topological order - аналогично предыдущему, но vertex-ы выбираем в указанном порядке.
Bellman-Ford algorithm - а вот с ним я помучалась. Почему-то не сразу сообразила в каком порядке relax vertex-ы. А проходятся они на каждом шаге от первого до последнего. Вкратце:
1. Шаг 1. Все vertex-ы - infinity, кроме того, от которого считаем дистанцию. Он - 0. Relax первый vertex. Предположим, это D. Значит, A, B и С мы уже прошли. Их relax на этом шаге больше не нужно. А если D "открыл" последующие, скажем, E и F, их нужно relax по порядку. Причём, если D "открыл" E, а сумма расстояний от D-F-E меньше расстояния от D до E, менять ничего на этом шаге не нужно. А вот если расстояние D-E-F меньше расстояния D-F - значение для F изменить нужно.
2. Шаг 2. Проходим все vertex-ы, открытые на предыдущем шаге, в порядке возрастания. Опять-таки, никаких возвратов обратно.
3. Шаг 3. Аналогично шагу 2.

На этой неделе полезным показалось Reverse Outline - пометка на полях параграфа, вкратце описывающая его суть. Собственно, главное здесь: один параграф - одна мысль. Как раз во время peer review было заметно, что тяжело читать большие параграфы, содержащие две или более идеи.

Пытаюсь проходить курс "English Composition I: Achieving Expertise". Из первых двух недель полезное:

Quick write - писать 5 минут не переставая, чтобы расписаться. Впрочем, аналогичный приём я использовала при работе над книгой: ставишь таймер и час пишешь.
Правила цитирования. Их, оказывается, много! Вот несколько школ:
Мне больше понравилось пользоваться Purdue OWL Упражнения я делаю в стиле MLA. Надо ещё CSE и Chicago пристальнее посмотреть.
Ещё, оказывается, нужно следовать правилам цитирования, даже если используешь собственную публикацию.
Ещё несколько ссылок:

Тут тоже имеет смысл сделать заметки только по тестам.

1. Breath-first search.

Аналогично предыдущему заданию.

2. Topological order.

Делаем depth-first search, но запоминаем nodes в порядке убывания из очереди. Затем этот список возвращаем в обратном порядке.

Так, для A->B->C D->E, сначала получим список C B A E D и правильным ответом будет D E A B C

3. Strongly-connected components.

Почти аналогично предыдущему, но components выбирать следующим образом: взять букву, пройти depth-first search-ем все слинкованные nodes; если остались неслинкованные - взять следующую букву из списка.

Reference: algs4.cs.princeton.edu/40graphs/

Попишу-ка я технические заметки про этот курс.

По опыту предыдущего курса: к экзамену забываются, во-первых, требуемый формат ответов, а во-вторых, что-то из усвоенного материала.

Тесты:

1. Depth-first search.

Что такое depth-first search - интуитивно понятно: берём текущую node, проходим путь от неё до тупика, возвращаемся к предыдущей node, проходим от неё до тупика и т.д. пока не доберёмся до цели. Пройденные node дважды не проходятся.

Сложность вопроса: выбрать порядок, принимаемый auto-grader, так как алгоритм сам по себе порядка не определяет.

Решение: смотреть только на текстовое представление графа и не обращать внимание на визуальное.

То есть если есть A: E B F, то надо первым выбрать E, пройти весь путь и только вернувшись обратно пройти сначала B, потом F.

2. Breath-first search.

Аналогично: не смотреть на картинку. Естественно, порядок будет: A E B F, потом по горизонтали E, B и F.

3. Connected components.

Совсем просто: как на слайдах пронумеровать по принадлежности к группе. Тут картинка, наоборот, всё упрощает.

Reference: algs4.cs.princeton.edu/41undirected/

Как и на других курсах Coursera в курсе по дизайну домашние задания проверяют сокурсники. Казалось бы что такого, однако оказалось очень эффективно.

Одно из заданий там на примитивные навыки рисования: рисовать стул в разных проекциях и ракурсах. В частности, один раз нужно было нарисовать его в горизонтальной перспективе, как будто он на одной плоскости с глазами. Я, конечно, совсем плохо рисую. Но нарисовала, показалось, что правильно, послала. Уже после заметила, что в одном месте вертикальную линию наврала. Стала проверять работы других: у четырёх из пяти перспектива неверная. Потом посмотрела на свой рисунок и увидела, что проблема там не в одной вертикальной линии. Что называется: просто смени роль.

Другое открытие. Основной проект для домашнего задания на этом курсе - какой-то объект, для которого нужно придумать дизайн. Я выбрала web-проект, так как мне показалось, что раз я это умею, то смогу выкроить время. Продумала что буду делать, однако на одном из заданий потребовалось спроектировать 10 альтернативных вариантов. Ну не разные же оформления странички делать? Стала думать ширше. И таки придумала несколько альтернативных вариантов, которые имеет смысл делать.

Прохожу сейчас два курса: MongoDB for DBAs и Design: Creation of Artifacts in Society.

По первому впечатления как обычно: не воспринимаю я 75% информации на слух, эффективнее читать. А по второму, можно сказать, гуманитарному, всё с точностью наоборот: отлично видео идёт.

Этот эффект точно не говорит о том, что курс про Mongo плох: я так большинство воспринимаю.

Какое-то время назад по наводке из ЖЖ-сообщества su_bodybuilding решила попробовать методику Фалеева. Только базовые упражнения, 5Х5, прибавляя вес каждую тренировку до своего максимума, далее циклы. Где нельзя добавлять, прибавлять повторы в подходе. Я от 5 до 10 делаю.

По факту можно сказать: работает. Во всяком случае в приседаниях я 12,5 кг прибавила. С остальным хуже. И что мне особенно нравится - это то, что стало видно какую подсобку нужно делать~~, а на какую забить~~.

Иногда у меня такое впечатление, что я живу в каком-то другом мире, отличном от остальных людей.

Например, женщины, живущие в Турции, утверждают, что здесь все сильно опаздывают. Они вызывают, скажем, электрика к двум, а он приходит в лучшем случае в четыре, а то и на следующий день.

То, что к нам большинство приходило вовремя, я списывала на тот факт, что в городе живёт много иностранцев и местная культура сервиса может отличаться от других мест.

Мы решили в первый раз здесь пойти в кино. Купили билеты, погуляли и вернулись минут за пять до объявленного начала сеанса. Какого же было наше удивление, когда обнаружилось, что ~~журнала не было~~ фильм вовсю идёт!

Ещё из особенностей местного кмнопоказа: где-то через час нам продемонстрировали обрывок плёнки, молча включили свет и народ начал бодро расходиться. Это был явно не конец фильма, к тому же кто-то ещё оставался на своих креслах. Мы решили подождать. Однако после странного начала сеанса думали разное. Минут через 10 все вернулись с едой и напитками: они знали! Оказывается, это был перерыв.