Программирование

Деанонимизация программиста возможна не только через исходный код, но и через скомпилированный бинарный файл

0

Источник — habrahabr.

 

Не секрет, что многие разработчики программного обеспечения с открытым исходным кодом и не только, по разным причинам желают сохранить свою анонимность. Совсем недавно группа исследователей опубликовала работу, в которой описываются методы деанонимизации программиста по его стилю кодирования через анализ исходных кодов. Авторы утверждают, что им удалось достигнуть средней точности идентификации в 94%.

(далее…)

Какой язык программирования выбрать новичку

0

В онлайне наконец-то появился перевод крутой инфографики Which Programming Language Should I Learn First? Здесь наглядно, в виде простого алгоритма показаны варианты выбора языка программирования, с учетом того, что выбирает новичок в IT.

Главные герои инфографики — это самые популярные языки вроде Java, JavaScript, Python, Ruby, С, PHP и другие. Критериями выбора могут служить самые разные факторы, начиная от желания заработать много денег или реализовать свою идею, до любимой игрушки. Изюминка инфографики — сравнение популярных языков программирования с героями саги «Властелин колец».

Оригинал был опубликован на carlcheo.com. Перевел инфографику на русский Владимир Болиев.

Ссылка на полноразмерно изображение (Правой кнопкой мыши — открыть на новой вкладе).

programming1

Конечный автомат: теория и реализация

0

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

(далее…)

Как работает реляционная БД

0

Реляционные базы данных (РБД) используются повсюду. Они бывают самых разных видов, от маленьких и полезных SQLite до мощных Teradata. Но в то же время существует очень немного статей, объясняющих принцип действия и устройство реляционных баз данных. Да и те, что есть — довольно поверхностные, без особых подробностей. Зато по более «модным» направлениям (большие данные, NoSQL или JS) написано гораздо больше статей, причём куда более глубоких. Вероятно, такая ситуация сложилась из-за того, что реляционные БД — вещь «старая» и слишком скучная, чтобы разбирать её вне университетских программ, исследовательских работ и книг.

(далее…)

Создание искусственного интеллекта для игр — от проектирования до оптимизации

0

Введение


Статья взята с сайта Хабрахабр   —   http://habrahabr.ru/company/intel/blog/265679/

Создание искусственного интеллекта для игр

В традиционных исследованиях в области ИИ целью является создание настоящего интеллекта, хотя и искусственными средствами. В таких проектах, как Kismet Массачусетского технологического института (МТИ) делается попытка создать ИИ, способный к обучению и к социальному взаимодействию, к проявлению эмоций. На момент написания этой статьи в МТИ ведется работа над созданием ИИ, располагающего уровнем способностей маленького ребенка, и результаты этой работы весьма перспективны.

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

(далее…)

Алгоритмы поиска и сортировки: Сортировка подсчетом

0

Файловый ввод-вывод в C++. Многообразие методов

0

Недавно в олимпиадном программировании я перешёл с Pascal на C++. Это был приятный переход и я не жалею о нём, мне открылось множество стандартных решений с готовыми методами и сущностями, которые раньше приходилось реализовывать самостоятельно. Потребовалось всего лишь выучить особенности нового синтаксиса и научиться ориентироваться в стандартной библиотеке. (далее…)

Задачи по алгоритмам

0

Статья взята с сайта

http://habrahabr.ru/company/spbau/blog/254093/

 

Добрый день. На первом курсе бакалавриата Академического университета читается годовой курс алгоритмов. Каждая лекция сопровождается семинаром, на котором мы разбираем алгоритмические задачи. Практические семинары проходят в небольших группах. В этом семестре я читаю лекции и веду практику у одной из групп.

Сегодня хочу поделиться с Вами двумя задачами с этих семинаров.

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

Задача 2. На окружности даны n дуг (отрезков), нужно выбрать максимальное по размеру подмножество непересекающихся.

Первая задача — один из примеров на тему «жадные алгоритмы». Решение можно посмотреть внизу. Если коротко, предполагается решение сортировкой за O(sort+n). Здесь за sort я обозначаю время на сортировку массива длины n. Кстати, sort — необязательно nlogn (например, bucket sort, radix sort, входные данные из ограниченного диапазона).

Вторая задача имеет красивое вероятностное решение за O(sort+n). Не смотря на свою похожесть на первую, вторая задача в лоб жадностью не решается. Вернее лично мне неизвестно жадное решение, если кто-нибудь из читателей придумает и поделится, буду рад послушать. А чтобы проще было думать, я сразу опишу несколько неработающих идей, наиболее часто всплывающих при попытках решать эту задачу:

  • Пусть на окружности есть точка, не покрытая ни одним отрезком, тогда окружность можно разрезать в этой точке и получить задачу про прямую, которую мы уже умеем решать!
    Да. Но таких точек может не быть. Более того, каждая точка окружности может быть покрыта 2, 10, или даже Θ(n) отрезками
  • Разрезать окружность по точке, покрытой минимальным количеством отрезков!
    Не работает. Представьте себе 3 разбиения окружности на 10 отрезков. Всего 30 отрезков. В двух из этих «разбиений» отрезки слегка накладываются друг на друга. Нам нужно угадать третье из разбиений и точкой разреза выбрать конец одного из именно этих 10 отрезков.
  • Выгодно взять в ответ самый короткий отрезок!
    Нет. Даже на прямой уже не правда: (0,49) (50,100) (48,51)
  • Выгодно выкинуть из множества самый длинный отрезок, который кого-нибудь пересекает!
    Нет. Смотрите предыдущий пример.
  • А ещё…
    Есть много неработающих идей, остановим перечисление на уже озвученных.

 

Решения задач

Решение задачи 1.
У каждого отрезка i есть левый конец L[i] и правый конец R[i]. Отсортируем отрезки в порядке возрастания R[i]. В таком порядке будем перебирать отрезки. Очередной отрезок будем добавлять в ответ, если его левая граница больше максимума правых границ уже добавленных отрезков.

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

Для начала скажем, как задаются дуги на окружности. Пусть окружность — зацикленный отрезок [0..M), а дуги (отрезки) окружности задаются парами L[i]..R[i]. Если R[i] < L[i], отрезок проходит через точку M.
Основная идея решения — найти точку, в которой можно разрезать окружность. Вернее так: выбрать отрезок i, который мы точно возьмём в ответ. Как только такой отрезок i зафиксирован, окружность можно разрезать, например в точке R[i].

Представляя все объекты на окружности, решать задачу не очень удобно. Поэтому, используя приём «удвоение окружности», перейдём на прямую.
1. Если у какого-то отрезка R[i] < L[i], то сделаем R[i] += M.
2. Для любого отрезка L[i]..R[i] породим парный ему L[i]+M..R[i]+M

Теперь у нас есть 2n отрезков на прямой, а окружности с разрезом в точке x соответствует отрезок этой прямой [x..x+M), где 0 <= x < M.

Решение задачи 2 за O(sort + n2). Отсортировать один раз отрезки по правому концу, затем перебрать n возможных точек разреза R[i], решая для каждой задачу за O(n), так же как Задачу 1.

Решение задачи 2 за O(sort + nk), где k — размер множества-ответа на задачу. Оставим сортировку.
А сразу после сортировки воспользуемся методом двух указателей и за O(n) для каждого отрезка i насчитаем следующий отрезок next[i], который мы бы взяли нашей жадностью (жадность: L[next[i]] > R[i], из таких next[i] = min).

// Код метода двух указателей
b = 0;
for (a = 0; a < n; a++) {
  while (L[b] <= R[a]) b++; // за всё время b увеличится не более 2n раз
  next[a] = b;
}

Теперь сделаем интересное наблюдение: в зависимости от точки разреза размер полученного нами множества отличается от оптимального не более чем на 1. То есть, если мы разрезали в первой попавшейся точке и получили множество размера k, нам достаточно найти множество размера k-1, и оно точно будет оптимальным.

Решение: перебираем первый отрезок, делаем k-2 шагов вперёд с помощью ссылок next, если расстояние между самой правой и самой левой точкой меньше M, мы нашли k-1 непересекающихся дуг.

for (a = 0; a < n; a++) {
  b = a;
  for (i = 0; i < k - 2; i++) b = next[b];
  if (R[b] - L[a] < M) ; // Успех, нашли k-1 отрезков! Это a, next[a], next[next[a]] ... b
}

Решение за O(sort + n)
Возьмём раз случайную точку i = random [0..n-1]. Для каждого i за O(k) попробуем a = next[i], как в коде выше.
Поскольку, если ответ из k-1 отрезков существует, нам достаточно было попасть в какой-то один из этих k-1, то вероятность того, что за попыток мы ни разу не попали равна при стремящимся к бесконечности. Заметим, что если = Θ(1), то предыдущий алгоритм за O(nk) нас полностью устраивал. Т.е. мы получили вероятностный алгоритм, время работы которого O(sort + n). Чтобы достигнуть лучшей ошибки e-T, достаточно попробовать не , а точек, время работы соответственно будет O(sort + Tn).

Эпилог

Не всегда на определённую тему достаточно уже готовых задач, регулярно приходится придумывать новые. Только что мы наблюдали забавный эффект: берём классическую простую задачу на сортировку, заменяем «прямую» на «окружность», получаем сложную задачу на метод двух указателей и вероятностную идею. Многие красивые учебные задачи так и придумываются. Кстати, попробуйте решить ещё две задачи:
Задача 3. Даны n отрезков на прямой, выбрать максимальное по размеру подмножество отрезков такое, что каждая точка покрыта не более чем k раз (мы её только что решали для k=1).
Задача 4. Даны n дуг (отрезков) на окружности… и та же самая задача.

Ещё больше задач

Если задачи Вам понравились, по ссылкам осень и весна можно найти ещё порядка сотни задач за осенний и весенний семестр этого года. К некоторым задачам прилагается разбор.

Экзотические языки программирования

0

Многие экзотические языки придумываются для развлечения, часто они пародируют «настоящие» или являются абсурдным воплощением «серьёзных» концепций программирования. Некоторые экзотические языки нарочно ограничены, другие являются тьюринг-полными, то есть языками общего назначения. Общее свойство, присущее любому экзотическому языку — текст программы на нём понятен лишь «посвящённому», либо непонятен вообще, потому что для составления программы нужно написать программу на обычном языке. В то время, как разработчики «реальных» языков программирования стараются сделать синтаксис максимально понятным, а программирование — удобным, создатели экзотических языков обычно ставят перед собой противоположные задачи. (далее…)

Олимпиадное программирование: с чего начать?

1

В отличии от обычных программ, создаваемых программистами повседневно, класс олимпиадных задач достаточно узок, но практичен с точки критериев выявления способности участников программировать за короткий срок. Как правило, олимпиадная задача представляет собой некоторую проблему, для решения которой требуется использовать свой IQ почти на пределе, однако, сам текст программы может быть совсем незначительным и помещаться на одной странице. (далее…)

Вверх