Рубрика «Занимательные задачки»

Введение

В мае далёкого 2015 года я заканчивал бакалавриат факультета общей и прикладной физики МФТИ. В основном я занимаюсь квантовой теорией поля, но в тот момент я решил, что хотелось бы больше вникнуть в современный мир компьютерных наук, что можно попробовать совместить МФТИ с ШАД Yandex (две магистратуры). ШАД тогда уже был у всех на слуху, вокруг только и твердили, какой там жёсткий курс алгоритмов, мне понравился сайт (лол), тематика курсов, и я решился поступать.

В этом посте я хотел бы рассказать о том, как происходило моё поступление в ШАД, рассказать своё решение экзаменационного варианта (разборов ШАДовских заданий на просторах рунета не очень-то много) и поговорить о том, что понравилось / не понравилось в этом замечательном заведении.
Читать полностью »

Фильм «Скрытые фигуры»: задачи из фильма и современный подход к расчетам орбиты и возвращения на Землю - 1

Перевод поста Джеффри Брайанта (Jeffrey Bryant), Пако Джейна (Paco Jain) и Майкл Тротта (Michael Trott) "Hidden Figures: Modern Approaches to Orbit and Reentry Calculations".
Код, приведенный в статье, можно скачать здесь.
Выражаю огромную благодарность Полине Сологуб за помощь в переводе и подготовке публикации


Содержание

Размещение спутника в определенном месте
Константы и первичная обработка
Вычисления
Построение графика
Как рассчитываются орбиты сегодня
Моделирование возвращаемого спутника


Вышедший недавно в кинотеатрах фильм Скрытые фигуры получил хорошие отзывы. Действие разворачивается в важный период истории США; в нем затрагивается также ряд тем вроде гражданских прав и космической гонки. В центре повествования — история Кэтрин Джонсон и ее коллег (Дороти Воган и Мэри Джексон) из NASA в период развертывания программы Меркурий и ранних исследований пилотируемых космических полетов. Внимание также акцентируется на драматической борьбе за гражданские права афро-американских женщин в NASA, происходившей в то время. Компьютеры в то время едва появились, так что способность Джонсон и ее коллег решать сложные навигационные задачи орбитальной механики без использования компьютера обеспечили важную проверку ранних компьютерных результатов.

Фильм «Скрытые фигуры»: задачи из фильма и современный подход к расчетам орбиты и возвращения на Землю - 2

Я остановлюсь на двух аспектах ее научной работы, упомянутых в фильме: вычислениях орбиты и расчетах, связанных с вхождением в атмосферу. Для орбитальных вычислений я сначала сделал ровно то же, что и Джонсон, а затем применил более современный прямой подход с использованием инструментов Wolfram Language. В фильме упоминается о решении дифференциальных уравнений методом Эйлера; я же буду сравнивать этот метод с более современным и вычислю возвратную траекторию с помощью данных модели атмосферы, полученных непосредственно из Wolfram Language).
Читать полностью »

Ученые из Университета ИТМО разработали прототип устройства для беспроводной передачи энергии, в основу которого легли диэлектрические диски-резонаторы. Эффективность технологии достигает 90%, при этом она состоятельна даже в случае изменения взаиморасположения источника и приемника.

Ученые из Университета ИТМО предложили новую систему передачи энергии на расстояние - 1Читать полностью »

Как говорить с искусственным интеллектом? - 1

Перевод поста Стивена Вольфрама (Stephen Wolfram) "How Should We Talk to AIs?".
Выражаю огромную благодарность Полине Сологуб за помощь в переводе и подготовке публикации


Содержание

Вычисления — это сила
Язык вычислительного мышления
Понимание ИИ
Что будет делать ИИ?
Постановка целей для ИИ
Разговор одного ИИ с другим
Сбор информации: обзор миллиарда лет
А что, если бы каждый мог писать код?
Действительно ли это будет работать?
Скажу больше


Еще совсем недавно идея иметь компьютер, который может отвечать на вопросы на английском языке, казалась научной фантастикой. Но когда мы в 2009 году выпустили Wolfram|Alpha, одним из самых больших сюрпризов (по крайней мере, для меня!) стало то, что мы сумели сделать наш продукт реально работающим. И теперь люди ежедневно задают личным помощникам несметное количество вопросов — на обычном разговорном языке.

Как говорить с искусственным интеллектом? - 2

Все это достаточно неплохо работает (хотя мы всегда стараемся сделать лучше!). Но как насчет более сложных вещей? Как общаться с искусственным интеллектом?

Я долго думал об этом, пытаясь совместить философию, лингвистику, неврологию, информатику и другие области знания. И я понял, что ответ всегда был перед моим носом, и лежал он в той сфере, которой я занимался последние 30 лет: Wolfram Language.

Может быть, это как раз тот случай, когда у вас есть молоток, и вы видите вокруг одни гвозди. Хотя я уверен, что дело не только в этом. По крайней мере, продумывание этого вопроса — хороший способ понять больше об искусственном интеллекте и его взаимоотношениях с людьми.
Читать полностью »

Рассмотрим следующую задачу. Найти период дроби 1/81. Уверяю, что для решения не потребуется ни калькулятор, ни деление столбиком. Для начала вспомним чему равно 81*(Период). Пусть длина периода n, тогда исходная дробь запишется как:

$frac{1}p=frac{Период}{10^n}+frac{Период}{10^{2n}}+frac{Период}{10^{3n}}+...$

Перепишем данное представление в следующем виде:

$frac{1}p=frac{Период}{10^n}+frac{1}{10^n}*(frac{Период}{10^{n}}+frac{Период}{10^{2n}}+..)$

Последнее выражение можно представить так:

$frac{1}p=frac{Период}{10^n}+frac{1}{10^n}*frac{1}p$

Ну а теперь то соотношение, которое мы искали:

$p*Период=10^n-1$

Для нашего случая это тождество будет следующим:

$81*Период=10^n-1$

Разделим левую и правую часть на 9, получим:

$9=111...111$

Читать полностью »

Прошло 1 апреля. Часто первоапрельские шутки, выложенные в Интернете, продолжают свое шествие, и всплывают совершенно в неожиданное время. О такой шутке про язык Си и будет эта статья. В каждой шутке есть только доля шутки, и я ее взял на вооружение для беглого тестирования на знание языка Си.

Надо написать программу (с пояснениями), в которой будет работать следующая строка:

for(;P("n"),R--;P("|"))for(e=C;e--;P("_"+(*u++/8)%2))P("| "+(*u/4)%2);

Всего одна строка, но по ней можно определить глубину понимания человеком языка Си. Эта строка будет работать также и на С++. Советую попробовать свои силы. Может будет полезно.
Читать полностью »

Троичные вычисления

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

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

Итак, вот список опубликованных статей цикла (будет обновляться):

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

Считаем до трёх: два - 1

Читать полностью »

Угадай фильтр по импульсной характеристике - 1

На некотором сайте, в некотором форуме, добрый молодец по прозвищу SciFi озадачил коллектив свой историей.
Нашел он в руководящих технических материалах иноземной фирмы Texis Instrument [FSK Modulation and Demodulation With the MSP430 Microcontroller] требуемый ему цифровой фильтр. Но иноземцы шибко хитры оказались, и в исходном коде привели следующее:
Читать полностью »

Haskell: об одном методе реализации функций с переменным числом параметров - 1

– А видела ты Черепаху «Как бы»?
– Нет, – сказала Алиса. – Я даже не знаю, кто это такой.
– Как же, – сказала Королева. – Это то, из чего делают «Как бы черепаший суп».

                  Льюис Кэрролл, 
                           «Алиса в Стране чудес»

— Судя по твоим речам, ты хорошо знаешь Фангорн? — спросил в ответ Арагорн.
— Какое там! — отозвался старик. — На это ста жизней не хватит. Но я сюда иной раз захаживаю.

                 Джон Р. Р. Толкиен, 
                          «Властелин Колец» — к слову о моём знании Haskell ;)

Homines dum docent, discunt. (Объясни другим — сам поймёшь.)

                 народная латинская поговорка

Все знают, что любая функция Haskell по своей сути является функцией одного параметра. Функции «как бы» нескольких параметров просто принимая первый аргумент, возвращают другую функцию, принимающую второй аргумент (исходной функции) и обратно возвращающую функцию и т.д. до финальной функции, которая уже возвращает значение не функционального типа (каррирование).

Казалось бы о каком переменном числе параметров может идти речь при таком раскладе? Однако поразмыслив, посмотрев исходники printf или просто почитав wiki.haskell становится очевидным, что как раз ФП даёт ключ к достаточно красивому, хотя и несколько «казуистическому» решению этой задачи.

В настоящей публикации я рассмотрю один из способов реализации такого механизма на простых примерах, а также предложу некоторое обобщённое решение на базе Template Haskell, для превращения семейства обычных функций с последним параметром типа список в функцию с «как бы с переменным числом параметром» (далее по тексту просто «с переменным числом параметром»).
Читать полностью »

image
Жилой массив людей. Нет, серьёзно.

Холивары между ценителями Си и приверженцами его "сына" в лице C++ начались ещё до моего рождения и прекратятся разве что после смерти обоих этих языков и меня заодно. Адепты великого творения Кернигана-Ритчи до последней секунды рабочего дня готовы доказывать аксиомы приспешникам Страуструпа про вечность Си и его невероятную гибкость. Те в ответ им по-свойски советуют лучше порадоваться рабочему дню, ведь он вот-вот окажется последним – двадцать первому веку кроссплатформенный ассемблер не нужен. Распаляясь, сторонники Си приводят давно прошедшие через голову навылет миллионы тезисов "почему Си лучше C++", при этом каждый раз подчёркивая, что второй все достоинства первого растерял ещё будучи в отцовской утробе, попутно утратив лик человеческий. Обвиняемая сторона в обиде не остаётся и… а хотя постойте, о чём это я.

Я люблю Си, уважаю C++ и не переношу холивары (честно). При этом я осознаю, что в Си действительно не хватает многого, и яркий тому пример – отсутствие удобной работы с данными. В C++ эту проблему во многом решает STL и свойства самого языка. На мой студенческий взгляд, здесь особо отличается всем знакомый std::vector. Если стало интересно, как я реализовал его аналог средствами C89 – прошу под кат.

Читать полностью »