Скорее всего, в лицензионном соглашении указано, что всю ответственность несёт пользователь инструмента. В любом случае, суд не будет разбираться как украденный код появился в твоём продукте. Твой продукт - твоя ответственность. Ну а дальше можешь попробовать её частично возместить за счёт поставщика инструментария.
У каждой лицензии свои требования. Указание авторства лишь одно из них. Причём самое безобидное. Веселее, когда суд обяжет вас опубликовать код вашего коммерческого продукта под открытой лицензией или выплатить % выручки авторам библиотеки, которая была свободной только для некоммерческого использования. Но это раньше и больше в США и Европе. Как будет теперь и в России - большой вопрос.
О да, это чертовски увлекательное чтиво! Особенно эта прекрасная мозаика из формул, ммммм....одно удовольствие!
Доказательства корректности, анализ и доказательство сложности идут отдельными секциями после всех объяснений. Эти секции никак не мешают чтению остального материала. При необходимости, их можно просто пропускать. Идентифицировать их легко, они так и называются:
Да, автор не пишет O(nlogn), но для половины задач либо дано условие, либо дан анализ: "число операций пропорционально log n", "число шагов не должно превосходить ?1 log(a/b) + ?2 для некоторых констант ?1, ?2", "время работы остаётся порядка ?^2" и тому подобное. Возможно, это неканонично. Возможно, это понятнее, чем "сложность O(n^2)".
В некоторых местах рассматриваются и затраты памяти. В некоторых местах рассматривается худший случай и в среднем.
Но ведь автор не утверждает, что книжка по школьной программе.
Нет, он говорит о том, что книга написана по материалам занятий программированием со школьниками. Я позволил себе усомниться в том, что это простые школьники.
Речь может идти только об очень очень особой школе и очень очень особых школьниках. Например, таких, которые ходят на математический кружок мехмата МГУ, где математически доказывают выигрышную стратегию при игре в крестики-нолики. 90% материала выходят за рамки школьной программы по информатике. Да и некоторые задачи используют математический аппарат, который тоже в школьный стандарт не входит. Не стоит отметать эту книгу как что-то для маленьких и неразумных.
Так каков же вывод? Книга для школьников (пусть и олимпиадников) и взрослому человеку читать её стыдно или поздно?
Ну мне не стыдно. Я почерпнул для себя новое. Мне было интересно. Тем, кто уже давно не школьник, я, по прежнему, её рекомендую:
Если базиса нет, то тут он дан. Если базис уже знаком, то для разминки и расширения кругозора.
Если сравнивать с "Грокаем алгоритмы", то лучше уж прочитать "Программирование: теоремы и задачи". Да, наверное есть другие книги, где нет доказательства корректности и задач без решений и они будут более эффективны в плане затрат времени и полученного результата. Например,
классический учебник MIT "Алгоритмы" Кормена, Лейзерсона, Ривеста, Штайна
Для этого мы мнением и обмениваемся. Нет общепризнанного списка о том, что читать и в каком порядке. В соседней ветке с обзором "Грокаем алгоритмы" тоже рекомендовали каноничные тексты, но каждый рекомендовал свой набор. Я уже пополнил список того, что мне стоит прочесть. Если кто-то заинтересуется книгой А. Шеня или наоборот из моего описания или ваших комментариев поймет, что она ему не подходит и не потратит время зря - тоже хорошо.
Речь идёт о том, что дети ... должны иметь возможность влезть в это всё.
Изначально речь шла о тезисе, что данная книга - школьное пособие. Автор не упоминает олимпиады в аннотации и введении (хотя в тексте некоторых задач дает примечание, что они были предложены на олимпиадах). В тоже время автор говорит об общеобразовательных школах. Именно это меня и удивило.
Почему бы в детском саду не поиграться с дискретной математикой, вместо сами знаете какой ерунды?
Речь шла о книге, которую автор позиционирует как пособие для школьного образования и о моём недоумении подобной характеристикой. Считаю излишним агитировать за или против помощи своему ребенку в развитии. Однако, сомневаюсь в способности и, главное, мотивации большинства школьников и учителей ИВТ среднеобразовательных школ освоить и дать представленный в книге материал. К счастью это не отменяет тех самых выдающихся одаренных детей и их исключительных преподавателей, коим являлся сам автор. Надеюсь, усилия государства в этом направлении, изменят ситуацию. Буду рад ошибиться и узнать, что с 90-х и начала нулевых ситуация действительно поменялась.
Благодарю за ссылки. По ним можно дойти до интересного документа, являющегося основанием всей этой деятельности:
Правила выявления детей, проявивших выдающиеся способности, и сопровождения их дальнейшего развития (утв. постановлением Правительства РФ от 17 ноября 2015 г. N 1239) 2. Выявление одаренных детей осуществляется ... посредством проведения олимпиад ... 6. По итогам проведения мероприятия организатор ... направляет ... в веб-интерфейс государственного информационного ресурса о лицах, проявивших выдающиеся способности, предусмотренного пунктом 9 настоящих Правил, информацию об одаренных детях, являющихся победителями и призерами заключительного этапа мероприятий ... 7. Информация ... направляется ... для формирования их портфолио и организации дальнейшей поддержки и сопровождения этих одаренных детей. 11. Сопровождение дальнейшего развития одаренных детей ... в следующих формах: а) обеспечение индивидуальной работы с одаренными детьми по формированию и развитию их познавательных интересов, в том числе тьюторской и (или) тренерской поддержки; б) профессиональная ориентация одаренных детей посредством повышения их мотивации к трудовой деятельности по профессиям, специальностям, направлениям подготовки, востребованным на рынке труда; в) содействие в трудоустройстве после окончания обучения; г) психолого-педагогическое сопровождение одаренных детей;
К сожалению, все это великолепие прошло мимо меня и я о нём даже не подозревал. У детей в школе чего-то такого тоже не замечал. Возможно, "выдающиеся" и "одаренные" - это поиск самородков в тысячах тонн породы. Я ни в коем случае не хочу умалять достижений олимпиадников. Я ими готов восхищаться и гордиться. Но собеседуя соискателей на вакансии разработчиков я вижу простых людей, которые окончили "простую школу", "простой институт" и имеют опыт предыдущей работы. Их бесполезно спрашивать про алгоритм Кнута-Морриса-Пратта. При этом они вполне справляются с решением задач в виде написания приложения, тестов и документации. На моей практике, тех, кто разбираются в структурах и алгоритмах, среди соискателей менее 10%.
Возвращаясь к тому, с чего всё началось: пособие для школьного олимпиадного кружка по информатике. Соглашаюсь. Каюсь: неверно истолковал как "в каждой школе это проходят".
Речь идет о любой школе, где есть вменяемый преподаватель, который готов вести такой кружок. И найдётся несколько интересующихся ребят, готовых на этот кружок ходить. Дело это добровольное, поэтому там, в общем-то, не "проходят", а просто этим занимаются
Ну я как человек когда-то преподававший информатику в школе могу сказать, что сильно повезет, если в классе есть хотя бы десяток ребят, у которых не ветер в голове, и еще сильнее повезет, если информатикой (а не химией, биологией, физикой, языком) заинтересуется хотя бы половина из них. Большая удача наскрести участников на школьную олимпиаду с реально ценными призами и подарками. В готовности школьника разбирать балансировку дерева после вставки я сильно сомневаюсь. В мотивации учителя факультативно это преподавать одному-двум ученикам тем более. Конечно, исключения бывают и среди первых, и среди вторых. Но это действительно исключения. Посмотрите, например, результаты по заключительным этапам ВсОШ по информатике по приведенной iliazeus ссылке.
Особенность прикладной дискретной математики, на мой взгляд, в том, что это, в сущности, игра в кубики. В той или иной форме эта дисциплина доступна не то, что в школе, а порою и в детском саду. А если кому-то она не даётся, то это не аргумент. В конце-концов, не все же должны этим заниматься.
Да, есть дети, которые в 3 года говорят на нескольких языках, выступают на скрипке и умножают двузначные числа в уме. Означает ли это, что все остальные должны соответствовать их уровню и школьный стандарт должен соответствовать бакалавриату? К сожалению, реальность такова, что далеко не каждый десятый и даже не двадцатый разработчик с опытом расскажет вам характеристики, как работает и как реализованы самые часто используемые контейнеры стандартной библиотеки ежедневно используемого им языка.
Посмотрите, например, задачки с некоторых предыдущих олимпиад.
Спасибо, посмотрел. Задачи очень сильно выходящие за школьную программу - это финальный этап. Но и там область необходимых знаний ограничена и не требует, например, реализовывать разбор текста по грамматике. Что наверное логично.
Вот для примера кусок оглавления:
10. Сопоставление с образцом
10.1. Простейший пример
10.2. Повторения в образце - источник проблем
10.3. Вспомогательные утверждения
10.4. Алгоритм Кнута - Морриса - Пратта
10.5. Алгоритм Бойера - Мура
10.6. Алгоритм Рабина
10.7. Более сложные образцы и автоматы
10.8. Суффиксные деревья
11. Анализ игр
11.1. Примеры игр
11.2. Цена игры
11.3. Вычисление цены: полный обход
11.4. Альфа-бета-процедура
11.5. Ретроспективный анализ
Какие задачи на каких олимпиадах требуют этих знаний и в какой школе их дают?
пособие для школьного олимпиадного кружка по информатике
А что именно там из школьной программы? Я понимаю, что гипербола - это такой художественный прием, но если серьезно, то какая часть студентов первого курса это поймет? Очень далеко не каждый соискатель на место разработчика расскажет, как хеш таблицы работают, а вы утверждаете, что сжатие данных в школе проходят. Не могли бы уточнить о какой школе речь?
def "9.2"() {
given:
Map<String, Ex_9.ItemInfo> inventory = [water : new Ex_9.ItemInfo(10.0, 3),
book : new Ex_9.ItemInfo(3.0, 1),
food : new Ex_9.ItemInfo(9.0, 2),
jacket: new Ex_9.ItemInfo(5.0, 2),
camera: new Ex_9.ItemInfo(6.0, 1),]
int bagSize = 6
when:
Set<String> result = new Ex_9().optimizeBagDynamic(inventory, bagSize)
then:
result ==~ ['water', 'food', 'camera']
}
Структура проекта - стандартный Java и C++ проекты Gradle.
прошу привести конкретные тесты на замер сравнения производительности вашей реализации и моей (полностью основанной на исходных кодах ГА)
Если обе реализации основаны на алгоритме, который в книге, то нет смысла что-то сравнивать. Одно дело взять реализацию варианта быстрой сортировки выбором с обменом и сравнить с реализацией варианта быстрой сортировки расщеплением, а потом сравнить потребление памяти и времени и глубину стека. А так что мы будем сравнивать? Кто сколько наоптимизировал отойдя от того, что есть в книге?
скидывайте ссылку на свой репо с вашей реализацией
Ссылка дана в конце статьи.
Все приведенные примеры ГА рабочие, на их основе я создал свою реализацию
Ключевая часть "на их основе я создал свою реализацию". А вот с "Все приведенные примеры ГА рабочие" есть проблемы. Например, в главе 9 есть пример с самой длинной общей подпоследовательностью двух строк. Автор берет слова с одинаковым количеством букв, причем первые буквы совпадают. Это очень удобно, так как не надо думать о начальных условиях и тому подобном. На практике, приведенный в книге код легко выйдет за левую и верхнюю границы. Это никак не учитывается при обращении к предыдущей строке/ячейке. Ровно также из ниоткуда появляется значение первой ячейки.
Не могу сказать, ибо не знаю. Но видимо, там рекомендуют какую-то более серьезную литературу. Возможно, что-то что перечислил HotkeyM или SibProgrammer.
и этот псевдокод еще очень странный и далёкий от современного программирования
Да эти примеры кода далеки от того, что каждый из нас увидит в коде коллеги или напишет сам. Но есть у такого подхода и преимущество. Во-первых, он позволяет точнее оценить стоимость алгоритма и, например, сравнить два алгоритма с одинаковой асимптотикой. У Кнута много таких примеров, где изначальный алгоритм оптимизируется и показывается за счет чего и на сколько именно получен выигрыш. Такая возможность появляется как раз благодаря тому, что код написан на машинном языке и хорошо видно сколько чего выполняется. Во-вторых, при таком подходе невозможна магия. Рукава закатаны и все прекрасно видно. Никаких допущений, что язык или библиотека, что-то сделали, а ты об этом не рассказал. Два примера. В том же ГА при описании быстрой сортировки приведен вот такой код:
Код работает правильно, все понятно, все приближено к современной реальности. Но за этой простотой и понятностью скрываются циклы и копирования. Эффективность такой реализации сомнительна. Второй пример: в Алгоритмике при объяснении метода двух указателей на примере сортировки слиянием можно увидеть вот такой код:
Не изучавшему STL будет сложно понять, что это std::merge из C++ и что тут на самом деле цикл и внутри него if, копирование и инкремент одного из двух указателей. Код короткий и хорошо понятный опытному C++ разработчику. Но для всех других такая высокоуровневость скорее помешает понять алгоритм.
Я не буду утверждать, что код у Кнута хорошо читается и переводится на нормальные языки. Но мое мнение, что не в этом его цель. Для понимания алгоритма у Кнута к каждой программе сначала идет пошаговое текстовое описание на человеческом языке и иллюстрация.
Но я соглашусь. Текст тяжелый, половина книг - упражнения и решения к ним. Это совсем не тоже, что каталог для практиков как у GoF.
ты пишешь "хотелось бы каталога алгоритмов". На мой взгляд монография Donald E. Knuth "The Art of Computer Programming" остается наилучшим вариантом.
К сожалению на русском можно купить только первые три тома. Четвертый том не найти. Остальные и вовсе не переводились. А похоже именно там комбинаторика, статистические методы, NP-полные задачи и т.п. По крайней мере этого нет в первых трех томах. Можно конечно и в электронном, и на английском почитать, но это не совсем то.
Скорее всего, в лицензионном соглашении указано, что всю ответственность несёт пользователь инструмента. В любом случае, суд не будет разбираться как украденный код появился в твоём продукте. Твой продукт - твоя ответственность. Ну а дальше можешь попробовать её частично возместить за счёт поставщика инструментария.
У каждой лицензии свои требования. Указание авторства лишь одно из них. Причём самое безобидное. Веселее, когда суд обяжет вас опубликовать код вашего коммерческого продукта под открытой лицензией или выплатить % выручки авторам библиотеки, которая была свободной только для некоммерческого использования. Но это раньше и больше в США и Европе. Как будет теперь и в России - большой вопрос.
Полное оглавление - это 7 страниц. Вам будет проще посмотреть его на сайте издательства по приведённой ссылке:
Доказательства корректности, анализ и доказательство сложности идут отдельными секциями после всех объяснений. Эти секции никак не мешают чтению остального материала. При необходимости, их можно просто пропускать. Идентифицировать их легко, они так и называются:
Корректность
Время исполнения
Правильность
Время работы
И тому подобное.
Благодарю. Исправил.
Благодарю, исправил. В разделе "Свободно распространяемые издания" ссылка именно на предыдущее. Наверное, забыли обновить.
Да, автор не пишет O(nlogn), но для половины задач либо дано условие, либо дан анализ: "число операций пропорционально log n", "число шагов не должно превосходить ?1 log(a/b) + ?2 для некоторых констант ?1, ?2", "время работы остаётся порядка ?^2" и тому подобное. Возможно, это неканонично. Возможно, это понятнее, чем "сложность O(n^2)".
В некоторых местах рассматриваются и затраты памяти. В некоторых местах рассматривается худший случай и в среднем.
Нет, он говорит о том, что книга написана по материалам занятий программированием со школьниками. Я позволил себе усомниться в том, что это простые школьники.
Так каков же вывод? Книга для школьников (пусть и олимпиадников) и взрослому человеку читать её стыдно или поздно?
Ну мне не стыдно. Я почерпнул для себя новое. Мне было интересно. Тем, кто уже давно не школьник, я, по прежнему, её рекомендую:
Если сравнивать с "Грокаем алгоритмы", то лучше уж прочитать "Программирование: теоремы и задачи". Да, наверное есть другие книги, где нет доказательства корректности и задач без решений и они будут более эффективны в плане затрат времени и полученного результата. Например,
Для этого мы мнением и обмениваемся. Нет общепризнанного списка о том, что читать и в каком порядке. В соседней ветке с обзором "Грокаем алгоритмы" тоже рекомендовали каноничные тексты, но каждый рекомендовал свой набор. Я уже пополнил список того, что мне стоит прочесть. Если кто-то заинтересуется книгой А. Шеня или наоборот из моего описания или ваших комментариев поймет, что она ему не подходит и не потратит время зря - тоже хорошо.
Изначально речь шла о тезисе, что данная книга - школьное пособие. Автор не упоминает олимпиады в аннотации и введении (хотя в тексте некоторых задач дает примечание, что они были предложены на олимпиадах). В тоже время автор говорит об общеобразовательных школах. Именно это меня и удивило.
Речь шла о книге, которую автор позиционирует как пособие для школьного образования и о моём недоумении подобной характеристикой. Считаю излишним агитировать за или против помощи своему ребенку в развитии. Однако, сомневаюсь в способности и, главное, мотивации большинства школьников и учителей ИВТ среднеобразовательных школ освоить и дать представленный в книге материал. К счастью это не отменяет тех самых выдающихся одаренных детей и их исключительных преподавателей, коим являлся сам автор. Надеюсь, усилия государства в этом направлении, изменят ситуацию. Буду рад ошибиться и узнать, что с 90-х и начала нулевых ситуация действительно поменялась.
Благодарю за ссылки. По ним можно дойти до интересного документа, являющегося основанием всей этой деятельности:
К сожалению, все это великолепие прошло мимо меня и я о нём даже не подозревал. У детей в школе чего-то такого тоже не замечал. Возможно, "выдающиеся" и "одаренные" - это поиск самородков в тысячах тонн породы. Я ни в коем случае не хочу умалять достижений олимпиадников. Я ими готов восхищаться и гордиться. Но собеседуя соискателей на вакансии разработчиков я вижу простых людей, которые окончили "простую школу", "простой институт" и имеют опыт предыдущей работы. Их бесполезно спрашивать про алгоритм Кнута-Морриса-Пратта. При этом они вполне справляются с решением задач в виде написания приложения, тестов и документации. На моей практике, тех, кто разбираются в структурах и алгоритмах, среди соискателей менее 10%.
Возвращаясь к тому, с чего всё началось: пособие для школьного олимпиадного кружка по информатике. Соглашаюсь. Каюсь: неверно истолковал как "в каждой школе это проходят".
Ну я как человек когда-то преподававший информатику в школе могу сказать, что сильно повезет, если в классе есть хотя бы десяток ребят, у которых не ветер в голове, и еще сильнее повезет, если информатикой (а не химией, биологией, физикой, языком) заинтересуется хотя бы половина из них. Большая удача наскрести участников на школьную олимпиаду с реально ценными призами и подарками. В готовности школьника разбирать балансировку дерева после вставки я сильно сомневаюсь. В мотивации учителя факультативно это преподавать одному-двум ученикам тем более. Конечно, исключения бывают и среди первых, и среди вторых. Но это действительно исключения. Посмотрите, например, результаты по заключительным этапам ВсОШ по информатике по приведенной iliazeus ссылке.
Да, есть дети, которые в 3 года говорят на нескольких языках, выступают на скрипке и умножают двузначные числа в уме. Означает ли это, что все остальные должны соответствовать их уровню и школьный стандарт должен соответствовать бакалавриату? К сожалению, реальность такова, что далеко не каждый десятый и даже не двадцатый разработчик с опытом расскажет вам характеристики, как работает и как реализованы самые часто используемые контейнеры стандартной библиотеки ежедневно используемого им языка.
Спасибо, посмотрел. Задачи очень сильно выходящие за школьную программу - это финальный этап. Но и там область необходимых знаний ограничена и не требует, например, реализовывать разбор текста по грамматике. Что наверное логично.
Вот для примера кусок оглавления:
Какие задачи на каких олимпиадах требуют этих знаний и в какой школе их дают?
А что именно там из школьной программы? Я понимаю, что гипербола - это такой художественный прием, но если серьезно, то какая часть студентов первого курса это поймет? Очень далеко не каждый соискатель на место разработчика расскажет, как хеш таблицы работают, а вы утверждаете, что сжатие данных в школе проходят. Не могли бы уточнить о какой школе речь?
Примеры использования можно найти в тестах. Для Java использован Spock, а для C++ - CUnit.
Например, задача оптимизации туристического рюкзака из 9-й главы
Структура проекта - стандартный Java и C++ проекты Gradle.
Если обе реализации основаны на алгоритме, который в книге, то нет смысла что-то сравнивать. Одно дело взять реализацию варианта быстрой сортировки выбором с обменом и сравнить с реализацией варианта быстрой сортировки расщеплением, а потом сравнить потребление памяти и времени и глубину стека. А так что мы будем сравнивать? Кто сколько наоптимизировал отойдя от того, что есть в книге?
Ссылка дана в конце статьи.
Ключевая часть "на их основе я создал свою реализацию". А вот с "Все приведенные примеры ГА рабочие" есть проблемы. Например, в главе 9 есть пример с самой длинной общей подпоследовательностью двух строк. Автор берет слова с одинаковым количеством букв, причем первые буквы совпадают. Это очень удобно, так как не надо думать о начальных условиях и тому подобном. На практике, приведенный в книге код легко выйдет за левую и верхнюю границы. Это никак не учитывается при обращении к предыдущей строке/ячейке. Ровно также из ниоткуда появляется значение первой ячейки.
Похоже только с рук или в букинистике.
Не могу сказать, ибо не знаю. Но видимо, там рекомендуют какую-то более серьезную литературу. Возможно, что-то что перечислил HotkeyM или SibProgrammer.
Да эти примеры кода далеки от того, что каждый из нас увидит в коде коллеги или напишет сам. Но есть у такого подхода и преимущество. Во-первых, он позволяет точнее оценить стоимость алгоритма и, например, сравнить два алгоритма с одинаковой асимптотикой. У Кнута много таких примеров, где изначальный алгоритм оптимизируется и показывается за счет чего и на сколько именно получен выигрыш. Такая возможность появляется как раз благодаря тому, что код написан на машинном языке и хорошо видно сколько чего выполняется. Во-вторых, при таком подходе невозможна магия. Рукава закатаны и все прекрасно видно. Никаких допущений, что язык или библиотека, что-то сделали, а ты об этом не рассказал. Два примера. В том же ГА при описании быстрой сортировки приведен вот такой код:
Код работает правильно, все понятно, все приближено к современной реальности. Но за этой простотой и понятностью скрываются циклы и копирования. Эффективность такой реализации сомнительна. Второй пример: в Алгоритмике при объяснении метода двух указателей на примере сортировки слиянием можно увидеть вот такой код:
Не изучавшему STL будет сложно понять, что это std::merge из C++ и что тут на самом деле цикл и внутри него if, копирование и инкремент одного из двух указателей. Код короткий и хорошо понятный опытному C++ разработчику. Но для всех других такая высокоуровневость скорее помешает понять алгоритм.
Я не буду утверждать, что код у Кнута хорошо читается и переводится на нормальные языки. Но мое мнение, что не в этом его цель. Для понимания алгоритма у Кнута к каждой программе сначала идет пошаговое текстовое описание на человеческом языке и иллюстрация.
Но я соглашусь. Текст тяжелый, половина книг - упражнения и решения к ним. Это совсем не тоже, что каталог для практиков как у GoF.
К сожалению на русском можно купить только первые три тома. Четвертый том не найти. Остальные и вовсе не переводились. А похоже именно там комбинаторика, статистические методы, NP-полные задачи и т.п. По крайней мере этого нет в первых трех томах. Можно конечно и в электронном, и на английском почитать, но это не совсем то.