Comments 36
Сколько людей, столько мнений. Мне показался лектор довольно занудным, а курс очень теоретизированным.
Может, это и хорошо для студентов на дневном, но для прикладных целей (aka job interview) очень уж затянуто.
Может, это и хорошо для студентов на дневном, но для прикладных целей (aka job interview) очень уж затянуто.
Скажите, а вы 2-SAT решали рандомом, потому что было такое задание? Или просто не был рассказан детерминированный линейный алгоритм?
Задание было решить рандомом. Мне на самом деле очень понравилось, особенно доказательство, почему именно рандомом работает. В чем состоит линейный алгоритм в двух словах?
Приводим все функции вида X OR Y к импликациям вида X'->Y', строим на них граф, дальше — по компонентам сильной связности пробуем поставить любой из переменных true или false и проверяем, сошелся ли ответ в данной компоненте при каком-либо значении. Если сошелся — то фиксируем и переходим к следующей компоненте, если нет, то решения системы нет.
Как альтернативу, глубоко рекомендую во многом похожий курс от Princeton:
Algorithms, Part I
Algorithms, Part II
Например, из интересных заданий:
— A* для поиска решений для пятнашек,
— контекстное изменение размеров изображения seamcarving,
— простенький архиватор
Algorithms, Part I
Algorithms, Part II
Например, из интересных заданий:
— A* для поиска решений для пятнашек,
— контекстное изменение размеров изображения seamcarving,
— простенький архиватор
плюсуюсь к Алгоритмам от Седжвика! помоему единственный курс на курсере, в котором Quiz генерятся рандомно и чтобы здать надо действительно понимать тему.
Quiz (тесты) в них шедевральны. Например, даны промежуточные(!) структуры данных, вопрос — каким алгоритмам они могу соответствовать, или могли ли такие данные получиться на промежуточном этапе работы алгоритма (промежуточные массивы в алгоритмах сортировки, или какие-нибудь недосбалансированные деревья в алгоритмах балансировки деревьев).
Такие тесты — хороший аргумент для тех, кто считает что тестами нельзя проверить знания.
Такие тесты — хороший аргумент для тех, кто считает что тестами нельзя проверить знания.
О, да, я хотела его тоже! Тем более там написано, что эти два курса как бы дополняют друг друга, что тот более теоретический, а этот более практический, что ли. Но я на Java не программирую, а там написано, что надо уже уметь на каком-то нормальном уровне. Поэтому решила, что будет иметь мало смысла.
Напрасно! Когда я проходил курс Седжвика в первый раз, не работал с Java вообще… Но, во-первых, Java — очень понятный и читабельный язык; второе — все алгоритмы из книги Седжвика написаны на Java. Плюс у них там есть урезанная IDE для написания кода, которая не отталкивает большим числом различного функционала. Так что, если у вас есть желание, рекомендую попробовать, тем более, что кур начался не особо давно — еще можно успеть пройти.
Java там вообще не представляет проблемы. Седжвика стоит послушать или почитать хотя бы за его объяснение к Left-Leaning Red–Black Trees, которые он же и изобрел. Становится понятно, откуда они вообще взялись, и как можно прийти к этой идее. До этого я читал не менее пяти разных объяснений красно-черных деревьев, и ни одного толком не понял.
Еще он работал над анализом heap sort, shell sort, quicksort. Он настолько глубоко разбирается в теме, что даже знание этих алгоритмов не делает курс менее интересным. Он рассказывает об истории, особенностях и интересных деталях реализации алгоритмов, на которых другие авторы не заостряют внимание, либо вообще не знают об этих вещах.
Еще он работал над анализом heap sort, shell sort, quicksort. Он настолько глубоко разбирается в теме, что даже знание этих алгоритмов не делает курс менее интересным. Он рассказывает об истории, особенностях и интересных деталях реализации алгоритмов, на которых другие авторы не заостряют внимание, либо вообще не знают об этих вещах.
Исключительно мое мнение:
Мне его манера преподавания (бубнеть под нос) показалась невероятно… скучной? Это вам не лектор CS50 c edX.
Вместо просмотра лекций Седжвика предпочел прочитать его же книги — а затем браться за задания.
Мне его манера преподавания (бубнеть под нос) показалась невероятно… скучной? Это вам не лектор CS50 c edX.
Вместо просмотра лекций Седжвика предпочел прочитать его же книги — а затем браться за задания.
Я прошу прощения, что такое Дайкстра? Неужели это настолько корявый первод фамилии Эдсгера Дейкстры (Dijkstra)? Даже в этом случае совершенно не понятно, что гласит заголовок.
Американцы так произносят фамилию Dijkstra.
есть же в гугле транслейте play audio, послушайте. Там точно не «а»
Хм. В каком-то из курсов я такое произношение слышал.
На англовики в статье про него лежит вот это — Dijkstra.ogg — я слышу «а» вполне отчетливо.
А как правильно — не знаю, не рискну предположить.
На англовики в статье про него лежит вот это — Dijkstra.ogg — я слышу «а» вполне отчетливо.
А как правильно — не знаю, не рискну предположить.
Господи, ну почему нельзя просто следовать традиции. Постоянно кто-то порывается обучить темную Россию правильному произношению.
А японцы «English» произносят как «Энгриш», и что теперь? Может будем следовать правилам транслитерации или хотя-бы брать готовые переведенные имена, а не придумывать новые?
Он же из Нидерландов, там ij произносится как эй или ай. Поэтому так и написала. Мне кажется, Тим тоже это как -ай- произносит. Хотя американцы конечно поражают своей способностью все имена переиначивать на свой лад.
Я вообще очень рада, что поднялся этот вопрос. Интересно, что русские сейчас стали так щепетильны к произношению. Вот какого черта, например, раньше перевели Эйнштейн, а не Айнштайн, как сам человек это произносил и в его стране это произносят. Или Гамбург вместо Хамбурга.
Я вообще очень рада, что поднялся этот вопрос. Интересно, что русские сейчас стали так щепетильны к произношению. Вот какого черта, например, раньше перевели Эйнштейн, а не Айнштайн, как сам человек это произносил и в его стране это произносят. Или Гамбург вместо Хамбурга.
Таких вот неоднозначных (по сегодняшним меркам) переводов — целое множество. И это, на самом деле, не вопрос для обсуждения на досуге, а довольно нетривиальная лингвистическая задача: изучать приходится не только язык оригинала, но и тот язык, из которого это слово пришло в русский, рассматривать отдельные наречия etc.
Современный русский язык унаследовал много устоявшихся переводов (Вильгельм Завоеватель, а не Уильям, король Карл, а не Чарльз). Порой они меняются (Невтон -> Ньютон). Но, как правило, меняются только правила перевода, а слова закрепляются. Так что писать «Айнштайн» или «Дайкстра» — это не по-русски. Вне зависимости от того, как эти слова произносятся на языке оригинала, при переводе всегда нужно проверять, не существует ли уже устоявшийся вариант в языке перевода.
Современный русский язык унаследовал много устоявшихся переводов (Вильгельм Завоеватель, а не Уильям, король Карл, а не Чарльз). Порой они меняются (Невтон -> Ньютон). Но, как правило, меняются только правила перевода, а слова закрепляются. Так что писать «Айнштайн» или «Дайкстра» — это не по-русски. Вне зависимости от того, как эти слова произносятся на языке оригинала, при переводе всегда нужно проверять, не существует ли уже устоявшийся вариант в языке перевода.
Да, ты хорошо сказал, на самом деле. Я в целом согласна, что когда есть устойчивый перевод, то его лучше использовать. Например, «Айнштайн» я бы не стала писать, режет глаза, потому что привыкла к другому написанию. Но вот, например, «Гейдельберг» ужасно режет глаза. Я знаю этот город как «Хайдельберг» и произносить и писать с «Ге-» мне просто дико.
Про Dijkstra я не знала, что вообще есть некоторый устойчивый перевод. Он практически наш современник. Представь себе ты придумаешь какой-нибудь алгоритм, назовут твоим именем. Потом через пару десятков лет ты приезжаешь в какую-нибудь страну, а они твою фамилию вообще переиначили и неправильно произносят. Причем не потому, что в их языке нет каких-то там звуков, но просто потому что «в силу некоторых исторических причин».
Про Dijkstra я не знала, что вообще есть некоторый устойчивый перевод. Он практически наш современник. Представь себе ты придумаешь какой-нибудь алгоритм, назовут твоим именем. Потом через пару десятков лет ты приезжаешь в какую-нибудь страну, а они твою фамилию вообще переиначили и неправильно произносят. Причем не потому, что в их языке нет каких-то там звуков, но просто потому что «в силу некоторых исторических причин».
Я всегда думал, что язык должен эволюционировать. Интересно, почему он может эволюционировать в привычном всем смысле — впитывать англицизмы, создавать новый жаргон, менять значения слов — но не может менять неправильное написание на правильное только из-за того, что неправильное считается устоявшимся?
Что касается «нетривиальныйх» лингвистических задач, то возникает закономерный вопрос: а зачем тогда нужны лингвисты, если они не занимаются этими задачами? Это как если бы ведущий программист сказал поправить баг, а я бы сослался на сложность правки, время на изучение документации и на то, что пользователи уже знают о баге, так что баг автоматически превращается в изящную фичу.
Что касается «нетривиальныйх» лингвистических задач, то возникает закономерный вопрос: а зачем тогда нужны лингвисты, если они не занимаются этими задачами? Это как если бы ведущий программист сказал поправить баг, а я бы сослался на сложность правки, время на изучение документации и на то, что пользователи уже знают о баге, так что баг автоматически превращается в изящную фичу.
Интересно, почему он может эволюционировать в привычном всем смысле — впитывать англицизмы, создавать новый жаргон, менять значения слов — но не может менять неправильное написание на правильное только из-за того, что неправильное считается устоявшимся?
Отчего не может-то? Всё он может. Но, что называется, нельзя просто взять и поменять слово. Языковые нормы не могут фиксироваться законодательно; язык формируют говорящие на нём люди.
Не всегда просто рассудить, «правильное» написание или нет. Что вкладывается в понятие «правильности»? Я не берусь судить, какой из вариантов — «Дейкстра» или «Дайкстра» — является «правильным». Но я знаю, что в школе и в университете мне рассказывали именно про Дейкстру. Что в статьях и всяких умных книжках пишут об алгоритме Дейкстры. И так далее. Значит, кто-то когда-то решил, что такой перевод имени нидерландского учёного будет адекватен. С течением времени ни у кого возражений не возникало, и этот вариант укоренился.
Но и то — бывает не всё так гладко, и в литературе происходят регулярные разночтения в именах некоторых учёных.
Что касается «нетривиальныйх» лингвистических задач, то возникает закономерный вопрос: а зачем тогда нужны лингвисты, если они не занимаются этими задачами? Это как если бы ведущий программист сказал поправить баг, а я бы сослался на сложность правки, время на изучение документации и на то, что пользователи уже знают о баге, так что баг автоматически превращается в изящную фичу.
Не понимаю. Ни вопроса, ни аналогии.
Разумеется, занимаются. Чем они только не занимаются. Я просто заметил, что то был не праздный вопрос, а вполне себе исследовательская задача.
Про слова вроде Гамбурга я тоже могу напридумывать всякого. Например, у славян есть целый букет звуков, промежуточных между «х» и «г» (украинское «хэканье» — традиционный пример). Вот из-за схожести с немецкой «h» и взяли в свое время один из них, а тот со временем нивелировался до русской «г». А что, рабочая гипотеза, почему бы и нет. :-) Только у меня нет ни знаний, ни энтузиазма, чтобы с ней работать.
Дийкстра-Дайкстра ладно, но почему переменные булиневы? :)
Они называются булевы (от Джорджа Буля), а булинь — это узел такой.
Они называются булевы (от Джорджа Буля), а булинь — это узел такой.
Вот же блин. Я полгода ждал новой сессии этого курса, а ее все не было. Просто лекции слушать было интересно, но не слишком полезно. Вписался в принстонский курс (Algorithms Part I, преподаватель Р. Сэджвик — и вот на тебе :)
Мое глубокое имхо — как лектор Тим гораздо лучше Сэджвика (хотя слайды читаются чуть хуже, ибо Тим их пишет от руки) — возможно, в силу возраста.
Материал подается глубже (но не сильно, в математике не тонешь), от Сэджвика я даже про master theorem не услышал.
Тесты и задания мне понравились, не слишком сложные; автогрейдер считается одним из лучших, присутствуют пасхалки в тестовых наборах данных. Тесты и задания от Тима я еще не видел, т.к. в закрытом курсе у него были видны только видеолекции.
Придется мне совмещать, видимо :) К счастью, по времени пересечение недели две всего.
Мое глубокое имхо — как лектор Тим гораздо лучше Сэджвика (хотя слайды читаются чуть хуже, ибо Тим их пишет от руки) — возможно, в силу возраста.
Материал подается глубже (но не сильно, в математике не тонешь), от Сэджвика я даже про master theorem не услышал.
Тесты и задания мне понравились, не слишком сложные; автогрейдер считается одним из лучших, присутствуют пасхалки в тестовых наборах данных. Тесты и задания от Тима я еще не видел, т.к. в закрытом курсе у него были видны только видеолекции.
Придется мне совмещать, видимо :) К счастью, по времени пересечение недели две всего.
Сложность тестов у Тима средняя: примерно на половину вопросов можно ответить без ручки и бумажки, в среднем на тест уходит 45 минут, на финальный экзамен 2 часа 45 минут.
На выполнение практического задания уходит от часа до трех. Некоторые практические задания не решаются обычными методами. Для меня самым сложной оказалась задача коммивояжёра с пятой недели второй части курса, которая не решалась влоб методами из лекций. Для большинства задач, метод решения описанный в лекциях подойдет только для небольших исходных данных и нужно будет придумывать как его улучшить.
Брал этот курс в прошлом году, было немного обидно ответить неправильно на два вопроса в самом последнем экзамене второй части курса.
На выполнение практического задания уходит от часа до трех. Некоторые практические задания не решаются обычными методами. Для меня самым сложной оказалась задача коммивояжёра с пятой недели второй части курса, которая не решалась влоб методами из лекций. Для большинства задач, метод решения описанный в лекциях подойдет только для небольших исходных данных и нужно будет придумывать как его улучшить.
Брал этот курс в прошлом году, было немного обидно ответить неправильно на два вопроса в самом последнем экзамене второй части курса.
Master theorem и другие «теоретические» аспекты смотрити в курсах Р. Сэджвика Analysis of Algorithms и Analytic Combinatorics
А я прошел курс Седжвика (обе части). После этого сразу пошел на codility.com/train/ практиковаться. Нужно сказать, что тоже получил массу удовольствия :). Рекомендую.
Лучший курс про алгоритмы, который я слушал, был из MIT OpenCourseWare: www.youtube.com/playlist?list=PL8B24C31197EC371C
Курс действительно классный, одновременно подробный и интересный. Благодаря ему я смог устроиться на свою нынешнюю работу. Сейчас смотрю лекции второй части, чтобы в июле сдать экзамен.
В качестве примера вот картинка, как я находила решаемость 2SAT проблемы рандомным алгоритмом.Я не помню такого. Это из второй части?
Sign up to leave a comment.
Дайкстра от Тима из Стэнфорда