?

Log in

No account? Create an account
программирование во вьетнаме - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

программирование во вьетнаме [мар. 21, 2013|09:57 am]
Anatoly Vorobey
Очень интересный рассказ Нила Фрейзера о том, как преподают компьютеры во вьетнамских школах. Не буду пытаться пересказывать - но советую прочитать. И игра его Blockly Maze для объяснения детям основных понятий программирования - тоже интересная штука.

Что касается задачи про лабиринт для старшеклассников, которую он описывает ближе к концу записи, меня это весьма впечатлило (и даже подзуживает скепсис несколько). Это действительно непростая задача, и автор не преувеличивает, когда пишет, что ее вполне можно задавать на интервью в Гугле. Любопытства ради я решил ее на Питоне, сидя за компьютером, и засек время: от начала работы до вывода всех требуемых результатов, включая отладку и все остальное, у меня заняло 35 минут.
СсылкаОтветить

Comments:
[User Picture]From: tat_ti
2013-03-21 08:29 am
Расширяем ли набор задач? Если да, то
1) хочу мазу и задачи в классы студентам
2) готова делать задачи (т.е. перевести часть задач классических задач cs на эту мазу забесплатно и придумать новые на разные разделы; я это могу и могу много)

Причина: даже если человек олимпиадник-международник по математике, то это еще не значит, что он прекрасно начинает писать программы на формальном языке (а если не олимпиадник-международник, а просто умный мальчик, то еще менее значит).
Я готова согласиться, что часть народа в студенческие годы, как и среднюю школу, нужно учить через "программирование в картинках". Особенно, если это первый язык программирования.
3-5% на математических специальностях обучаются либо туго, либо очень туго.
(Ответить) (Thread)
[User Picture]From: francis_drake
2013-03-21 09:54 am
Запись не грузится :(
(Ответить) (Thread)
From: ztarlitz
2013-03-21 10:11 am
Программирование, как написано в заголовке лучшего учебника по программированию это алгоритмы + структуры данных.
Где в этой игре данные? Возможно эта игра развивает алгоритмическое мышление, но это не программирование.
(Ответить) (Thread)
[User Picture]From: vika_1_2
2013-03-21 10:18 am
Данные используются в 10 уровне.
(Ответить) (Parent) (Thread) (Развернуть)
(Удалённый комментарий)
[User Picture]From: alpas
2013-03-21 11:41 am
да, очень интересно.
в конце автор рассуждает о том, что в США проблема с компетентными учителями CS, при этом умалчивает о том, откуда они взялись во Вьетнаме. что удивительно, учитывая его же слова о том, что в тамошних университетах не так всё впечатляет, т.к. CS пришли в страну недавно.

ну и по поводу нёрдов, по-моему, у него устаревшая информация. с тех пор как супергерои и звёздные войны завоевали попкультуру (последние 7-10 лет), ботаны вышли из подполья. сам этот факт уже вполне обыгрывается в фильмах, см. к примеру 21 Jump Street (2012).
(Ответить) (Thread)
[User Picture]From: alenaroo
2013-03-21 01:27 pm
Очень интересно, спасибо. По забавному совпадению я сейчас во Вьетнаме отдыхаю, а один из моих коллег-разработчиков в сиднейской компании, где я работаю, - вьетнамец и один из лучших программистов в компании. Правда, акцент его ну очень сложно бывает понимать.
(Ответить) (Thread)
[User Picture]From: sorcerer_
2013-03-21 01:36 pm
Во Вьетнаме были одни из самых лучших аутсорс программистов, которых мы нанимали.
(Ответить) (Thread)
[User Picture]From: prosto_tak
2013-03-21 01:54 pm
Интересно, что эта его игра сделана на базе Scratch (http://scratch.mit.edu/). Мы с Юлей с ним как раз последние пару недель играем. С одной стороны, язык для детей, но с другой, вполне мощный и интересный. Можно делать мультики и игры. Это не то же самое, как в детстве Фортран учить...
(Ответить) (Thread)
From: huzhepidarasa
2013-03-21 07:31 pm
Задача непростая, да — не сразу понятно, что же обозначают единицы и нули в данных.
(Ответить) (Thread)
[User Picture]From: avva
2013-03-21 09:09 pm
Это сарказм, или не вполне понятный мне смысл?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: aivean
2013-03-21 08:23 pm

в чем сложность задачи?

Правильно ли я понимаю, что вся «сложность» заключается в поиске в ширину? Вначале он запускается при проходе по периметру, затем при проходе за N*M по всей площади лабиринта. Ассимптотическая сложность O(N*M).
(Ответить) (Thread)
[User Picture]From: avva
2013-03-21 09:33 pm

Re: в чем сложность задачи?

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

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


В Гугле на интервью задают в принципе три разных вида задач:
1. algo
2. coding
3. system design

Для алгоритмической задачи эта слишком проста. Для задачи на написание кода она в самый раз или даже сложнее средней.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: dvornikstepanof
2013-03-22 08:48 am
В школьном тесте я бы решал задачу в лоб, не заботясь об эффективности и общности:
1. Заменить в матрице все «висячие» единицы (т.е. граничащие с не более чем одной единицей) на 0. Итерировать, пока таковых не останется.
2. Удалить из матрицы (скажем, заменить на «-1») все пограничные нули. (Ноль – пограничный, если с одной из 4 сторон касается границы матрицы или ранее удаленного нуля). Итерировать, пока пограничных нулей не останется.
3. (общий шаг) Выбрать какой нибудь «0» и удалить из матрицы. Затем итеративно удалить все другие нули, граничащие с ранее удаленными. При удалении накапливать суммарную площадь по правилу: если не граничит с единицами, добавить 1; если граничит с одной единицей, добавить ½; если с двумя – добавить ¼. Когда не остается нулей для удаления, накопленная сумма есть (16-кратная) площадь соответствующей области.
Продолжаем процесс, считая области и сравнивая их площади, до тех пор пока остаются нули.

У меня чистое программирование с отладкой в С++ заняло около 40 мин, но перед этим я потратил некоторое время на обдумывние алгоритма и структуры программы. Это время я не засек; это могло быть от 5 до 20 мин.

Но на интервью я бы, наверное, решал иначе, сведя к более общей задаче. Какие-то усилия заняло бы написание процедуры перевода матрицы в плоский граф (вершины с координатами и ребра), но зато потом решать легче и приятнее. Достаточно трех-четырех операторов, чтобы удалить все висячие ребра; при обходе контура элементарно считается площадь многоугольника через координаты вершин, и т.п.
(Ответить) (Thread)
[User Picture]From: meshko
2013-03-22 07:47 pm
А нельзя просто сжульничать с казать,, что площадть -- это floor(s/12), где s -- это площадь в единицах измерения файла?
(Ответить) (Parent) (Thread) (Развернуть)
From: lanceupper
2013-03-25 05:47 pm
Когда речь идет об обучении детей программированию, понятно, что могут представлять ценность разнообразные надумано-искуственные задачи с заранее заказанными надуманно-искуственными способами решения. Но за пределами этой области надуманость и искуственность никакого смысла не имеют.

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

Готовый программист же, будучи ознакомлен с исходной абстрактной постановкой задачи, должен сделать большие глаза, увидев, что входные данные вдруг с какого-то бодуна представлены растром. Для любого job interview (если интервьюирующий не идиот) в такой ситуации правильным ответом является: ткнуть пальцем во входные данные и сказать "вы что, с дуба ляснулись?!". Садиться же тихо строчить растровое решение "за 40 минут" в такой ситуации является ярко выраженным признаком непрофессионализма.

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

Edited at 2013-03-25 17:48 (UTC)
(Ответить) (Thread)
[User Picture]From: dvornikstepanof
2013-03-25 11:22 pm
Поскольку я один в этой дискуссии упомянул 40 минут ( Avva решил за 35), то Ваши слова -
Садиться же тихо строчить растровое решение "за 40 минут" в такой ситуации является ярко выраженным признаком непрофессионализма -
очевидно, относятся ко мне.

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

Но говорить на интервью "вы что, с дуба ляснулись?!" я бы все-таки воздержался.


Edited at 2013-03-25 23:25 (UTC)
(Ответить) (Parent) (Thread)