Павел Войтович

Павел Войтович

Записей (14), комментариев (0)

Главный администратор сайта.

Программист по профессии.
Высшее образование (ГГУ им. Ф. Скорины, Гомель)
Преподаватель курсов по программированию фирмы 1С.
В свободное время изучаю языки программирования и технологии.

Записи автора Павел Войтович

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

0

Источник — habrahabr.

 

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

(далее…)

Учитель гениального программиста Гены Короткевича: «Многие дети просто не хотят напрягаться»

0

Имя Геннадия Короткевича известно как в Беларуси, так и за ее пределами: многократный победитель международных школьных олимпиад по информатике, победитель турниров по программированию от таких компаний, как Google и «Яндекс». Но у каждого способного и талантливого человека должен быть учитель, ведущий к цели.

Фото: Иван Яриванович, TUT.BY

(далее…)

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

0

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

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

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

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

programming1

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

0

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

(далее…)

Работа с освещением в Unity — теория и практика

0

В видеоиграх красивое освещение в реальном времени сильно бьёт по производительности, что особенно заметно на мобильных устройствах. Таким образом, разработчики вынуждены искать методы обхода этой проблемы. Lightmapping — технология, сохраняющая информацию об освещении в текстуру, что позволяет высвободить вычислительные ресурсы под другие нужды.
В этой статье я познакомлю читателя с теорией освещения в играх, опишу процесс создания “лайтмапа” в Unity 5 и поделюсь рядом советов.

image

(далее…)

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

0

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

(далее…)

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

0

Введение


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

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

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

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

(далее…)

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

0

Как компьютеры складывают числа?

0

Наверное, нет таких людей, которые не использовали калькулятор в компьютере.

Однако кто из вас задавался вопросом: «а как же на самом деле внутри происходят вычисления». Тема эта столь интересна, сколь и сложна, и обычно для её изучения отводится специальный курс в университете (например, «Физика ЭВМ» или «Программирование микроконтроллеров»).

В этом видео будет доходчиво рассказано, каким образом компьютер вычисляет числа. Это не только познавательно, но ещё и очень интересно. Ведь складывание чисел — это только начало, компьютер способен на многое большее!

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

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 дуг (отрезков) на окружности… и та же самая задача.

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

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

RSS лента автора Павел Войтович
Вверх