Теорема, протилежна оберненій

Оскільки я вже згадав у попередньому дописові про третє видання книжки Кормена і компанії «Вступ до алгоритмів» (так звану CLRS), то напишу і тут про ненароком помічену помилку в російському перекладі книжки.

Працюючи з текстом задачі 8-7 («Лема сортування 0-1 і сортування стовпцями», сторінка 208 оригіналу) вирішив зазирнути в російський переклад, як там цю лему назвали, і тут же око вихопило дуже некоректний текст.

У перекладі російською (сторінка 238) є такі слова: «докажем 0-1-лемму сортировки путём доказательства обратной к ней». Але так не буває. Ніколи-ніколи-ніколи доведення оберненого твердження не доводить пряме. Якщо істинне як пряме твердження, так і обернене, то частини тверджень еквівалентні, тобто (А⇒Б ∧ Б⇒А) ⇒ (А⇔Б). Але шляхом доведення Б⇒А неможливо довести А⇒Б.

І в оригіналі було: «prove the 0-1 sorting lemma by proving its contrapositive»

Контрапозитивне твердження (протиставлення) це протилежне оберненому (або обернене протилежному, що те ж саме), тобто (А⇒Б) ⇔ (¬Б⇒¬А) і саме ¬Б⇒¬А можна довести для доведення А⇒Б (що і зроблено далі по тексту).

Цікаво, скільки ще таких неточностей у цьому перекладі з англійської на російську? І зрозуміло, чому я проти таких подвійних перекладів навіть у «технічних» текстах.

Scratch і двійкове дерево пошуку

З різних міркувань вирішив прослухати курс CS50 на «Прометеусі» (саме українською).
Перший тиждень там Scratch. Завдання без оцінки, просто щоб погралися, хоча деякі формальні вимоги є (не менше двох спрайтів і трьох скриптів чи щось таке — насправді дуже легкі обмеження).
Ну я й вирішив таки побавитися. Озброївся CLRS і зробив побудову та центрований обхід двійкового дерева пошуку з випадкової перестановки чисел 1–10:

Враження від Scratch » » »

Пінгвінятко Лінукс

Пінгвінятко Лінукс, яке вишивалося донькою, губилося, вишивалося наново, потім десь лежало, потім знайшлося — нарешті отримало рамку і постійне місце на стіні.

Таки економимо резистори?

Різке подорожчання пасивних компонентів — то, я так розумію, мова про великий опт, бо у роздріб ціни виросли набагато більше. В умовах законтрактованості партій практично на рік вперед «трошки» і «прямо зараз» коштує грошей кожне окремо.

Допис про економію резисторів отримав нове звучання?

Універсальний gcc-avr.mak

У зв’язку з описаною раніше помилкою avr-ld та методом боротьби з нею мене спитали про той «універсальний» файл gcc-avr.mak, яким я користуюся у всіх проектах. «Нічого воєнного», це просто файл, у який зібрано команди, які без змін переходили б з проекту в проект шляхом копіювання (і наступного редагування) Makefile від попереднього проекту 😉

Тепер файл gcc-avr.mak підключається до Makefile проекту командою include. Так само, як і подібний мейк-файл для роботи з програматором avreal — avreal.mak. Файл для проекту тепер короткий, містить лише головні налаштування. Легше знайти потрібне, важче поламати те, що вже перевірене.

Повернімося тепер до цього універсального мейк-файлу для avr-gcc і до згаданої помилки в avr-ld.

Окрім іншого, на початку gcc-avr.mak здійснюється налаштування шляхів до програм, використовуваних при компіляції. Виглядає це так (нумерація рядків відповідає файлу, доданому у прикріплений архів).

40
41
42
43
44
45
46
47
48
49
# Set default toolchain prefix if it does not defind in environment or project makefile
TOOL ?= avr-

# Set tool names
CC  := $(TOOL)gcc
AS  := $(TOOL)gcc -x assembler-with-cpp
BIN := $(TOOL)objcopy
OBJCOPY := $(TOOL)objcopy
OBJDUMP := $(TOOL)objdump
SIZE    := $(TOOL)size

Читати далі » » »

Attached Files:

Випалювач з ЧПК

Ось дивіться, яку цікавезну штуку я надибав — випалювач з числовим програмним керуванням.

Arduino Nano, трохи іншої електроніки плюс механіка; «великий» комп’ютер або OrangePi Zero. Прошивка ардуінки як ардуінівський скетч і зроблена. А ще Qt-шні програми — для OrangePi і для Linux/Windows десктопів.

Опис у блозі автора (там і посилання на GitHub):

І все це там, де найближча «Нова пошта» за 25 кілометрів. Але у автора «Випалювача» девіз — «Зробити можна все, головне мати терпіння й бажання». І у нього є і перше, і друге.

Саморобний дозиметр

Той саморобний дозиметр, фото якого було у попередньому дописові спогадів про аварію 1986 року.
Я таки наважився його розібрати і сфотографувати нутрощі. Нічого не розсипалося і є шанси зібрати назад 😉

Дозиметр зібрано в корпусі від слухового апарата. Штатний відсік батарейок випиляно і туди вставлено 9-вольтову.
Саморобний дозиметр 1986 (1)
Подивитися більше фото » » »

Чорнобиль — багатьом є що згадати

Вийшло так, що 26 квітня 1986 року, в суботу вранці, мені конче треба було дістатися до університетського 12-го гуртожитка, щоб вже звідти з дружиною їхати на вокзал.
Так-так, я мав «койкомєсто» у заводському гуртожитку в Броварах, дружина те ж саме у студенстькому гуртожитку в Києві, ні там, ні там кімнату не давали. Мене у студентський не пускали, бо вже не був студентом, а дружині в Броварах… Та там мене, «молодого спеціаліста», кілька місяців не хотіли прописувати, «у тебе дружина в Києві прописана!» (ага, по студентському гуртожитку «до 30 червня»), куди вже окрему кімнату. Але то вже з іншої категорії спогадів.

Ну так от, квитки на поїзд з Києва на Полтаву вже давно були куплені. У мене була жменя відгулів за нічні виклики на завод, дружині у деканаті теж легко дали дозвіл «погуляти», тому повернутися до Києва ми мали аж 10 чи 11 травня. Але я ледь вибрався з Броварів до Києва, бо раптом кудись поділися всі автобуси. Їх і так на маршрутах було по два-три, інтервал руху до пів години. Коли якийсь ламався, то ходили ще рідше. Але після довгого очікування люди почали турбуватися і тут хтось відкілясь приніс звістку — «всі автобуси забрали на евакуацію». Куди, чому — незрозуміло, десь аварія, вибух, називалися різні версії. Так нічого конкретного і не знаючи, 26 ввечері ми поїхали і найтяжчі дні були у безпечному місці. Коли ж повернулися назад, то вже більш-менш було зрозуміло, що берегтися треба сильно. Хусточка-шапочка, в пилюку не лізти, повітря зволожувати, підлогу мити, самим в душ і так далі.
А в кінці травня я вже паяв дозиметра » » »

ECC і HW parity

Знову згадую Лиса з Маленького принца, пора вже тег «Світ недосконалий» на його честь заводити.

STM32F0 (і не лише, але я зараз Cortex-M0 дивлюся) — є апаратний контроль парності в оперативній пам’яті.

STM32L0 — є контроль і виправлення помилок (ECC) у флеші та EEPROM.

А от щоб разом, так ні.
І, до речі, STM32F0 має переривання по збою оперативної пам’яті, а STM32L0 не має переривань від свого блоку ECC. Хоча переривання «все виправлено, але збій був» було б дуже корисним для раннього попередження про можливі відмови.

p.s. Ще цікава штука на цю тему є в ATtiny41x/81x, апаратна перевірка флеша по CRC16.

Падіння напруги на кабелі

Стало цікаво, як спадає напруга на кабелі, коли навантаження не зібрано все в одній точці на кінці, а розподілено рівномірно. Скажімо, декілька десятків споживачів із приблизно однаковим споживанням на приблизно рівних відстанях. Спочатку напруга спадатиме швидше, бо підключено більше споживачів, потім, ближче до кінця кабелю, швидкість спадання зменшиться. Але якими будуть загальні втрати напруги?
От якщо на кінці кабелю із загальним опором R висить навантаження зі споживанням струму I, то напруга впаде на величину IR. А що буде при рівномірному підключенні?
Дивится формули і графіки » » »

[flagcounter image]