[Перевод] Как простая задача о голубях помогает математической теории сложности

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

https://habr.com/ru/articles/903410/

#голуби #теория_сложности #гнезда #информатика

Как даже 6 простых команд на поле 4x4 могут стать головной болью геймдизайнера

Я автор настольной игры о программируемых роботах «Битва Големов». Игры, обучающей детей от 6–7 лет. И я хочу рассказать, почему даже 6 простых команд, которые «понимают» роботы, стали для меня головной болью, как я решал проблемы игровой механики и почему в итоге правила игры «распухли» до 16 страниц, но это не страшно.

https://habr.com/ru/articles/878474/

#информатика #робототехника #настольная_игра #геймдев #программирование #образование #образование_детей

Настольные игры по Информатике, Химии и Физике — что искать и ждать в 2025 году?

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

https://habr.com/ru/articles/878390/

#настольная_игра #информатика #физика #химия #робототехника #образование_детей #программирование

[Перевод] Специалисты по информатике объединили два «красивых» метода доказательства

Как доказать, что что-то истинно? Для математиков ответ прост: начните с базовых предположений и шаг за шагом дойдите до вывода. ЧТД, доказательство завершено. Если где-то есть ошибка, эксперт, внимательно прочитавший доказательство, сможет её заметить. В противном случае доказательство должно быть верным. Математики придерживаются этого базового подхода уже более 2 000 лет. Затем, в 1980-х и 1990-х годах, учёные-информатики переосмыслили, каким может быть доказательство. Они разработали головокружительное разнообразие новых подходов, и когда пыль осела, два изобретения стали особенно заметны: доказательства с нулевым знанием, которые могут убедить скептика в истинности утверждения, не раскрывая причин его истинности, и вероятностно проверяемые доказательства, которые могут убедить читателя в истинности доказательства, даже если он видит лишь несколько крошечных фрагментов.

https://habr.com/ru/articles/854350/

#раскраска_карты #интерактивные_доказательства #информатика

Куда уходят звёзды? Сверхновые события, химия нейтронных звёзд и массовые вымирания. Интервью с астрономом

Весной 2024 года мы начали работу над новым материалом. Посещение Крымской астрофизической обсерватории , проход на уникальный телескоп «Синтез» и беседа с Сергеем Назаровым , научным сотрудником КрАО , позволили нам узнать много нового о сверхновых звёздах. Эти драматические события наполняют галактику веществом, и результат космических катастроф каждый из нас может видеть в зеркале. Куда уходят звёзды, какие явления происходят в последние секунды их жизни и что это значит для человечества? Об этом и многом другом вы узнаете из интервью с профессиональным астрономом.

https://habr.com/ru/companies/first/articles/827174/

#звезды #наука #астрономия #звездная_пыль #звёздная_атмосфера #сверхновые #нейросети #математика #информатика #математическое_моделирование

[Перевод] Новый прорыв приближает умножение матриц к идеалу

Устранив скрытую неэффективность, учёные придумали новый способ умножения больших матриц, который работает быстрее, чем когда-либо. Учёные, занимающиеся информатикой, — это требовательная группа. Им недостаточно получить правильный ответ — цель почти всегда состоит в том, чтобы получить ответ как можно эффективнее. Возьмем, к примеру, умножение матриц или массивов чисел. В 1812 году французский математик Жак Филипп Мари Бине разработал базовый набор правил, которым мы до сих пор обучаем студентов. Это работает прекрасно, но другие математики нашли способы упростить и ускорить процесс умножения матриц.

https://habr.com/ru/companies/first/articles/814453/

#матричное_умножение #матрица #информатика #алгоритмы #лазерный_метод #алгоритм_штрассена

Размышления о выборе языка программирования для школы (и ситуации с информатикой в целом)…

Эта статья выросла из ответа на комментарии к статье Основные отличия PascalABC.NET , где возник традиционный спор про то, есть ли смысл в 2023 году изучать Pascal. Для комментов мой ответ слишком большой, так что оформлю в виде такого спонтанного поста. Как бывший программист-практик, ныне преподающий информатику в обычной сельской школе, выскажу своё мнение касательно Pacal в школе, да и вообще того, как сейчас обстоят дела с изучением информатики. Сразу уточню: речь, прежде всего, идёт о среднем звене "среднестатистических" школ, где информатика изучается строго по ФГОС - только с 7-9 классы, по 1 часу (уроку в 40-45 минут) в неделю. Если хотите изучить "единую министерскую" программу, можете скачать её с официального сайта Минпроса. Конкретно на программирование эта программа отводит порядка 30 часов . По 1 часу в неделю, растянутых на конец 8 - начало 9 классов (с перерывом в 3 месяца, ага). За это время авторы ФГОС предлагают с нуля (!) объяснить детям (которые только-только поверхностно изучили строение компьютера и принципы работы с мышино-клавиатурным интерфейсом (а нынешние дети реально от мыши тупят, т.к. с пелёнок привыкли к тачскринам!) ):

https://habr.com/ru/articles/783900/

#школа #информатика #pascal #python

Дополнительный код/запись отрицательных чисел в памяти компьютера

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

https://habr.com/ru/articles/783842/

#дополнительный_код #информатика #отрицательные_числа #знаковые_числа #signed_binary

[Перевод] Простая проблема приводит к слишком большим числам для нашей Вселенной

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

https://habr.com/ru/companies/first/articles/782118/

#алгоритмы #вычислительная_сложность #информатика