04.03.2015

Парадоксы Зенона

Бесконечность интересная и таинственная вещь. Но совершенно не понятно может ли наш мозг понять и принять ее? Я уже рассказывал вам о бесконечном отеле Гильберта и мне все это кажется чем-то ненатуральным, чьей то безумной фантазией. Но бесконечность может быть гораздо ближе к реальности, чем закрома нашего разума. Предлагаю вашему внимаю два парадокса о движении, которые сформулировал Зенон Элейский где то в 5 веке до нашей эры.

Чтобы по-настоящему насладится этими парадоксами, надо знать, что рациональные числа обладают свойством плотности. Оно говорит нам следующее: между двумя неравными рациональными числами всегда можно найти рациональное число которое меньше большего числа и больше меньшего. То есть: ∀(a,b ∈ Q)∃(m ∈ Q): a<b ⇒ a<m<b. Это свойство позволяет нам говорить о том, что между вещественными числами 0 и 1 существует бесконечное число рациональных чисел (½, ⅓, ¼, ⅕, ..., ∞). Доказательство.

Гонка Ахиллеса и черепахи

Устроим небольшое воображаемое соревнование. На стартовой линии стоит греческий герой Ахиллес, воин и атлет, символ скорости и силы своего времени. И черепаха. Что? Черепаха? Бред, как черепаха может соревноваться с Ахиллесом? Я думаю, вы бы не стали возражать, если бы мы дали черепахе фору в 100 метров для того, чтобы Ахиллесу пришлось хотя бы немного размять свои мышцы перед триумфальной победой. Предположим, что в целом нашим спортсменам надо преодолеть дистанцию в 1000 метров.

Кстати, на кого вы бы поставили ¤ в этой математической гонке?

Судья взводит стартовый пистолет. На старт, внимание, бдыщь!

Для того, чтобы Ахиллесу обогнать черепаху, ему необходимо сначала ее догнать. Пока Ахиллес бежит 100 метров форы черепаха пробегает еще 10. Черепаха вновь впереди Ахиллеса, он вновь бросается ее догонять и пробегает еще 10 метров. В это время черепаха проползает еще 1 метр. Этот процесс может продолжаться до бесконечности, в которой Ахиллес так и не догонит черепаху.

Проиграли ставку? Но это ничего, ведь деньги у нас не настоящие (в отличии от банков ☺).

Википедия дает данную формулировку этого парадокса:

Допустим, Ахиллес бежит в десять раз быстрее, чем черепаха, и находится позади неё на расстоянии в тысячу шагов. За то время, за которое Ахиллес пробежит это расстояние, черепаха в ту же сторону проползёт сто шагов. Когда Ахиллес пробежит сто шагов, черепаха проползёт ещё десять шагов, и так далее. Процесс будет продолжаться до бесконечности, Ахиллес так никогда и не догонит черепаху.

Представить такую гонку на компьютере нет возможности. Как думаете, почему? Потому что компьютер не может делить бесконечно, так как у нас нет бесконечной памяти, чтобы хранить числа произвольной длинны. Благодаря этим свойствам Ахиллес и черепаха в компьютерной гонке все же окажутся в одной точке. Но, несмотря на это, ее смысл мы можем представить так:

1000 метров
И так до бесконечности.

Давайте сделаем еще одну визуализацию. Для этого мне понадобятся ваши руки. Расставьте их на расстоянии одного метра. Правая рука стоит не подвижно, а левая начинает движение к ней. Но не плавное, сначала левая рука приближается к правой на половину начального расстояния, то есть на 50 сантиметров. Потом на половину полученного расстояния, то есть на 25 сантиметров, потом на половину этого и так далее. До бесконечности. Забавно, да? Вы только что завершили бесконечный процесс своим хлопком.

Еще одна хорошая визуализация, которую опять же нельзя по настоящему представить на компьютере, это построение квадрата из бесконечного числа прямоугольников. Берем квадрат, скажем, 100 на 100 единиц измерения, делим его пополам, одну половину делим еще раз на две равные части, еще одну полученную половину делим пополам. И так далее, до бесконечности. Да, наш конечный квадрат состоит из бесконечного числа меньших прямоугольников:

Так о чем это? О бесконечном процессе и его конечном завершении. Как же Ахиллесу удается настичь и обогнать черепаху в этой нелегкой гонке? Почему наши руки сходятся в хлопке, завершая процесс у которого нет финального шага? И еще: как конечный кусок материи может состоять из бесконечного числа частиц, как в случае с нашим квадратом?

Дихотомия

Дихотомия в переводе с греческого значит «Деление пополам», именно так Аристотель назвал этот парадокс Зенона.

Давайте представим что мы решили прогуляться в парк. Парк находится от нас в 100 метрах. Для того, чтобы пройти 100 метров, надо сначала пройти 50 метров. А для того, чтобы пройти 50 метров, нам надо пройти 25 метров. Вы уже поняли к чему я клоню? Да, к бесконечности процесса деления этого расстояния. Движение невозможно!

Есть забавная выдержка в которой противник Зенона, чтобы доказать обратное, начал просто ходить перед ним:

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

Википедия дает нам такую формулировку этого парадокса:

Чтобы преодолеть путь, нужно сначала преодолеть половину пути, а чтобы преодолеть половину пути, нужно сначала преодолеть половину половины, и так до бесконечности.

Представим это визуально:

100 метров
или подождем еще минутку?

Как мы видим, этот парадокс похож на парадокс Ахиллеса и черепахи, только в отличии от последнего, у него отсутствует точка старта — что и делает невозможность совершить шаг.

Заключение

Данные парадоксы обсуждаются уже более 2000 лет, и, как говорит нам Википедия, научное сообщество до сих по не пришло к общему мнению о сущности парадоксов. Мне нравятся эти парадоксы тем, что они, при достаточном погружении в их суть, задают интересные вопросы, которые, как мне кажется, уходят корнями во что-то очень базовое:

  • Как бесконечное действие может завершиться?
  • Есть ли конечная мера у времени и пространства, или его можно делить до бесконечности?
  • Если время можно делить бесконечное число раз, тогда как быть с такими вот парадоксами?
  • Если пространство бесконечно, то как конечные предметы могут состоять из бесконечного числа частиц?
  • Как физический процесс за конечное время принимает бесконечное множество значений?

Я говорю с позиции профана и в этих вещах не разбираюсь, если у вас есть ответы на эти вопросы, я бы очень хотел прочитать о них в комментариях к посту. Или, возможно, у вас возник тоже какой-то интересный вопрос?

В качестве бонуса интересное видео по теме:

14.05.2014

Понимание русских

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

Перевод описания со страницы курса:

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

Целью курса является предоставление студентам широкого обзора базовых принципов которые руководят прошлыми, настоящими и будущими взаимодействиями между Россией и западом, сфокусированными на культуру и национальную психологию русских и западных европейцев.

15.01.2014

Задача о n-ферзях

В это статье мы на примере шахматной проблемы n-ферзей рассмотрим как соединить наши знания о рекурсивных функциях и представлении данных в виде деревьев для решения сложных проблем. Если вы не читали предыдущие статьи (рекурсия, деревья) то советую их изучить перед продолжением чтения этой статьи. Для решения задачи мы так же изучим еще пару интересных трюков: как с помощью рекурсии создавать деревья и как в них искать данные методом поиска с возвратом. Я надеюсь, что я заинтриговал вас. Приступим.

Постановка задачи

Для начала определим задачу. На шахматной доске с заданным размером n клеток по ширине и n клеток по высоте, всего n×n клеток, необходимо расставить n ферзей так, чтобы каждый ферзь не атаковал друг друга. Для простоты поставим себе задачу найти первое возможное решение.

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

Ферзь ходит по красным клеткам

Приведем пример почти решенной задачи для доски 4 на 4. Попробуйте сами закончить это решение кликнув на нужной ячейке:

Кликните на клетку где должен стоять ферзь

А вот одно из возможных решений для доски 8 на 8:

Задача не такая простая, как может показаться. К примеру, общее число расположения ферзей на доске 8 на 8 равняется 4 426 165 368. Разумеется, человек не будет решать эту задачу за счет простого перебора, но в любом случае при возрастании доски сложность увеличивается во много раз, и тут нам на помощь приходит компьютер.

Анализ проблемы

Разберем нашу проблему на составляющие.

Первое что приходит на ум при разборе любой шахматной проблемы это шахматная доска. Поскольку наша доска квадратная, она имеет только один параметр, который отвечает за высоту и ширину — назовем его размерность и обозначим n. Доска с размерностью n=8 имеет высоту и ширину в 8 клеток. Всего на данной доске 8×8=64 клетки:

n
n

Каждая клетка имеет координаты вида ряд:столбец. Она может быть пустой, или на ней может находится ферзь.

Ферзь атакует другого ферзя если они находятся на одном ряду, или на одной колонке, или на одной из диагоналей (слева-направо, справа-налево).

атак(x,y)⇔(ряд(x)=ряд(y))⊕(кол(x)=кол(y))⊕(диа_лп(x)=диа_лп(y))⊕(диа_пл(x)=диа_пл(y))

Решением является доска, которая удовлетворяет следующим условиям:

  1. Количество установленных на доске ферзей равно размерности доски.
  2. Ни один ферзь не атакует другого.

решена(доска)⇔(колво_ферзей=n)∧∀x.¬∃y.атак(x,y)

Алгоритм решения

Самое сложное при решении любой проблемы, а тем более незнакомой, это сделать первый шаг. Не пытайтесь объять незнакомую проблему разом, первый шаг должен быть максимально простым.

Мы начинаем с пустой доски. Представьте себе доску с минимальной размерностью. n=1? Нет, слишком тривиально. n=2? Вот этот вариант нам подходит.

Взглянем еще раз на условие решения: на доске должно находиться n ферзей и ни один ферзь не должен атаковать другого. Начнем с первой части этого условия: надо поставить n фигурок. Как мы это сделаем?

Маленький шаг для человека, большой шаг для решения проблемы. Поставим ферзя в клетку с рядом 1 и колонкой 1 (1:1):

Поскольку у нас размерность доски n=2, то по условию нам остается поставить всего одну фигурку. Поставим ее в первую свободную клетку:

Посмотрим на условие еще раз. Две фигурки есть, следовательно, первую часть условия мы удовлетворили. Вторая часть условия гласит, что ни одна фигурка не должна атаковать другую. Напомню, что ферзь атакует по своему ряду, колонке или диагоналям. Получается, что вторую часть условия мы не удовлетворили — наш первый ферзь атакует второго, так как они находятся на одном ряду:

Но не будем унывать, уберем второго ферзя с доски и поставим его в клетку 2:1. Теперь первый ферзь атакует второго ферзя по вертикали:

Опять уберем его и поставим в оставшуюся клетку, которую мы не попробовали — 2:2. Но и тут наш воинственный первый ферзь не дает соседу покоя атакуя его по диагонали:

Все ли варианты мы попробовали? Нет, еще можно переставить самого первого ферзя из клетки 1:1 на клетку 1:2 и попробовать решить с этой начальной позицией. Если и так не получится, то можно попробовать еще клетки 2:1 и 2:2 в качестве начальной позиции. Для доски с размерностью n=2 уже по этим вариантам можно заключить что решения не существует, но если мы посмотрим на решение для доски с размерностью n=8, которое мы приводили выше, то заметим, что там первая клетку свободна, следовательно менять позицию первого установленного ферзя имеет смысл.

Наша попытка не увенчалась успехом в виде решения задачи, но мы получили нечто большее — алгоритм. И, если с него скинуть частные детали, то его можно будет применить для решения задачи с любой размерностью доски. Давайте немного формализуем то, что мы описали выше. Для большей наглядности и простоты предположим, что размерность доски больше единицы:

  1. Начинаем с пустой доски.
  2. Ставим фигурку в первую свободную клетку:
    1. Если фигурка атакует другую, тогда переставляем ее на следующую свободную клетку:
      1. Если больше нет не попробованных клеток, тогда возвращаемся к предыдущей установленной фигурке и переставляем ее:
        1. Но если текущая фигурка является начальной, тогда предыдущей быть не может, следовательно задача не имеет решения.
    2. Если количество фигурок равно размерности доски тогда данная доска является решением.
    3. Если количество фигурок меньше размерности доски тогда берем еще одну фигурку и возвращаемся к пункту 2.

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

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

Представим это визуально:

Нажмите чтобы проиграть демо

Решение

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

Самое очевидное это представить доску в виде матрицы размером n строк, в каждой строке n элементов. Но это можно сделать проще: в виде одного плоского массива n×n элементов. Каждый элемент этого массива представляет собой клетку. Клетка может иметь два состояния: пустая, с фигурой. Давайте условимся что пустая клетка будет представляться булевой константой false, а клетка с фигурой будет представляется булевой константой true. Для простоты давайте называть такие данные не массив а Board. Давайте попробуем представить доску с размерностью n=4, и решение для этой доски:

/** B представляет пустую клетку
  * @type {CellState}
  */
var B = false;

/** Q представляет клетку с ферзем
  * @type {CellState}
  */
var Q = true;

/** Пустая доска с размерностью n=4
  * @type {Board}
  */
var n4emptBrd = [B, B, B, B,
                 B, B, B, B,
                 B, B, B, B,
                 B, B, B, B];

/** Решение для доски с размерностью 4
  * @type {Board}
  */
var n4solBrd = [B, Q, B, B,
                B, B, B, Q,
                Q, B, B, B,
                B, B, Q, B];

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

Каждый раз вручную создавать доску в виде большого массива не удобно. Поэтому нам бы не помешала функция которая делала бы это за нас. Назовем ее createEmptyBoard. Реализовать ее просто: создаем пустой массив и заполняем его пустыми значениями n×n раз:

/** Создает пустую доску n*n элементов
  * @param  {Natural} n Размерность доски
  * @return {Board}
  */
function createEmptyBoard(n){
  var b = [];
  for(var i=0;i<n*n;i++){ b.push(B); }
  return b;
}
// Тесты для функции createEmptyBoard
(function(){
  console.log("Тест1:", createEmptyBoard(4).length==16);
})();

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

Все приготовления закончены и мы можем приступать к функции которая будет решать проблему n-ферзей. Это уже задачка посложнее. Для начала давайте подумаем что должна принимать и возвращать эта функция. По нашему алгоритму она принимает пустую доску и возвращает доску с решением. А если решения нету, как у доски с размерностью 2? Мы не обговорили этот момент при проектировании алгоритма, так что пусть это будет false.

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

Самый тривиальный случай для этой задачи это n=1. Тот самый, который мы проигнорировали при проектировании алгоритма. Решением для этой доски будет доска с одной клеткой, в которой установлен ферзь. Для доски с размерностью n=2 решения нету, мы это узнали при проектировании алгоритма. А для доски с размерностью n=4 мы уже записали решение в коде чуть выше.

Для того чтобы наши тесты сразу начали приносить пользу нам надо написать заглушку для функции. Кстати, мы забыли ее назвать, пусть она называется solve. Заглушка должна возвращать значение которая реальная функция может вернуть, поэтому пусть это будет false. Перенесем в код то, о чем мы сейчас рассуждали:

/** Решает проблему n-ферзей
  * @param  {Board} b Доска
  * @return {Board | false} Если задача имеет решение - доску
  *                         Иначе false
  */
function solve(b){ return false; } // заглушка

(function(){
  console.log("Тест2:",
    solve(createEmptyBoard(1)).toString()==[Q].toString());

  console.log("Тест3:", solve(createEmptyBoard(2))==false);

  console.log("Тест4:",
    solve(createEmptyBoard(4)).toString()==n4solBrd.toString());
})();

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

Теперь самое время подумать над наполнением функции. В процессе разработки алгоритма мы заметили что он генерирует данные с древовидной структурой. Из предыдущей статьи мы научились мастерски обрабатывать такие данные используя функции со взаимной рекурсией. Напоминаю, для того чтобы обработать древовидные данные нам надо создать две функции. Одна из них оперирует над узлом дерева, который в контексте этой проблемы представляет собой доску, с установленными фигурками или без них. Вторая оперирует над потомками данной доски, которые мы получаем устанавливая фигурки в свободные клетки на данной доске. Первую назовем solveBrd, а вторую solveChilds. Обе эти функции вложим в нашу функцию solve с помощью замыкания, так же закомментируем заглушку за ненадобностью:

// function solve(b){return false}; // заглушка
function solve(b){
   // Ищет решение для данной доски
   // @param {Board} b
   // @return {Board | false}
  function solveBrd(b){

  }

  // Ищет решения для списка потомков
  // @param {array of Board} lob
  // @return {Board | false}
  function solveChilds(lob){

  }

  return solveBrd(b);
}

Про замыкания можно почитать в Википедии.

Функция solveBrd принимает доску, которая может поступить из функции solve или из функции solveChilds, потому что мы используем взаимную рекурсию. Поскольку доска поступающая из solveChilds содержит в себе фигурки логично было бы узнать является ли она решением. Поэтому давайте пожелаем чтобы у нас была функция isSolved, которая принимает доску и возвращает true если доска является решением. Если поступившая в функцию solveBrd доска является решением задачи тогда ее надо вернуть, и функция solve завершит свою работу. В противном случае поочередно, для каждой свободной клетки на данной доске, надо поставить фигурку. Из получившегося массива досок надо удалить не валидные доски, так как обрабатывать их и их потомков не имеет смысла потому что они не могут содержать решения. Не валидной является доска на которой одна фигурка атакует другую. Давайте представим процесс формирования данных досок, у не валидных досок красный фон:

Нажмите чтобы проиграть демо

Функцию которая создает массив потомков данной доски и вырезает из него несостоятельные варианты назовем nextBoards. И наконец реализуем все это в виде кода:

function solve(b){
   // Ищет решение для данной доски
   // @param {Board} b
   // @return {Board | false}
  function solveBrd(b){
    if(isSolved(b)){
      return b;
    }else{
      return solveChilds(nextBoards(b));
    }
  }

  // Ищет решения для списка потомков
  // @param {arrayof: Board} lob
  function solveChilds(lob){

  }

  return solveBrd(b);
}

И заглушки для нереализованных функций isSolved и nextBoard:

/** Является ли данная доска решением?
  * @param  {Board} b
  * @return {Boolean}
  */
// !!!
function isSolved(b){ return false; } // Заглушка

/** Создает массив потомков данной доски
  * Все несостоятельные доски вырезаются
  * @param  {Board} b
  * @return {array of Board}
  */
// !!!
function nextBoards(b){ return []; } // Заглушка

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

Для того чтобы закончить функцию solve нам осталось поработать над функцией solveChilds. Это классическая рекурсивная функция, которая принимает массив и обрабатывает каждый элемент. Напомню, для того чтобы написать хорошую рекурсивную функцию нам надо поработать над тремя составляющими: базовым случаем, рекурсивным случаем, доказательством того что рекурсивный случай приведет к базовому.

Функция solveChilds очень похожа на функцию map, которую мы реализовали в статье о рекурсии. Она так же принимает массив и обрабатывает каждый элемент. Поэтому базовым случаем, как и в функции map, у нас будет пустой массив. А теперь подумаем что мы вернем в базовом случае. Поскольку функция solveChilds возвращается из solveBrd, которая в свою очередь возвращается из solve, получается что наша функция должна возвращать доску или false. Если мы достигли случая когда в solveChilds передается пустой массив значит у доски нету потомков в которых можно искать решения. Следовательно мы возвращаем false в базовом случае.

В рекурсивном случае нам необходимо узнать имеет ли первая доска в данном массиве потомков решение. Для этого мы передадим первую доску в функцию solveBrd, а не в isSolved. Потому что функция solveBrd будет искать решение не только в переданной доске, но и в ее потомках. Вызывая из функции solveChilds функцию solveBrd мы создаем цикл взаимной рекурсии. Если в первой доске нету решения тогда нам необходимо обработать следующую доску в данном массиве. Для этого уберем первую доску из массива потомков и с полученным массивом рекурсивно вызовем функцию solveChilds.

Вот и все, с функцией solve мы закончили. Эту функцию сложно объяснить на словах, поэтому давайте выразим ее в коде:

/** Решает проблему n-ферзей
  * @param  {Board} b Доска
  * @return {Board | false} Если задача имеет решение - доску
  *                         Иначе false
  */
// function solve(b){return false}; // заглушка
function solve(b){
   // Ищет решение для данной доски
   // @param {Board} b
   // @return {Board | false}
  function solveBrd(b){
    if(isSolved(b)){
      return b;
    }else{
      return solveChilds(nextBoards(b));
    }
  }

  // Ищет решения для списка потомков
  // @param {array of Board} lob
  // @return {Board | false}
  function solveChilds(lob){
    if(lob.length==0){
      return false; // базовый случай
    }else{
      // рекурсивный случай
      var first = lob[0];
      var rest  = lob.slice(1,lob.length);
      var tryBrd = solveBrd(first);
      if(tryBrd!=false){
        return tryBrd;
      }else{
        return solveChilds(rest);
      }
    }
  }

  return solveBrd(b);
}

У нас еще остались две нереализованные функции: isSolved и nextBoards. Давайте начнем с nextBoards. Она принимает доску и возвращает массив потомков этой доски. Этот массив формируется путем установки одной фигурки во все свободные клетки доски. Еще он должен содержать доски в которых ни один ферзь не атакует другого.

Получается что эта функция должна выполнять сразу два действия: заполнять пустые клетки на доске и фильтровать получившийся список. Давайте разделим эту функцию на две функции. Первая будет заполнять клетки на доске и возвращать массив получившихся досок. Назовем ее fillBlanks. Вторая будет фильтровать получившийся список, оставляя только валидные доски. Ее назовем keepOnlyValid. Поскольку наша функция nextBoards является просто комбинацией двух функций напишем к ней простой тест, который проверяет что комбинация этих функций возвращает тоже, что и nextBoards. Реализуем функцию nextBoards и заглушки для fillBlanks и keepOnlyValid:

/** Создает массив потомков данной доски
  * Все не валидные доски вырезаются
  * @param  {Board} b
  * @return {array.}
  */
  // function nextBoards(b){ return []; } // Заглушка
  function nextBoards(b){
  return keepOnlyValid(fillBlanks(b));
  }

  // Тесты для nextBoards
  (function(){
  console.log("Тест5:", (function(){
  var nb = nextBoards(createEmptyBoard(1));
  var fn = keepOnlyValid(fillBlanks(createEmptyBoard(1)));

  return nb.toString()==fn.toString();
  })());
  })();


  /** Создает массив досок в которых в каждой пустой клетке
  исходной доски стоит фигурка
  * @param  {Board} b Исходная доска
  * @return {array of Board}
  */
  // !!!
  function fillBlanks(b){ return []; } // заглушка

  /** Фильтрует массив досок оставляя только те доски
  в которых ни одна фигурка не атакует другую
  * @param  {array of Board} lob
  * @return {array of Board}
  */
  // !!!
  function keepOnlyValid(lob){ return []; } // заглушка

Напишем функцию fillBlanks. Она довольно сложная, поэтому лучше начать с тестов. Самый простой случай это пустая доска с размерностью n=1. В этом случае наша функция должна вернуть массив который содержит одну доску, в единственной клетке которой должен стоять ферзь. Если мы передадим этой функции доску с размерностью n=1 в клетке которой стоит ферзь, тогда наша функция должна вернуть пустой массив. Если мы передадим функции пустую доску с размерностью n=2 тогда она должна вернуть нам четыре доски: в первой доске ферзь стоит в клетке 1:1, во второй в 1:2, в третьей в 2:1, в четвертой в 2:2. Я думаю нам хватит столько тестов, реализуем их:

// Тесты для fillBlanks
(function(){
  console.log(
    "Тест6:",
    (function(){
      var x = fillBlanks(createEmptyBoard(1));
      return x.length==1 && x[0][0]==Q;
    })());
  console.log("Тест7:", fillBlanks([Q]).length==0);
  console.log(
    "Тест8:",
    (function(){
      var x = fillBlanks(createEmptyBoard(2));
      return x.length==4 &&
        x[0].toString()==[Q,B,B,B].toString() &&
        x[1].toString()==[B,Q,B,B].toString() &&
        x[2].toString()==[B,B,Q,B].toString() &&
        x[3].toString()==[B,B,B,Q].toString()
    })());
})();

Тесты стали немножечко сложнее, но не пугайтесь — функция будет простой. Нам надо пройтись по всем клеткам данной доски, если клетка не содержит фигурку тогда надо ее поставить туда, а данную доску сохранить в результирующем массиве. Если клетка занята тогда мы просто ее игнорируем.

Для удобства так же давайте реализуем функцию которая принимает доску, координаты клетки (ряд и колонку) и значение клетки. В результате функция возвращает доску с установленным значением на клетке с данными координатами. Назовем ее fillSquare.

Реализуем функцию fillBlanks:

/** Создает массив досок в которых в каждой пустой клетке
    исходной доски стоит фигурка
  * @param  {Board} b Исходная доска
  * @return {array of Board}
  */
// function fillBlanks(b){ return []; } // заглушка
function fillBlanks(b){
  // @param {Board}   brd Итерируемая доска
  // @param {Natural} pos Позиция
  function iter(brd, pos){
    if(brd.length==0){
      return []; // базовый случай
    }else{
      var first = brd[0];
      var rest  = brd.slice(1,brd.length);
      if(first!=Q){
        return [fillSquare(b, pos, Q)].concat(iter(rest, pos+1));
      }else{
        return iter(rest, pos+1);
      }
    }
  }

  var clone = b.slice(0, b.length); // Клонируем доску
  return iter(clone, 0);
}

И функцию fillSquare:

/** Ставит на доску в данную позицию данное значение
  * @param {Board}   b Доска
  * @param {Natural} p Позиция
  * @param {Q | B}   v Ферзь или пустая?
  */
function fillSquare(b,p,v){
  var clone = b.slice(0, b.length);
  clone[p]=v;
  return clone;
}

// Тесты для функции fillSquare
(function(){
  console.log("Тест9:",
    fillSquare([B],0,Q).toString()==[Q].toString());
})();

Перейдем к функции keepOnlyValid. Она принимает массив досок и возвращает только те, на которых ни одна фигурка не атакует другую. Получается наша функция выполняет сразу два действия: фильтрует и проверяет на валидность.

Для первого действия в Яваскрипте уже есть встроенная функция filter. Она вызывается у массива и принимает в качестве параметра функцию. В эту функцию поочередно передается каждый элемент данного массива и если она возвращает true то этот элемент будет в результирующем массиве.

Теперь подумаем о второй части нашей функции — проверки валидности доски. Для того чтобы доска считалась валидной ни одна фигурка не должна атаковать другую. Нам надо пробежаться по всем фигуркам на доске и проверить не атакует ли она другую. Фигурка может атаковать по горизонтали, вертикали и диагонали. Довольно сложная логика и она нам пригодится еще в функции isSolved, поэтому для нее напишем отдельную функцию, назовем ее isValid.

Начнем с написания тестов:

(function(){
  console.log("Тест10:",
    keepOnlyValid([[B]]).toString()==[[B]].toString());

  console.log("Тест11:",
    keepOnlyValid([[Q]]).toString()==[[Q]].toString());

  console.log("Тест12:", function(){
    var lob = [
      [Q,Q,B,B],
      [B,Q,Q,B],
      [B,Q,B,Q]
    ];
    return keepOnlyValid(lob).length==0;
  }());
})();

В первых двух тестах передаем валидные доски и проверяем что они вернулись в результате. В последнем передаем список не валидных досок и проверяем что вернулся пустой массив. Перейдем к реализации самой функции и заглушки для функции isValid:

/** Фильтрует массив досок оставляя только те доски
    в которых ни одна фигурка не атакует другую
  * @param  {array of Board} lob
  * @return {array of Board}
  */
//function keepOnlyValid(lob){ return []; } // заглушка
function keepOnlyValid(lob){
  return lob.filter(function(b){ return isValid(b); });
}


/** Проверяет валидна ли доска
  * @param {Board} b Доска
  * @return {Boolean} true - доска валидна, иначе false
  */
function isValid(b){ return false; }

Наша функция вызывает у переданного массива досок функцию filter и передает ей в качестве параметра функцию, которая возвращает значение isValid для каждой доски. Не забываем закомментировать заглушку для keepOnlyValid.

Последняя и самая сложная функция на нашем пути — isValid. Посмотрим на заглушку которую мы написали выше. Наша функция принимает доску и возвращает true если она валидна, в противном случае false. Для того чтобы узнать валидна ли наша доска мы должны пробежаться по каждой фигурке и посмотреть атакует ли она другую. Фигурка может атаковать по горизонтали, диагонали и вертикали. Начнем с написания тестов для всех этих случаев:

// Тесты для функции isValid
(function(){
  // Не валидна если фигурки на одной горизонтали
  console.log("Тест13:", isValid([Q,Q,
                                  B,B])==false);
  // Не валидна если фигурки на одной вертикали
  console.log("Тест14:", isValid([Q,B,
                                  Q,B])==false);
  // Не валидна если фигурки на одной диагонали
  console.log("Тест15:", isValid([Q,B,
                                  B,Q])==false);
  console.log("Тест16:", isValid([B,Q,
                                  Q,B])==false);
  // Валидные доски
  console.log("Тест17:", isValid([Q])==true);
  console.log("Тест18:", isValid(n4emptBrd)==true);
  console.log("Тест19:", isValid(n4solBrd)==true);
})();

Для того чтобы определить атакует ли фигурка другую фигурку нам понадобятся три функции которые выясняли бы что фигурка не атакует по горизонтали, вертикали и диагоали. Назовем их notAttackByHorizontal, notAttackByVertical, notAttackByDiagonal.

Для каждой из этих функций нам важно две вещи: позиция первой фигурки и позиция второй фигурки. Если ряд нашей фигурки совпадает с рядом другой фигурки значит она ее атакует по горизонтали. Если столбец нашей фигурки совпадает со столбцом другой фигурки то она ее атакует по вертикали.

С диагональю немножечко посложнее. Посмотрим на пример:

3 3 6 6

(3−6)÷(3−6)=−1; |−1|=1

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

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

Напишем заглушки для этих функций и вложим их внутрь isValid используя замыкание:

function isValid(b){
  // Не атакует по горизонтали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  // !!!
  function notAttackByHorizontal(pos1, pos2){} // заглушка

  // Не атакует по вертикали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  // !!!
  function notAttackByVertical(pos1, pos2){} // заглушка

  // Не атакует ли первая фигурка вторую по диагонали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  // !!!
  function notAttackByDiagonal(pos1, pos2){} // заглушка

  // Не атакует ли эта фигурка другую фигурку?
  // @param  {Integer} thisPos   Позиция этой фигурки
  // @param  {Integer} othersPos Позиция остальных фигурок
  // @return {Boolean} true если атакует
  // !!!
  function notAttackOthers(thisPos, othersPos){} // заглушка
}

Поскольку мы имеем дело с плоским массивом нам понадобятся еще две вспомогательные функции которые определяют колонку и столбец по позиции в массиве и размерности доски. Назовем их posToRow и posToCol. Они будут принимать позицию фигурки в массиве и саму доску для определение ее размерности.

Для того чтобы определить ряд нам нужно разделить позицию на размерность доски и результат округлить в меньшую сторону. Для того чтобы определить колонку мы возьмем остаток от деления позиции на размерность доски. А для того чтобы определить размерность доски возьмем квадратный корень из количества клеток, которые она содержит. Реализуем эти вспомогательные функции:

/** Считает размерность доски исходя из количества элементов
  * @param  {Board}   Доска
  * @return {Natural} Размерность доски
  */
function getBoardSize(board){
  return Math.sqrt(board.length);
}

// Тесты для функции getBoardSize
(function(){
  console.log("Тест20:", getBoardSize(n4emptBrd)==4);
})();

/** Переводит позицию фигурки в строку
  * @param  {Integer} Позиция доски
  * @param  {Board}   Доска
  * @return {Integer} Строка на которой стоит фигурка. Zero-base
  */
function posToRow(pos, board){
  // Тут важно округлить в меньшую сторону
  return Math.floor(pos/getBoardSize(board));
}

// Тесты для функции posToRow
(function(){
  console.log("Тест21:", posToRow(1, n4emptBrd)==0);
})();

/** Переводит позицию фигурки в столбец
  * @param  {Integer} Позиция доски
  * @param  {Board}   Доска
  * @return {Integer} Колонка на которой стоит фигурка. Zero-base
  */
function posToCol(pos, board){
  return pos%getBoardSize(board);
}

// Тесты для функции posToCol
(function(){
  console.log("Тест22:", posToCol(5, n4emptBrd)==1);
})();

Вернемся к нашим функциям проверки атаки. Алгоритм для функции проверки атак мы описали выше. А в функции notAttackOthers мы, используя рекурсию, поочередно проверим атакует ли фигурка другие фигурки из переданного массива позиций используя функции проверки атак. Если фигурка атакует какую-либо другую тогда наша функция вернет false. Реализуем их:

function isValid(b){
  // Не атакует по горизонтали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByHorizontal(pos1, pos2){
    return !(posToRow(pos1, b)==posToRow(pos2, b));
  }

  // Не атакует по вертикали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByVertical(pos1, pos2){
    return !(posToCol(pos1, b)==posToCol(pos2, b));
  }

  // Не атакует ли первая фигурка вторую по диагонали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByDiagonal(pos1, pos2){
    var rowDiff = posToRow(pos1, b) - posToRow(pos2, b);
    var colDiff = posToCol(pos1, b) - posToCol(pos2, b);
    return !(Math.abs(rowDiff/colDiff)==1);
  }

  // Не атакует ли эта фигурка другую фигурку?
  // @param  {Integer} thisPos   Позиция этой фигурки
  // @param  {Integer} othersPos Позиция остальных фигурок
  // @return {Boolean} true если атакует
  function notAttackOthers(thisPos, othersPos){
    if(othersPos.length==0){
      return true;
    }else{
      var othersFirst = othersPos[0];
      var othersRest  = othersPos.slice(1, othersPos.length);
      return notAttackByHorizontal(thisPos, othersFirst) &&
        notAttackByVertical(thisPos, othersFirst) &&
        notAttackByDiagonal(thisPos, othersFirst) &&
        notAttackOthers(thisPos, othersRest);
    }
  }
}

Теперь нам надо каким-то образом получить массив позиций всех фигурок на доске и определить что ни одна фигурка на доске не атакует другую.

Начнем с получения массива. Для этого напишем небольшую рекурсивную функцию которая будет проходить по всей доске и сохранять в результирующем массиве позиции фигурок, которые она встретит. Эта функция будет похожа на функцию map, которую мы реализовывали в посте про рекурсию, так что базовый и рекурсивный случай у нее такой же. Назовем ее getFiguresPos. Приступим к реализации:

/** Возвращает массив со всеми позициями фигурок на доске
  * @param  {Integer} curPos Текущая позиция
  * @param  {Board}  board  Доска
  * @return {array of Integer}
  */
function getFiguresPos(curPos, board){
  if(board.length==0){
    return [];
  }else{
    var first = board[0];
    var rest  = board.slice(1, board.length);
    if(first==Q){
      return [curPos].concat(getFiguresPos(curPos+1, rest));
    }else{
      return getFiguresPos(curPos+1, rest);
    }
  }
}

Мы уже близко к развязке. Нам осталось придумать способ как убедится что ни одна фигурка не атакует другую. Давайте подумаем, поскольку все фигурки у нас одинаковые то если одна не атакует ни какую другую, то и никакая другая не может атаковать ее. То есть, если мы проверили одну фигурку с координатами всех других фигурок, то другие фигурки проверять с координатой этой фигурки смысла не имеет. Получается, что мы можем очень удобно организовать данную функцию, давайте назовем ее checkFigures, в рекурсивном стиле:

  1. Берем первую фигурку из маcсива позиций.
  2. Проверяем не атакует ли она позиции в оставшийся части массива используя функцию notAttackOthers.
  3. Рекурсивно вызываем эту же функцию, но с массивом уже без первого элемента.
  4. Возвращаем результаты рекурсивного вызова и вызова функции notAttackOthers объединенные логическим оператором И.

Базовый случай у нас это пустой массив, возвращаем true. В противном случае мы проверяем не атакует ли эта фигурка кого-то еще и рекурсивно вызываем эту же функцию для проверки оставшегося массива. Звучит запутанно, но на деле все просто:

  // Проверяет не атакуют ли фигурки друг друга
  // @param  {array of Integer} Массив позиций фигурок на доске
  // @return {Boolean} true если фигурки не атакуют друг-друга
  function checkFigures(positions){
    if(positions.length==0){
      return true; // базовый случай
    }else{
      var first = positions[0];
      var rest  = positions.slice(1, positions.length);
      return notAttackOthers(first, rest) && checkFigures(rest);
    }
  }

Финальный штрих в функции isValid: вызываем функцию checkFigures с массивом позиций который нам отдает функция getFiguresPos и возвращаем результат. Вот полный вид функции isValid:

/** Проверяет валидна ли доска
  * @param {Board} b Доска
  * @return {Boolean} true - доска валидна, иначе false
  */
//function isValid(b){ return false; }
function isValid(b){
  // Не атакует по горизонтали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByHorizontal(pos1, pos2){
    return !(posToRow(pos1, b)==posToRow(pos2, b));
  }

  // Не атакует по вертикали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByVertical(pos1, pos2){
    return !(posToCol(pos1, b)==posToCol(pos2, b));
  }

  // Не атакует ли первая фигурка вторую по диагонали?
  // @param {Integer} pos1 Позиция первой фигурки
  // @param {Integer} pos2 Позиция второй фигурки
  // @return {Boolean} true если не атакует
  function notAttackByDiagonal(pos1, pos2){
    var rowDiff = posToRow(pos1, b) - posToRow(pos2, b);
    var colDiff = posToCol(pos1, b) - posToCol(pos2, b);
    return !(Math.abs(rowDiff/colDiff)==1);
  }

  // Не атакует ли эта фигурка другую фигурку?
  // @param  {Integer} thisPos   Позиция этой фигурки
  // @param  {Integer} othersPos Позиция остальных фигурок
  // @return {Boolean} true если атакует
  function notAttackOthers(thisPos, othersPos){
    if(othersPos.length==0){
      return true;
    }else{
      var othersFirst = othersPos[0];
      var othersRest  = othersPos.slice(1, othersPos.length);
      return notAttackByHorizontal(thisPos, othersFirst) &&
        notAttackByVertical(thisPos, othersFirst) &&
        notAttackByDiagonal(thisPos, othersFirst) &&
        notAttackOthers(thisPos, othersRest);
    }
  }

  // Проверяет не атакуют ли фигурки друг друга
  // @param  {array of Integer} Массив позиций фигурок на доске
  // @return {Boolean} true если фигурки не атакуют друг-друга
  function checkFigures(positions){
    if(positions.length==0){
      return true; // базовый случай
    }else{
      var first = positions[0];
      var rest  = positions.slice(1, positions.length);
      return notAttackOthers(first, rest) && checkFigures(rest);
    }
  }

  return checkFigures(getFiguresPos(0, b));
}

Вот мы и подобрались к развязке этой истории. У нас осталось не доделана только функция isSolved. Возвращаемся к условию: решением является доска на которой находится количество фигурок равное ее размерности и ни одна фигурка не атакует другую. Для проверки атак у нас уже есть функция isValid, а для проверки количества фигурок на доске можем использовать длинну массива, который возвращает функция getFiguresPos. Наша функция тогда принимает вид:

/** Является ли данная доска решением?
  * @param  {Board} b
  * @return {Boolean}
  */
//function isSolved(b){ return false; } // Заглушка
function isSolved(b){
  return isValid(b) && getFiguresPos(0, b).length==getBoardSize(b);
}

(function(){
  console.log("Тест23:", isSolved(n4emptBrd)==false);
  console.log("Тест24:", isSolved(n4solBrd)==true);
})();

Вот и все, если вы подошли к написанию кода с должным вниманием и аккуратностью после запуска программы все тесты должны показывать true, что является признаком того что наша программа работает как и задумывалось. Полная версия исходного кода программы находится в репозитории на Гитхабе.

Запустим поиск для доски с размерностью 4:

  solve(createEmptyBoard(4));

У меня возвращается вот такой массив:

  [false,true,false,false,
   false,false,false,true,
   true,false,false,false,
   false,false,true,false]

Да, это решение. Попробуем поискать решение для доски с размерностью 2, функция должна вернуть false так как для этой доски нет решения:

  solve(createEmptyBoard(2));
  // > false

Ага, программа работает как надо. А теперь давайте посмотрим на что способны наши железки и алгоритм. Соорудим небольшой тест производительности:

// Тест производительности,
// @param {Natural} startSizeOfBoard Начальный размер доски
// @param {Natural} endSizeOfBoard   Конечный размер доски
// @return {true} Тест закончился
function benchmark(startSizeOfBoard, maxSizeOfBoard){
  if(startSizeOfBoard>maxSizeOfBoard){
    return true;
  }else{
    console.log("Считаем для доски с размерностью:",
      startSizeOfBoard);

    var startTime = Date.now();
    var solution  = solve(createEmptyBoard(startSizeOfBoard));
    var endTime   = Date.now();

    console.log("Решение:", solution.toString());

    console.log("Затраченное время:",
      endTime - startTime, "миллисекунд");

    return benchmark(startSizeOfBoard+1, maxSizeOfBoard);
  }
}

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

Вот мои результаты для досок от 1 до 9 на компьютере МакБук Эйр (1.8 гигагерц «Intel core i5», 4 гигабайта ОЗУ):

benchmark(1,9);

Создавая такие тесты и строя графики на основе их данных мы можем узнать много интересного о задаче и алгоритме. Например, почему для поиска решения для доски с размерностью n=6 тратится 442 миллисекунды, а для доски с размерностью n=7 всего 5? Посмотрим на найденные решения:

Ага, решение доски с размерностью n=7 лежит прямо в первой ветке дерева, потому что ферзь стоит прямо в самой первой клетке. А вот с доской с размерность n=6 нам не повезло и алгоритму пришлось раскрывать больше ветвей дерева. Получается что с ростом размерности доски скорость поиска в нашем алгоритме не будет расти линейно, а что было бы если бы стояла задача найти все возможные решения? Подумайте над этим.

Так же в этих решениях содержится еще одна интересная закономерность: решение доски на 6 клеток как бы вложено в решение доски на 7 клеток. Иначе говоря если мы уберем первую строку и первый столбец из решения доски на 7 элементов мы получим решение для доски на 6 элементов. Забавно, я это заметил уже только когда делал визуализацию.

Заключение

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

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

А о методах ускорения поиска по деревьям поговорим в следующих статьях.

13.01.2014
архивирован

Большие идеи в великие компании

Приглашаю вас окунуться в мир капитализма и стартапов вместе со мной, опытным индивидуальным предпринимателем, и курсом «Разработка инновационных идей для новых компаний: первый шаг в предпринимательство» от Мэрилендского университета. Это, конечно, не так интересно, как наше любимое программирование или наука, но все же в обществе, где предприниматели — это новые рок-звезды ☺, эти знания могут быть полезными.

Перевод описания со страницы курса:

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

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

09.12.2013
архивирован

107 лет со дня рождения Грейс Хоппер

9 декабря 1906 года родилась одна из пионеров компьютерной науки, контр-адмирал флота США Грейс Хоппер. Грейс писала программы для одной из первых крупных американских вычислительных машин Марк 1, развила идею машинно-независимых языков программирования в своем языке «Флоу-Матик», который потом стал основой для языка Кобол, и популяризировала то слово, которое снится в самых ужасных кошмарах большинству программистов — дебагинг. Причем один из первых багов имел не логический, а вполне себе физический смысл:

Биографию лучше расскажет Википедия, а я хочу отметить что Грейс обладает отличным чувством юмора, смотрите сами:

лайк
05.12.2013

Социальная экспансия

Сегодня я начинаю свой план социальной экспансии с открытия группы в Вконтакте, страницы в Фейсбуке, канала в Серфингберде, Твиттера, и аккаунта с крутыми технократическими Кобами.

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

Еще одно незаметное изменение — у блога сменился домен с ch-ms.ru на forallx.ru.

Ну и главная мантра интернета: лайк, шейк, репост.

лайк
02.12.2013
архивирован

Учимся разрабатывать приложения для Андроида

К сожалению пока только телефонного. Но все же хочу сообщить вам, что сегодня начинается интересный курс «Креативность, серьезность и увлекательная научность приложений для Андроида» от Иллинойсского университета. Курс подходит даже для людей которые не знакомы с компьютерной наукой и программированием. Для дополнительной мотивации можете ознакомится с тем сколько получают андроид и ява разработчики.

Перевод описания со страницы курса:

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

Вы будете использовать инструменты которые используют разработчики под систему Андроид и создадите полноценные и полезные приложения. Мы так же представим фундаментальные принципы компьютерной науки и идеи программирования которые питают современные смартфоны и планшетные компьютеры.

25.10.2013

Гостиница Гильберта. Ответ

Эту задачу предложил немецкий математик Давид Гильберт где то в третьем десятилетии 20 века. Давид был одним из величайших умов своего времени. Среди большого числа его учеников, которые в последствии стали видными учеными, был Джон Фон Нейман. Он так же консультировал Эйнштейна при разработке тензорного анализа — фундамента теории относительности.

Один гость

Напомню вам условие задачи для одного гостя из предыдущей статьи:

Представьте себе гостиницу с бесконечным числом комнат. Комнаты пронумерованы натуральными числами, от 1 до ∞. В один прекрасный день в нашу гостиницу вошел человек и попросил снять комнату. К сожалению, для нашего гостя не нашлось комнаты, так как именно в этот день отель был полностью заполнен бесконечным числом гостей. Выгнать гостя? Или все же есть возможность предоставить ему свободную комнату не выселяя никого из постояльцев?

Несмотря на то, что задача явно говорит что все номера заняты, мы все же можем выделить сколько угодно свободных комнат. Давайте просто переселим человека из первой комнату во вторую, человека из второй комнаты в третью и так далее. То есть, каждого гостя из комнаты с номером n переселим в комнату с номером n+1, n→n+1. В результате этого у нас освобождается комната с номером один, и мы с радостью можем поселить нашего нового гостя.

Бесконечное число гостей

Напомню условие:

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

Задача стала интереснее. Может ли бесконечность вместить еще одну бесконечность? Для решения предыдущей задачи мы переселили каждого гостя на один номер вперед. Этот подход можно применить для любого конечного числа постояльцев. Если n номер комнаты постояльца, а m число прибывших гостей, тогда каждого постояльца надо переселить в номер n+m, чтобы освободить m номеров для m гостей. Но что если число гостей бесконечно, то есть m=∞?. Чему равно n+∞? Давайте попросим «Вольфрам Альфа» дать нам ответ: n+∞=∞. То есть, надо переселить каждого постояльца на номеров. Нет, это нам не подходит. Но задача имеет решение, давайте взглянем на определение четного числа:

Четное число — целое число, которое делится без остатка на 2.

Что если мы возьмем номер постояльца и умножим его на два? В результате мы получим четное число, так как оно будет делится на два. Следовательно если мы переселим каждого гостя из номера n в номер 2×n, n→2×n, мы получим бесконечное число нечетных свободных комнат, и мы сможем поселить бесконечное число гостей. Только не спрашивайте сколько времени займет переселения гостя из комнаты номер 8140406085191601 в комнату номер 16280812170383202.

***

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

22.10.2013

Гостиница Гильберта

Представьте себе гостиницу с бесконечным числом комнат. Комнаты пронумерованы натуральными числами, от 1 до ∞. В один прекрасный день в нашу гостиницу вошел человек и попросил снять комнату. К сожалению, для нашего гостя не нашлось комнаты, так как именно в этот день отель был полностью заполнен бесконечным числом гостей. Выгнать гостя? Или все же есть возможность предоставить ему свободную комнату не выселяя никого из постояльцев?

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

Ответ.

09.10.2013

Учимся правильно

Итак, вам понравился мой пост о Курсере и вы решили попробовать. Замечательно, но я хочу еще больше улучшить вашу жизнь и написал несколько советов о том, как избежать проблемы с которыми я столкнулся занимаясь на первых курсах. На данный момент я закончил 5 курсов, и еще 3 в процессе. Так что я уже опытный в этом деле и ко мне можно прислушаться. Я хочу поставить этой статье амбициозную цель — помочь вам научится учится. И если ваша цель получить знания и навыки, а не пройти больше курсов, тогда эти советы помогут вам более эффективно тратить свое время и сделать так чтобы оно приносило максимальную пользу.

Массовые онлайн образовательные курсы (МООК) имеют очень много общего с обычными курсами, к которым мы привыкли со школы или университета, поэтому опыт образования в этих учебных заведениях хорошо ложится на реалии МООК. Но есть так же и существенное отличие — МООК предоставляет значительную свободу в организации времени занятий и процесса обучения. Писать или не писать лекции, выполнять или не выполнять дополнительные практические упражнения, заниматься утром или вечером, вся тягота решения этих вопросов ложится на ваши плечи, а не на плечи учебного заведения и учителя. Эта свобода требует от вас большой дисциплины и ответственности, и она может вас привести к тому, что вроде курс закончен, а знания растерялись по дороге.

Выбор курса

Курсера похожа на огромный магазин с очень качественными товарами по очень низким ценам. Какой курс выбрать: «Введение в систематический дизайн программ», или «Универсальная игровая программа», или «Введение в математическое мышление», или «Введение в историю человечества»? Очень часто потребитель внутри нас заменяет эти ИЛИ на И, и тут вы попадаете в ловушку. Курсы вроде бы бесплатные, но на самом деле вы платите одним из самых ценных ресурсов — временем. Не сомневайтесь, образование одна из самых лучших инвестиций в жизни, но если вы нагрузите вашу тележку огромным количеством курсов то у вас не хватит времени на все и, скорее всего, вы потратите кучу нервов в этой борьбе и ничего не приобретете.

Почему так? Потому что курсы на Курсере соответствуют во многом их университетским аналогам. Они не так просты, как может показаться, и требуют должного внимания к себе. Но не все курсы одинаково сложны. Давайте попробуем их разделить на три категории:

  • Cложные. Это курс в предметной области которого вы не разбираетесь. К примеру если вы не разбираетесь в математике и берете курс «Исчисления» тогда приготовьтесь потратить на него очень много времени.
  • Средние. Это курсы в предметной области которых вы разбираетесь. К примеру, я программист и мне довольно легко даются новые знания в этой области.
  • Простые. Не могу дать характеристику поэтому приведу пример. Курс «Введение в историю человечества» можно назвать таким. Он не предполагает выполнения каких-либо домашних заданий, тема проста и понятна каждому человеку. В процессе обучения просто слушаешь интересные рассказы. Такой курс очень приятно и легко слушать, в нем не будет неожиданных сложностей, в общем это как хорошее кино посмотреть.

А теперь давайте попробуем посчитать. В аннотации к каждому курсу обычно пишется сколько времени в неделю студент должен будет уделять этому курсу по мнению автора. Так же учитывайте то, что это время для носителя английского языка. Так что к нему еще прибавляется время которое вам понадобится на перевод и понимание сказанного. Для простых курсов это время обычно указано 2-4 часа в неделю и совпадает с тем, что в реальности отводится на них. Для средних курсов это время 6-10 часов в неделю, при этом пару часов можно добавить на непредвиденные сложности. Для сложных курсов это время такое же, 6-10 часов в неделю, но при этом к нему надо прибавить как минимум 50% этого времени, так как сложности у вас точно возникнут, особенно если курс не вводный.

Если вы работаете полный рабочий день то сможете безболезненно уделять около 2 часов в будни и около 6 часов по выходным. Получается что можно взять сложный и средний курс, или два средних и простой. Используя эту классификацию можете произвести расчет под ваши условия. Конечно, это все примерно, в моей практике было так что сложный курс в аннотации которого написано 6-10 часов занимал 22 часа в некоторые недели, так что учитывайте и такие непредсказуемые обстоятельства и оставляйте всегда свободное время.

Какие курсы выбирать — вопрос личный. Но если вы собираетесь проходить несколько курсов одновременно, и все они на одну тему, советую включить в эту сессию какой-нибудь понравившийся курс на совершенно другую тему, чтобы разрядить монотонность сессии. То есть, если вы параллельно взяли четыре курса по программированию то вы можете устать от этой темы, и эффективность обучения будет постепенно падать. А если неделю разбавлять другой темой, тогда эта монотонность пропадет, и вы получите дополнительные знания. Это все конечно зависит от человека, но на своем примере могу сказать что это работает.

Старайтесь задания и лекции по более сложным курсам делать в начале недели, а более простые курсы оставлять на конец недели. Это даст вам дополнительный запас времени на непредвиденные сложности.

Мотивация

Cамое главное при выборе курса и начале обучения — мотивировать себя закончить его. В начале курса вы рветесь в бой, готовы свернуть горы, смотрите лекции и выполняете задания за одну бессонную ночь. Но в середине курса, а курс может идти 3 месяца, все это пропадает. Хочется покорять новые вершины, а покорение текущих целей оставить позади. И это очень плохо. Поэтому мотивируйте себя для того чтобы дойти до конца. Курсера предлагает нам сертификат по окончанию курса, поставьте себе цель во чтобы это не стало заполучить его. Придумайте для себя ему ценность, распечатайте уже полученные сертификаты и повесьте на стену, гордитесь ими и старайтесь собрать как можно больше, как фантики от жвачки в детстве (если кто этим занимался).

Если этого мало — мотивируйте себя с помощью денег. У Курсеры есть механизм сертификатов которые подтверждают то, что именно вы прошли этот курс. Этот сертификат существует в материальном виде и придет вам по почте. За эту услугу берется плата, приблизительно 50$, но это может дать вам хорошую мотивацию довести дело до конца.

Еще попробуйте вступить в группу учеников. Лучше в физическую, а не в онлайн группу. Смотрите лекции с друзьями. Окутайте этот процесс социальными связями. Одному гораздо проще забросить любое дело чем группе.

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

Обучение

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

А теперь перейдем к лекциям. Одна из главных проблем с которой я столкнулся при прохождении своего первого курса заключалась в том что я смотрел лекции один раз и потом, когда приступал к практическим заданиям, постоянно оказывался в такой ситуации что я не понимал какой либо детали. Сначала я долго сокрушался на сложность курса, на плохо составленные материалы, на шум за окном, на неверное расположение звезд и так далее. В конечном счете я возвращался к лекциям, пересматривал их, находил ответ на вопрос, решал эту проблему и вскоре находилось еще одно непонимание и процесс начинался сначала. Конечно уровень английского был ниже, я относился к занятиям проще чем надо было бы, но это все пустяки. Решением вопроса стала изобретенная мной двух-проходная система просмотра лекций. В первый раз я смотрю лекцию на нормальной скорости, стараясь уловить общую картину и представить как одна часть относится к другой. Я просто слушаю что мне стараются объяснить и не отвлекаюсь на детали. Во второй раз я смотрю лекцию ускоренной от полутора до двух раз, со включенными субтитрами, и составляю конспект лекции. Да-да, делаю именно то что бесило в школе и колледже. Если в процессе просмотра я встречаю незнакомое слово, то я останавливаю лекцию и перевожу его в переводчике. Со временем количество незнакомых слов не будет так раздражать, еще и язык подучите. Используя двух-проходную систему просмотр одной десятиминутной лекции занимает от 15 до 17 минут, так что учитывайте эти затраты при подсчете трат времени на курс.

А теперь про конспектирование. Его проблема в том что никто никогда не объяснял зачем оно нужно, а еще некоторые преподователи выдвигали совершенно непонятные требования в виде полного конспекта лекций в качестве пропуска к экзамену. Тут всплывает еще одна проблема классических лекций — необходимость слушать и писать одновременно, в итоге это все превращалось в кашу и теряло смысл. МООК не имеет данной проблемы потому что можно возвращаться к материалу сколько угодно. Ускорение просмотра видео убирает проблему того, что много раз одно и тоже скучно смотреть. Вообще ускорение это замечательный инструмент, в большинстве случаев при втором просмотре можно смотреть на скорости 2x и все понимать. Это зависит от лектора, но большинство лекторов специально говорят медленней чтобы люди, у которых проблема с английским, имели шанс понять о чем речь.

Конспект лучше составлять в цифровом виде, потому что по нему можно осуществлять поиск. Еще круче делать его в виде ментальных карт. Они представляют собой диаграмму связей начальным узлом которой является тема, а отростки от него являются какими-то понятиями которые относятся к этой теме. Такие карты позволяют нам делать меньше записей и лучше структурировать их. Еще в них можно использовать ссылки, изображения, прикреплять файлы. На многих курсах видео сопровождение к лекции в формате слайдов, и если мысль которую вы хотите законспектировать находится на экране то лучше сделать скриншот и прикрепить его к узлу диаграмы. Для дополнительного усвоения материала я перевожу данный слайд своими словами. Я использую программу «ИксМайнд», она бесплатная и полностью меня устраивает.

Конспект в виде ментальной карты

Так в чем же смысл конспекта? У него есть две цели. Первая и самый важная — конспектирование как процесс позволяет повысить запоминаемость материала во много раз, при условии что оно выполняется в спокойных условиях и конспектируется материал который уже был воспринят устно, то есть знакомый. Этот результат не научный, это мой опыт. Именно этот смысл теряется в традиционных лекциях-диктовках, когда пишешь и слушаешь то ни одно из этих дел не получается на должном уровне. Второй смысл в том, что удобней найти ответ на вопрос в своих лекциях, особенно если им придана структура с помощью ментальных карт, чем найти и посмотреть нужную лекцию. Самое интересное в том, что при двух-проходной системе просмотра лекций у меня эта потребность возникала всего пару раз. То есть материал запоминается отлично.

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

В большинстве случаев лекции разбиты на короткие кусочки по 5-10 минут. Такие лекции проще усваивать чем более длинные лекции. Но, если вы встречаете лекцию длинной 30 минут то можете разбить ее на отрезки по 10 минут и применять двух-проходную систему на каждом отрезке. То есть 10 минут посмотрели, отмотали и посмотрели ускоренно. Я вначале прибегал к этому приему, но потом как то 30 минутные лекции научился за один присест смотреть.

Очень часто прямо посреди лекции появляется тест, если ответ на него не очевиден и вообще вопрос не понятен значит вы что то упускаете, и лучше отмотать обратно и пересмотреть фрагмент до теста. Вообще тесты довольно хороший индикатор понимания материала, проходите их, думайте над неверными ответами, и находите понимание того, почему верный ответ действительно верный. Если вы не получаете 100% балов за тест есть смысл попробовать его еще раз до тех пор пока вы не достигнете мастерства.

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

  1. Понимание
    1. Теория
    2. Практика
  2. Мастерство

Понимание это основная часть обучения. Мы изучаем теоретический материал и применяем его на практике. Советы по этому шагу я озвучил выше. На шаге мастерства вы детализируете и структурируете свои знания путем объяснения их другому человеку. Этот шаг является ключем к полному пониманию вопроса. Вы можете заниматься каким-либо делом 5 лет и думать что вы эксперт в нем, но как только вы пытаетесь объяснить суть этого дела кому-то другому у вас получается такой рассказ, что вы ловите себя на мысли о том, что вы не понимаете то о чем говорите. Ваш собеседник будет задавать каверзные вопросы на которые у вас может не быть ответа. Старайтесь искать ответы, заполняя пробелы в своем знании, и этот процесс позволит вам отшлифовать ваши знания до совершенства. Форум и группы студентов это идеальное место для этого шага. Помогайте другим и ваше понимание будет намного глубже.

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

И напоследок поговорим о жуликах. О тех людях которые создают ощущение несправедливости в мире образования и которые разрушают его. За что я люблю МООК это то что в нем есть только одна награда — знания. То, ради чего и создавалось образование. Оно не обросло степенями и титулами которые в нашей стране, к сожалению, можно купить и наличие такого титула может приносить прибыль. Так что если вы что то не понимаете, а крайняя дата сдачи скоро, есть только один выход — понять.