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

Оскільки я вже згадав у попередньому дописові про третє видання книжки Кормена і компанії «Вступ до алгоритмів» (так звану 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 » » »

[flagcounter image]