От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1
Часть 2

Логарифмы

Если вы знаете, что такое логарифмы, то можете спокойно пропустить этот раздел. Глава предназначается тем, кто незнаком с данным понятием или пользуется им настолько редко, что уже забыл что там к чему. Логарифмы важны, поскольку они очень часто встречаются при анализе сложности. Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. На рисунке справа зелёный график — линейная функция f(n) = n, красный — f(n) = sqrt(n), а наименее быстро возрастающий — f(n) = log(n). Далее: подобно тому, как взятие квадратного корня является операцией, обратной возведению в квадрат, логарифм — обратная операция возведению чего-либо в степень.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Опубликовано ранее:
Часть 1

Сложность

Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчёта инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее). Одиночный цикл от 1 до n, даёт асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.

От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.

Введение

Многие современные программисты, пишущие классные и широко распространённые программы, имеют крайне смутное представление о теоретической информатике. Это не мешает им оставаться прекрасными творческими специалистами, и мы благодарны за то, что они создают.

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

Когда речь заходит об эффективных алгоритмах сортировок, эрудированный хабраюзер сразу же припомнит неувядаемую «быструю сортировку», новомодную «сортировку Тима», легендарную «сортировку слиянием» и даже мудрёную «интроспективную сортировку».

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

Предисловие

Как-то в гостях мне в руки попалась головоломка, в которой из 25 одинаковых фигурок требовалось собрать куб. Я провозился с ней почти весь вечер, и как можно догадаться, абсолютно безрезультатно. Тем не менее, я не мог сдаться просто так.

Не можешь сам — заставь компьютер. Сказано — сделано. В результате написанному по наитию алгоритму пришлось работать всю ночь, чтобы найти все 4 уникальных решения. В процессе гугления решений для сравнения, я нашёл программу Burr Tools, которая справилась с этой задачей за 3 минуты на моём ноутбуке.

Такая разница в скорости заставила меня разобраться, как решается эта задача и ещё целый класс подобных.

Для начала, хочу поздравить всех хабровчан с днем программиста!
О чем же писать в этот день, как не об игре, которая позволит воспитать из вашего ребенка юного Стива Джобса или Аду Лавлейс.

Robot Turtles — это игра от программиста из Google Дэна Шапиро.
Она предназначена для детей от трех до восьми лет, и в неё очень легко научиться играть. Ваши детки даже не будут подозревать, что в течение игры они будут строить настоящие алгоритмы и изучать основы программирования.

Приветствую разработчиков программного обеспечения, которые интересуются образованием и повышением квалификации, хотят изучить что-то новое или проверить свои силы с помощью сертификации.

Онлайн-академия Microsoft Virtual Academy еще в начале года объявила о первом миллионе участников из 100 стран мира. Сегодня мы приветствуем новых участников и приглашаем вас присоединиться к нашему движению. С помощью курсов и тестирования MVA вы сможете быстро изучить новые технологии и проверить свои знания с помощью тестов, получив сертификат. И все это совершенно бесплатно! Вы можете найти подробности о академии MVA в этой статье на Хабре.

Мне приятно представить вам несколько новых курсов MVA, которые были специально опубликованы для русскоязычных разработчиков:

• Разработка приложений для Windows 8 на XAML/C#
• Разработка приложений для Windows 8 на HTML/JS
• Дизайн приложений для Windows 8
• Новые возможности Windows Phone 8 для разработчика
• Расширенные возможности разработки для Windows Phone 8
• Создание облачных веб-приложений в Windows Azure Web Sites
• Разработка приложений Windows 8 с использованием Windows Azure Mobile Services
• HPC-кластеры по запросу в Windows Azure

Буквально пару часов назад в Санкт-Петербурге завершился открытый чемпионат по программированию Яндекс.Алгоритм 2013. Состязания состояли из нескольких онлайн-раундов по 100 минут, за победу боролись более 3000 программистов из 84 стран. По результатам трёх отборочных раундов в финал вышли 25 лучших.



Финалисты должны были решить шесть алгоритмических задач за 100 минут. Первое место занял недавний победитель ACM ICPC 2013 в составе команды НИУ ИТМО Геннадий Короткевич (tourist), который набрал меньше всего штрафного времени. Второе место досталось выпускнику НИУ ИТМО Евгению Капуну (eatmore). Третье место занял представитель Тайваня Ши Бисюнь.

В подготовке заданий для чемпионата участвовали специалисты из нескольких стран: России, Беларуси, Польши и Японии. Главными составителями задач стали разработчики минского офиса Яндекса (как и все сотрудники компании, к участию в состязаниях они не допускались). Мы попросили всех авторов разобрать задания, которые они подготовили для участников Яндекс.Алгоритма. Кстати, все задачи не удалось решить никому, лучший результат — три решённые задачи — показали только три участника.

Отличный подход к информационной безопасности показала Американская администрация экономического развития (The Commerce Department's Economic Development Administration).

Вирусная атака нанесла этому ведомству урон в $2.7 млн. долларов, что составило практически половину его бюджета, но весь сок в подробностях.

Несколько компьютеров организации были заражены вирусами. Команда реагирования на инциденты провела анализ трафика и пришли к выводу, что заражены 146 из 250 компьютеров. Как потом оказалось, они проанализировали неверные данные и проблема затронула всего два компьютера, на самом деле.

Но проблема предстала перед ними серьезной — это ж кибер атака! Надо срочно защищаться! Как результат, было принято решение о физическом уничтожении «инфицированных» компьютеров, включая (!) мышки, клавиатуры, принтеры, видеокамеры, и даже телевизоров (на что потрачено $170 тыс долларов), и полной смене IT-инфраструктуры.

Примерно полтора года назад компания, в которой я работал, приняла решение начать образовательный проект: готовить будущих программистов со студенческой и даже школьной скамьи. Решение было вызвано как нехваткой квалифицированных программистов в нашем регионе, так и тем, что приходящих выпускников приходится очень многому доучивать – получаемое в вузе образование не полностью отвечает современным реалиям индустрии разработки ПО. Проект взаимовыгодный как для студентов, которые получают возможность познакомиться с промышленным программированием на практике, так и для компании, которая получит через несколько лет квалифицированных специалистов.

Но еще интереснее оказалась часть проекта, ориентированная на работу со школьниками. Я принимаю непосредственное участие именно в этой части, поэтому хочу рассказать о ней.

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



Итак, кто заинтересовался — прошу под кат.

Программное обеспечение проникает во все щели человеческого общества. Мы узнаем погоду через интернет, а не через обычный градусник за окном. Мы едем по новому адресу с навигатором, а не ищем квадрат G7 на странице 59. Мы включаем RunKeeper, когда катаемся на велосипеде, чтобы узнать среднюю скорость и похвастаться в твиттере. Мы используем софт каждый день. Наверное, бОльшую часть жизни мы уже проводим в обнимку с любимыми гаджетами и программным обеспечением, а не с любимым человеком.

Проблема в том, что никто не знает, как на самом деле писать классный софт быстро и правильно. Waterfall благополучно скончался на рубеже веков, а новые методы разработки (agile) пока не могут решить фундаментальные проблемы.

1. Выучить новый язык программирования

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

Среди языков программирования отличный познавательный эффект и наверстывание опыта дают: Lisp (или Scheme), Форт, PostScript или Factor (стековые языки программирования), Haskell (строго типизированный, чистый функциональный язык) либо OCaml (объектно-ориентированный язык функционального программирования), Пролог (логическое программирование), Erlang (отличные паралельные вычисления).

От переводчика: Я думаю многие читали статью Rey Bango — What to Read to Get Up to Speed in JavaScript, но до хабра обсуждение так и не докатилось. Предлагаю закрыть этот пробел и поговорить о хороших книгах, блогах, тренингах и конференциях, посвященных в первую очередь клиентскому JavaScript и клиентской веб-разработке. Чтобы не копипастить оформляю статью в виде перевода.

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

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

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

Я опишу одну известную и простую методику, с помощью которой вы сможете достигать свои цели. Только это. Не гарантирую, что это будет быстро или дешево или эффективно, но могу гарантировать одно — цель будет достигнута.

Методика общеизвестна и называется она — планирование.

Если вы скажете — «а, знаю, пробовал я эти методики планирования — не помогают они, никаких гарантий они не дают, да и вообще — бесполезы» — я нисколько не удивлюсь. Отвечу так:
«Вы просто не умеете их готовить»