• Каспаров против Deep Blue. Часть II: Филадельфийский эксперимент


      После некоторого перерыва, продолжаю серию статей (а также обещаю в ближайшее время её закончить) про многолетнюю шахматную борьбу двух миров – человеческого и компьютерного. Планировалось, что Rom77 напишет статьи про обе битвы Каспарова с Deep Blue, но, к сожалению, мой соавтор, написавший отличное начало, не выходит на связь. Мне иногда приходят письма от благодарных читателей с вопросом почему же до сих пор нет продолжения, поэтому, вновь берусь за перо сажусь за клавиатуру, дабы продолжить прервавшееся повествование про приключения Гарри и его кремниевых друзей. Помимо разрозненных сведений о событиях тех лет, в статье также решил использовать, оказавшиеся в моём распоряжении, черновые наброски Романа про матч 1996 года.
      Название статьи, кстати, тоже придумал он
      • +56
      • 19,6k
      • 6
    • Первые обидчики. Fritz и Genius


        Вторая серия о многолетней борьбе Каспарова с армадой терминаторов. Первую статью из цикла читайте здесь.

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

        Участие компьютеров в человеческих соревнованиях вошло в моду. IT-компании охотно и щедро спонсировали мероприятия, с непременным условием – роботы играют на тех же правах, что и люди. Особенно интересен 1994 год, в которых произошли несколько знаковых событий, когда внезапно компьютеры начали регулярно наносить людям чувствительные поражения.
        Причём досталось и чемпиону мира
      • Каспаров – Deep Thought. Игра в одни ворота


          История о нашумевшем противостоянии Каспарова с детищем IBM уже затрагивалась на GeekTimes Хабре. Мой комментарий хоть и набрал приличное количество плюсов, содержит несколько существенных неточностей, которые я уже исправить, увы, не в силах. Дабы внести ясность и расставить все точки над ё, было решено написать более подробную статью про этот знаковый матч. Однако в творческом процессе выяснилось, что затронутая тема гораздо обширнее, многограннее и интереснее, и охватывает куда больший период времени. А посему статья про матч 1997 года органично трансформировалась в серию публикаций о незаурядных победах и поражениях 13-го чемпиона мира в борьбе с искусственным разумом на протяжении 15 лет.
          С чего же всё начиналось
          • +71
          • 16,6k
          • 8
        • J-сортировка


            Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм который, пожалуй, должен знать любой программист. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени (причём, очень пристойная) – O(n log n). Лучших и вырожденных случаев для неё нет.

            С момента изобретения метода (а в этом году алгоритм празднует свой полувековой юбилей) было немало охочих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом – вот неполный список инноваций. Перечисленные алгоритмы хотя при тестировании и опережают оригинал по абсолютной скорости кто на 12, а кто и на 25%, в оценке временной сложности всё равно крутятся вокруг O(n log n). При этом данные методы весьма изощрённо реализованы.

            Своё видение пирамидальной сортировки предложил и скромный труженик Университета Манитобы Джейсон Моррисон. При этом способ в некоторых случаях по скорости приближается к O(n).

            Так ещё метод и прост до безобразия
          • Корректный YML для Яндекс.Маркета. Взгляд программиста


              Многие интернет-магазины попадают в Яндекс.Маркет, не все там остаются надолго. Одно из условий присутствия в ЯМ-е – наличие корректного прайса в специальном формате YML.

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

              Данная статья – попытка обобщить те ошибки, с которыми сталкиваются программисты, впервые создающие инструменты (будь то автономный скрипт или плагин для CMS) для генерации YML-файла. Тем, кто с этим чудным форматом имел дело раньше, статья уже будет не столь интересна, ибо всё шишки набиты. Впрочем, вдруг и ветераны борьбы за своё место под солнцем Яндекса узнают что-то новое для себя. А то и поделятся собственным фронтовым опытом.
              YML? Легко!
            • Эзотерические сортировки Дэвида Морган-Мара



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

                Сплошная алгоритмическая эзотерика
              • Глупая сортировка и некоторые другие, поумнее


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

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

                  image: эволюция

                  Другое ответвление глупой сортировки
                • Пузырьковая сортировка и все-все-все


                    Все отлично знают, что из класса обменных сортировок самый быстрый метод – это так называемая быстрая сортировка. О ней пишут диссертации, её посвящено немало статей на Хабре, на её основе придумывают сложные гибридные алгоритмы. Но сегодня речь пойдёт не про quick sort, а про другой обменный способ – старую добрую пузырьковую сортировку и её улучшения, модификации, мутации и разновидности.

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

                    image: пузырьки

                    Сделать первый шаг в изучении сортировок
                  • ABC-сортировка


                      Данная разновидность поразрядной MSD-сортировки «заточена» для строк. Впрочем, алгоритм так назван отнюдь не за лексическую специализацию. Автор Аллен Бичик (Allen Beechick) выбрал название в честь себя любимого, ABCsort расшифровывается как Allen Beechick Character sort.

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

                      Что касается алгоритма, то это единственно известная мне сортировка, за использование которой её изобретатель требует деньги.
                      Богоугодная сортировка за 88 у.е.
                    • Бисерная сортировка (Bead sort)


                        Сегодня предложу Вашему вниманию симпатичный алгоритм, который хоть и придумали совсем недавно (11 лет назад), но «прототипом» послужило счётное устройство с трёхтысячелетней историей.
                        Но обо всём по порядку