Побудова діаграми Вороного методом 'розділяй і володарюй'. Релаксація Ллойда

image
Нещодавно, на хабрахабре була опублікована стаття, цілком і повністю присвячена діаграм Вороного. У статті автор детально описує алгоритм Форчуна, що застосовується для побудови Діаграми Вороного за O(n*log(n)). Варто зазначити, що опис цього алгоритму не раз з'являлося в рунеті, в той час як про інших алгоритмах(з тієї ж асимптотикой) розказано рівним рахунком нічого. Дана стаття виправляє це непорозуміння, а також є відмінним доповненням до вже опублікованим раніше матеріалом.
Нижче я розповім про алгоритмі 'розділяй і володарюй' побудови діаграми Вороного за O(n*log(n)), а також, ґрунтуючись на своєму практичному досвіді, про по-справжньому крутих штуках, в яких це стосується. Взагалі, алгоритми типу 'розділяй і володарюй' є свого роду класикою програмування(думаю, про сортування даних методом чув кожен програміст), добре параллелятся і легко читаються(якщо, звичайно, знати основну ідею алгоритму).

Читати далі →

Чому компанії так наполегливо хочуть мати Fullstack розробників?

image
Тут вже написано безліч статей про те, хто такий Fullstack, в чому його плюси і мінуси, в яких проектах є сенс наймати таких розробників, а де — ні. Я буду виходити з думки, що ви розумієте, що таке Fullstack і з чим його їдять.

Думка, яку я хотів би висловити полягає в наступному — «Чому, навіть великі аутсорсингові і продуктові компанії, хочуть наймати Fullstack і/або розвивати своїх співробітників в цьому напрямку?».

Читати далі →

Переклад підручника по алгоритмах

  
 
Радий повідомити, що вийшов переклад відмінного підручника Дасгупта, Пападімітріу, Вазірані «Алгоритми», над яким я працював останні кілька років. У книзі багато алгоритми пояснені набагато коротше і простіше, ніж в інших підручниках: з одного боку, без зайвого формалізується, з іншого — без втрати математичної строгості. Відкрийте книгу на якому-небудь відомому вам алгоритмі і переконаєтеся в цьому. =)
 
Загалом, угощайтесь: друкований варіант перекладу , електронний варіант перекладу (PDF) , друкований варіант оригіналу , електронний варіант оригіналу (PDF) .
 
Читати далі →