Pull to refresh
  • by relevance
  • by date
  • by rating

Осваиваем Python. Унция 1. Типы данных.

Programming *
image
Продолжаю своё начинание. Данная статья является логическим продолжением первой. Было приятно читать ваши комментарии. Я надеялся, что данный цикл статей окажется для кого-то полезным, но совершенно не предполагал, что заинтересовавшихся будет довольно большое количество. Это заставляет относится к делу серьёзнее и ответственнее.
Без лишних слов, сразу к делу.
Читать дальше →
Total votes 54: ↑45 and ↓9 +36
Views 71K
Comments 55

Фильтр Блума

Algorithms *
И снова здравствуйте! Сегодня я поведаю о фильтре Блума — структуре данных гениальной в своей простоте. По сути, этот фильтр реализует вероятностное множество всего с двумя операциями: добавление элемента к множеству и проверка принадлежности элемента множеству. Множество вероятностное потому, что последняя операция на вопрос «принадлежит ли этот элемент множеству?» даёт ответ не в форме «да/нет», а в форме «возможно/нет».

Как фильтр это делает?
Total votes 88: ↑85 and ↓3 +82
Views 52K
Comments 36

«Aliketo» — ищет похожие вещи, и даже иногда находит, но только на английском

Search engines *
Привет, Хабр!

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

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

Естественно, основная проблема — где достать данные по множествам, ответ — получить их от самих пользователей. Но беда в том, что первые пользователи сервиса обречены на бесполезные попытки найти хоть какие-то ответы на свои запросы. Так что, всё-таки нужно где-то заранее добыть эти множества. Для английского языка, я это худо-бедно, но сделал, а вот для русского не получилось.

Если вы владеете английским, попробуйте что-нибудь поискать, другое что-нибудь непременно найдётся. Из русских множеств, сервис знает только о «хабр, лепра, дёрти» и «мир, труд, май», но ничто не мешает вам эти знания расширить. Ах да, ссылка — aliketo.com.

Весёлых выходных!

UPDATE: Вижу, что ищут одной строчкой «мир, труд», так не работает. Так работает:

мир
труд
Total votes 6: ↑5 and ↓1 +4
Views 869
Comments 11

Алгоритм поиска наименьшего по мощности покрытия конечного множества его подмножествами

Algorithms *
Sandbox
Разбирая старые бумаги наткнулся на изрядно потрёпанную тетрадь, в которой обнаружил наброски алгоритма поиска покрытия. Автор алгоритма Виктор Анатольевич Щербанов — мой учитель, под руководством которого я работал в девяностые годы прошлого столетия. Моё скромное участие в основном заключалось в том, что я предлагал в большинстве случаев неверные (а порой и просто бредовые) варианты. Что в общем-то не помешало Шефу (так мы его называли между собой) таки довести работу над алгоритмом до логического завершения. Где-то в двухтысячных годах алгоритм был опубликован в одном из институтских изданий Томска. Но думаю, что не лишним будет вспомнить его ещё раз. Собственно в память о Шефе я и решил написать этот пост. Может быть алгоритм покажется кому-то интересным или подтолкнёт на какие-то новые идеи по реализации алгоритма.
Читать дальше →
Total votes 29: ↑26 and ↓3 +23
Views 14K
Comments 11

Экран с бесконечным количеством пикселей

Mathematics *Data visualization
Translation
image

На прошлой неделе я обновил свои мониторы. Выбросил Apple Cinema Display и на их место взял 4К-мониторы от Dell. Как печатнику, мне понравился предыдущий апгрейд с чёрно-белых до grayscale-мониторов в 90-х годах. Но 4К – ещё лучше. Дисплеи высокого разрешения уже пришли на смартфоны и планшеты. Приятно, что они появляются и у ноутбуков и декстопов. Шрифты выглядят чудесно.

Хотя – хорошие шрифты выглядят чудесно. Плохие выглядят хуже – они уже не спрячутся за плохо различимыми гранями грубых пикселей. Если вы работаете с текстом – читаете, пишете, программируете, рисуете (а это охватывает чуть ли не все профессии), то апгрейд на 4К стоит того.

image

Но что есть «4К»? С лёгкой руки маркетологов, это экран размера 3840 на 2160 пикселей (3840 – это ну почти 4000). По каждой из сторон разрешение в два раза больше, чем у HDTV, то есть 1920х1080.

Спервоначалу люди говорили, что у 4К-экранов «в два раза больше пикселей». На самом деле, если вы удвоите количество пикселей линейно, это всё равно, что вы разрежете каждый пиксель как по вертикали и по горизонтали. То есть, на экране 4К в 4 раза больше пикселей, чем у HDTV.

И, что характерно, на этом останавливаться никто не собирается, на горизонте уже дисплеи 7680 х 4320, известные как 8К. С другой стороны, разрешение, воспринимаемое человеческим глазом, имеет границы. Переход на 4К заметен. На 8К – менее заметен. В какой-то момент нужно будет перестать делить пиксели.

Но что, если они не перестанут? Что, если они будут делить пиксели бесконечно? Сколько тогда пикселей будет на экране?

а) по количеству положительных целых чисел
б) меньше
в) больше

Если вам не интересна математика, тогда итог статьи такой: купите 4К-монитор. Не стоит благодарности.
Читать дальше →
Total votes 77: ↑52 and ↓25 +27
Views 54K
Comments 126

Советская школа: адресный язык программирования

ua-hosting.company corporate blog Programming *
Адресный язык программирования считается одним из первых языков программирования высокого уровня. Он был создан советским разработчиком Екатериной Логвиновной Ющенко совместно с математиком Владимиром Семеновичем Королюком в 1955 г. Конструкции этого алгоритмического языка вошли в основу современных языков программирования.

Своеобразной базой для адресного языка стали разработки члена корреспондента АН СССР Алексея Андреевича Ляпунова. Этим выдающимся математиком был создан операторный метод программирования, получивший широкое распространение на практике и оказавший сильное влияние на все последующее развитие теоретического программирования.


Екатерина Логвиновна Ющенко и Владимир Семенович Королюк

Читать дальше →
Total votes 31: ↑23 and ↓8 +15
Views 24K
Comments 4

Элементы, универсумы и регистры правил

Programming *System Analysis and Design *SQL *Algorithms *

"Дуэли запрещены в субботу, воскресенье и остальные дни недели."


Речь в статье пойдет о некоторых нюансах операции выборки данных. Эта довольно востребованная в информационных системах операция сводится фактически к определению принадлежности значений (элементов) множествам. Табличная функция, содержащая значения-множества, называется регистром правил. При наличии нескольких множеств, которым принадлежит элемент, возникает вопрос определения наиболее релевантного из них. Вопросам оценки релевантности выборки данных посвящена первая часть работы.



Забегая вперед, укажем, что основным результатом (многолетних наблюдений) является то, что в реляционных отношениях следует учитывать род атрибутов — являются ли значения атрибута отношения конкретными (элементами) или абстрактными (множествами). При этом в операции выборки данных атрибуты входной таблицы и таблицы, к которой обращаются, должны быть разных родов. Более подробно об этом — во 2-й части.


И еще одна оговорка. Там, где приходилось выбирать между простотой (понятностью) описания и его строгостью, автор старался выбирать простоту (хотя слов, в том числе не всегда понятных, все равно набралось много).

Читать дальше →
Total votes 9: ↑9 and ↓0 +9
Views 5K
Comments 13

Релевантное соединение — атрибуты конкретные и универсальные

Programming *System Analysis and Design *SQL *Algorithms *

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



Здесь же более подробно остановимся на самой операции выборки (не будет ни одной формулы!). В общем случае в данной операции могут участвовать (соединяться) не только вектор с таблицей, но и две таблицы. Операцию над таблицами, в которой используется проверка на принадлежность элемента множеству, назовем релевантным соединением. Далее рассмотрим, в чем его особенности.

Читать дальше →
Total votes 6: ↑6 and ↓0 +6
Views 2.3K
Comments 0

Понятия: множество, тип, атрибут

Semantics *System Analysis and Design *Designing and refactoring *IT Standards *Mathematics *
Математикам лень объяснять на языке обывателя, что такое действительное число. Обывателю трудно читать значки, написанные математиком, потому что их смысл для него не понятен. В итоге есть разрыв между теорией и практикой. В теории математики прекрасно знают, что такое типы объектов и что такое атрибуты, но, спускаясь к практике, мы видим, что мало, кто из практиков понимает, что это такое. Существует множество интуитивных понятий, но каждое из них скорее похоже на религиозную догму, нежели на знание. В данной статье я попытался ликвидировать пробел между математиками и прикладниками, объясняя основы теории множеств простым языком, без сложных значков. Например, вы знакомы с определением понятия атрибут? Я выстрадал его самостоятельно, потому что не мог найти формального его определения. И лишь потом Игорь Катричек прислал мне ссылку на книгу Е.Киндлера «Языки моделирования» (1979 год, перевод 1985 год), в которой дано определение атрибута:


В данной статье я дам свое, более общее определение атрибута, чтобы можно было легко его себе представить.
Читать дальше →
Total votes 14: ↑10 and ↓4 +6
Views 15K
Comments 128

10 типов структур данных, которые нужно знать + видео и упражнения

Нетология corporate blog Data Mining *Big Data *Open data *Data visualization
Recovery mode
Translation
Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.

«Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», — Линус Торвальдс, создатель Linux.

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

В этой статье я покажу вам 10 самых распространенных структур данных.
Total votes 37: ↑29 and ↓8 +21
Views 202K
Comments 31

О выборе структур данных для начинающих

Programming *Game development *
Translation
image

Часть 1. Линейные структуры


Массив


Когда вам нужен один объект, вы создаёте один объект. Когда нужно несколько объектов, тогда есть несколько вариантов на выбор. Я видел, как многие новички в коде пишут что-то типа такого:

// Таблица рекордов
int score1 = 0;
int score2 = 0;
int score3 = 0;
int score4 = 0;
int score5 = 0;

Это даёт нам значение пяти рекордов. Этот способ неплохо работает, пока вам не потребуется пятьдесят или сто объектов. Вместо создания отдельных объектов можно использовать массив.

// Таблица рекордов
const int NUM_HIGH_SCORES = 5;
int highScore[NUM_HIGH_SCORES] = {0};

Будет создан буфер из 5 элементов, вот такой:



Заметьте, что индекс массива начинается с нуля. Если в массиве пять элементов, то они будут иметь индексы от нуля до четырёх.
Читать дальше →
Total votes 42: ↑40 and ↓2 +38
Views 129K
Comments 31

О формировании последовательностей в гипотезе Коллатца ( 3n+1 )

Entertaining tasks Algorithms *Mathematics *
Меня привлекают такие задачи, как проблема Коллатца. Они просты в формулировке и отлично тренируют голову, в особенности алгоритмического мышления, что очень полезно программисту.

Формулируется задача довольно просто:
Берём любое натуральное число n. Если оно чётное, то делим его на 2, а если нечётное, то умножаем на 3 и прибавляем 1 (получаем 3n + 1). Над полученным числом выполняем те же самые действия, и так далее.

Гипотеза Коллатца заключается в том, что какое бы начальное число n мы ни взяли, рано или поздно мы получим единицу.

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

while (number > 1) {
	if (number % 2 === 0) number = number / 2;
	else number = 3 * number +1;
}
Читать дальше →
Total votes 14: ↑12 and ↓2 +10
Views 13K
Comments 10

Введение в теорию множеств

Mathematics *Popular science
Translation
image

Концепция бесконечности идеологически далека от обычной математической терминологии — ни одна другая тема не выходит за пределы математики так, что превращается из практического, аналитического инструмента в явление мифического порядка. Понятие бесконечности на короткой ноге с такими культурными темами, как религия и философия, и окутана загадочной аурой божественности.

Когда-то давным давно во всех академических дисциплинах было заложено фундаментальное убеждение — существует единственная бесконечность.

Но 1874 году довольно малоизвестный математик провёл серию революционных наблюдений, подвергавших сомнению это всеми принятое и глубоко укоренившееся убеждение. Георг Кантор в своей (теперь уже ставшей легендарной) публикации On a Property of the Collection of All Real Algebraic Numbers доказал, что множество вещественных чисел «более многочисленно», чем множество алгебраических чисел. Так он впервые показал, что существуют бесконечные множества разных размеров (не волнуйтесь — для прояснения этого мы вскоре подробно изучим его статью).
Читать дальше →
Total votes 38: ↑31 and ↓7 +24
Views 64K
Comments 26

Математики начинают укрощать «задачу о подсолнухе»

Mathematics *Popular science
Translation

Серьёзный прорыв в деле решения гипотезы 60-летней давности проливает свет на то, как при росте случайных систем в них начинает появляться порядок




Команда из математиков и специалистов по информатике, наконец, продемонстрировала прогресс в решении, на первый взгляд, простой задачи, терзавшей исследователей почти шесть десятилетий.

Эта задача, поставленная математиками Палом Эрдёшем и Ричардом Радо в 1960-м, касается того, как часто можно ожидать появления узоров, напоминающих подсолнух, в больших наборах объектах – например, в большом количестве точек, рассыпанном на плоскости. И хотя новый результат не решает гипотезу Эрдёша и Радо полностью, он продвигает понимание математиков в вопросе появления удивительно сложных структур в случайных скоплениях. Для этого в работе задачу переформулировали в терминах компьютерной функции, воспользовавшись преимуществами становящейся всё более тесной взаимосвязи между теоретической информатикой и чистой математикой.
Читать дальше →
Total votes 20: ↑19 and ↓1 +18
Views 14K
Comments 16

Математики нашли закономерность, разбираясь в том, как избежать её появления

Mathematics *Popular science
Translation

Мы, наконец, узнали, насколько большим должно быть множество чисел, чтобы в нём гарантировано содержалась закономерность под названием «многочленная прогрессия»




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

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

«Этим закономерностям присуща своего рода неразрушимость», — сказал Теренс Тао из Калифорнийского университета в Лос-Анджелесе.
Читать дальше →
Total votes 35: ↑30 and ↓5 +25
Views 12K
Comments 1

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

Entertaining tasks Mathematics *
Translation

Тяжело оценивать последовательности, не содержащие закономерностей, поэтому математики в поисках ответов на свои вопросы полагаются на простые ограничения




Если за окошком дождь, или объявлена самоизоляция, то рекомендуем вам такую простую числовую игру. Допустим, вы и я по очереди вычёркиваем числа из списка {1, 2, 3, …, 9}. Победит последний человек, вычеркнувший число так, чтобы три вычеркнутые числа не шли подряд. Играем! Вы первый.

Допустим, после четырёх ходов мы вычеркнули следующие числа:

1 2 3 4 5 6 7 8 9

Снова ваш ход. Если вы вычеркнете 4, вы проиграете, поскольку тогда вы составите последовательность из трёх чисел, 3-4-5. Также вы проиграете, вычеркнув 7, из-за последовательности 7-8-9. Безопасно будет вычеркнуть только 1, 2 или 6. Однако вне зависимости от того, какое число вы вычеркнете, я вычеркну одну из оставшихся и выиграю, не оставив вам безопасных ходов.
Читать дальше →
Total votes 15: ↑14 and ↓1 +13
Views 4.1K
Comments 7

Полнота метрического пространства индуцированного расстоянием Хаусдорфа

Mathematics *
Translation

Аннотация


Пусть дано метрическое пространство $(X, d)$. Тогда мы можем определить метрическое пространство с расстоянием Хаусдорфа $h$ на множестве $\mathcal{K}$, которое является семейством всех непустых компактных подмножеств $X$. В этой статье будет показано, что если $(X, d)$ — полное, то метрическое пространство $(\mathcal{K}, h)$ также является полным.


Читать перевод
Total votes 10: ↑5 and ↓5 0
Views 3.5K
Comments 11

Математики решили проблему классификации тридцатилетней давности

SkillFactory corporate blog Entertaining tasks Mathematics *Reading room Popular science
Translation

Как сравнить «яблоки» в «апельсины» математически? Ответив на этот вопрос, исследователи показали, что классификация групп чисел, называемых «абелевыми группами без кручения» — это предельно сложная задача. Подробностями о доказательстве делимся к старту флагманского курса по Data Science.

Читать далее
Total votes 14: ↑12 and ↓2 +10
Views 10K
Comments 8