Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)
Алгоритмы, дискретная математика и пр.'s Journal [Most Recent Entries][Calendar View] [Friends]
Below are the 20 most recent journal entries recorded inАлгоритмы, дискретная математика и пр.'s LiveJournal:
[ << Previous 20 ]
| Thursday, December 5th, 2013 | |
|---|---|
| _11:31 am_[potan] |
Поиск консенсуса. Не могу найти подходящий алгоритм для следующей задачи.Есть неизвестная строка. И есть много вариантов испорченной строки (процентов на 80). Портится строка заменами, удалениями и, реже, вставками. Получение новой испорченной строки операция дорогая, но не запредельно.Надо с достаточным правдоподобием восстановить исходную строку.Так как новых строк мы можем получать много, хочется иметь алгоритм, работающий на константной памяти.Основное пожелание, что бы алгоритм был простой (хочу быстро его реализовать на малознакомой платформе что бы проверить некоторые идеи). Есть готовые функции для выравнивания двух строк, вычисление расстояния редактирования.Посоветуйте, где такой искать? (16 Comments |Comment on this) |
| Sunday, October 20th, 2013 | |
| _10:26 am_[antilamer] |
Быстрые реализации приоритетной очереди Интересно, какие есть быстрые на практике реализации приоритетной очереди, кроме классической двоичной кучи.Особенно интересует производительность decrease-key, и, крайне желательно, малое потребление памяти.Нашёл пару статей:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16.6563&rep=rep1&type=pdf, ftp://ftp.cs.utexas.edu/pub/techreports/honor_theses/cs-07-34-roche.pdf - исследуют несколько видов куч на практике, и у них вроде получается, что "sequence heaps" и "4-ary heaps" быстрее, чем двоичные кучи.Ещё нашёл http://stackoverflow.com/questions/6531543/efficient-implementation-of-binary-heapsИ про cache-oblivious кучи: http://queue.acm.org/detail.cfm?id=1814327Ещё один обзор видов куч: http://www.cs.au.dk/~gerth/papers/ianfest13.pdfБыло бы здорово, если бы кто-нибудь поделился практическим опытом. (12 Comments |Comment on this) |
| Friday, September 27th, 2013 | |
| _8:29 pm_[xcontcom] |
Фрактал Герасимова |
| Tuesday, June 18th, 2013 | |
| _1:53 am_[rootkid] |
логические операции над матрицами Всем привет, подскажите, пожалуйста, есть ли такая вещь как subj? eg:0 1 01 0 00 1 0&0 1 01 1 01 0 0=0 1 01 0 00 0 0т.е.A&B=Cинтересует более-менее академический подход и алгоритмы луче полного перебора, спасибо. (37 Comments |Comment on this) |
| Tuesday, April 9th, 2013 | |
| _4:39 pm_[atlaskard] |
Developers wanted! Краткий пост про работу, вернее - краткое описание вакансии (полагаю, данный пост может быть интересен некоторым из участников сообщества):Оригинал взят у  atlaskard в К нам в команду!Всем привет!В связи с ростом числа проектов мы расширяем нашу комнду. Сейчас нам как никогда, нужны программисты C++. Но не "просто программисты", а специалисты в области крипторгафии!. Вкратце о нас:Учитывая направление нашей деятельности, представить нашу компанию "во всех красках" не имею права. Надеюсь, вот такого краткого описания на этапе первичного знакомства Вам будет достаточно:Мы существуем с 2003 года.Наша деятельность связана с защитой информации, основные направления - это:- разработка программного обеспечения;- создание программно-аппаратных комплексов;- разработка микропроцессорной техники;- исследовательская деятельность.Заказчиками наших проектов выступают различные государственные организации, включая ФГУП "Гознак", Минздравсоцразвития России, ОАО "Универсальная электронная карта" и др.**Вкратце про проекты:**Могу сказать только одно - скучно не бывает!Вкратце про наш коллектив: Коллектив (пока) не очень большой, в связи с этим каждый сотрудник на виду ("за заслуги перед Отечеством" наградим каждого, кто себя проявит). В команде работают как молодые специалисты, так и сотрудники с солидным опытом работы. Команда дружная, сплоченная, "пополнеие в строю" воспринимает исключительно позитивно.В отделе разработки есть несколько групп, каждая из которых отвечает за определенное направление (например, группа Тестирования-Документирования отвечает, что очевидно, за тестирование продукта и создание тех. документации).Наши руководители - это вполне реальные люди, с которыми можно в любой момент обсудить какие-то рабочие процессы/вопросы/условия, а не записываться на прием за месяц через секретаря.**Вкратце про условия:**Комфортные:- График: полный рабочий день, но конкретное время прихода/ухода можно соглсовать с руководителем (кому-то комфортнее работать с 8.00, а кому-то - с 11.00).- Уютный офис рядом с метро (5-7 минут пешком от м. ВДНХ)- Зарплата - с каждым обсуждаем отдельно (все зависит от опыта/уникальных навыков), безусловно, принимая во внимание рынок и запросы кандидата- Обучение: при поступлении от сотруднка заявки на обучение, Компания, рассмотрев заявку, при необходимости направляет сотрудника на прохождение определенного курса/семинара.В целом это все, что могу про нас написать (остальное доступно только при личной встрече). Ниже направляю формальное описание одной из наших вакансий, буду Вам очень благодарна за отклик или перепост:Программист/Ведущий программист C/C++ **Требования (обязательно):• Высшее техническое/математическое образование• Опыт разработки на С/С++ от 5 лет• Знания в области защиты информации и криптографии, опыт разработки соответствующего ПО• Английский язык – базовый• Личностные качества: внимание к деталям, ответственность, стрессоустойчивостьТребования (желательно):**• Опыт разработки на C#Обязанности:• Разработка и сопровождение программных продуктов компанииУсловия• Участие в интересных и сложных проектах• Самореализация. Дружный, сплоченный коллектив единомышленников• Заработная плата – от 100 000 – 120 000 рублей (по итогам собеседования)• Бонусная система• ДМС• Строгое соблюдение всех норм Трудового кодекса• Комфортный офис в 5-ти минутах пешком от м. ВДНХКонтакты для связи:Ксения Шауро7 495 620 57 21resume@atlas-kard.ru или shauro@atlas-kard.ruPS: Молодым криптографам (без опыта работы) мы также рады. Условия те же, за исключением зарплаты (будем обсуждать при встрече). (3 Comments |Comment on this) |
| Tuesday, February 12th, 2013 | |
| _5:29 pm_[ivanbliznets] | Начало весеннего семестра в Computer Science клубе при ПОМИ РАН В CS клубе при ПОМИ РАН первое занятие нового семестра пройдет 21 февраля.Ниже список курсов, читаемых в этом семестре:* Николай Вяххи (СПб АУ РАН), Алгоритмы в биоинформатикеначало: 24.02.2013, 11:15http://compsciclub.ru/courses/algorithmsbioinformatics* Дмитрий Ицыксон (ПОМИ РАН), Сложность вычислений и основы криптографииначало: 21.02.2013, 18:30http://compsciclub.ru/courses/complexitycryptography* Илья Кацев (СПб ЭМИ РАН/Яндекс), Теория игрначало: 24.02.2013, 13:00http://compsciclub.ru/courses/gametheory* Computer Science семинарначало: 24.02.2013, 15:35http://compsciclub.ru/courses/seminar2013springВход свободный, приглашаются все желающие.Расскажите, пожалуйста, о курсах заинтересованным друзьям.Адрес: наб. реки Фонтанки, 27.Подробност http://compsciclub.ru. (Comment on this) |
| Sunday, January 20th, 2013 | |
| _8:15 pm_[alien_nostromo] |
NAGLIB Может быть, у кого-либо есть живая ссылка на библиотеку NAGLIB (интересуют исходники)?На ихнем сайте вроде как не разживешься для халявного пользования.PS. Можно старую, у меня есть от 89 г., но на ленте для СМ-ки - считать негде. (5 Comments |Comment on this) |
| Tuesday, December 25th, 2012 | |
| _4:28 pm_[sobol_noobz] |
Олимпиады для поступающих в магистратуру Друзья, здравствуйте!Хотел вам сообщить, что с 1 декабря открылась регистрация на олимпиады для студентов и желающих поступить в магистратуру Национального исследовательского университета "Высшая школа экономики".Среди технических направлений присутствуют олимпиады:по системной и программной инженериипо прикладной математике и информатикепо математикепо информационным технологиям (сети, информационные системы, создание аппаратуры для космической техники)по электронике (инжиниринг, наноиндустрия, биомедицина)Со всем списком олимпиад можно ознакомится вот тут.Регистрация и участие -- свободное и бесплатное для всех.Зарегистрироваться можно вот тут. (Comment on this) |
| Tuesday, October 9th, 2012 | |
| _5:09 pm_[mrsotvertka] |
Осенний Форум Технологий: фокус на веб-разработку Мы приглашаем вас на главное технологическое событие осени — Форум Технологий Mail.Ru Group.Что будет: 24 доклада, три потока, гигабайты информации о самых актуальных трендах и веб-технологиях. На Форуме российские и зарубежные специалисты будут говорить о том, как использовать самые свежие и горячие разработки в собственных проектах.Выступающие: эксперты Mail.Ru Group, Google, Opera Software, Ajax.org и других крупнейших IT-компаний.( Collapse ) (Comment on this) |
| Tuesday, September 4th, 2012 | |
| _4:41 pm_[kucheryavenko] |
Книги математические Посоветуете книги по математике для взрослого человека 30ти годков) давно изучавшего школьную и высшую математику.Для вспомнить и ну дальше чтобы интерес остался или проснулся и вспыхнул с новой силой).Тематика подходит любая.Если конечно есть что то типа "Вы, конечно, шутите, мистер Фейнман!" будет очень замечательно. Или например обзор всей школьной программы для начала)Заранее благодарю. (12 Comments |Comment on this) |
| Friday, July 13th, 2012 | |
| _10:31 am_[word_sparrow] |
Всероссийская молодежная конференция «Математическое моделирование..." 29 июня в РГСУ состоялась Всероссийская молодежная конференция «Математическое моделирование в проблемах рационального природопользования». Организаторами конференции выступили Министерство образования и науки Российской Федерации и Российский государственный социальный университет.В состав Оргкомитета вошли: Г.С. Жукова (РГСУ), А.А. Нечаев (МГУ), Е.В. Комарова (РГСУ), Н.П. Третьяков (РГСУ), Д.Н. Скрипка (РГСУ). В рамках работы Всероссийская молодежной конференции был рассмотрен круг теоретических и практических вопросов, касающихся математического моделирования в проблемах рационального природопользования. Среди тем докладов были такие как: «Методы принятия решения с учетом экологических ограничений» (М.Г. Дмитриев, д.ф.-м.н., профессор, главный научный сотрудник института системного анализа РАН), «Разработка способов и алгоритмов поддержки принятия экологических решений на основе метода анализа иерархий» (Д.А. Скрипова, выпускник кафедры прикладной математики РГСУ, магистр ПМИ), «Математическое моделирование биологической эволюции» (Н.П. Третьяков, к.ф.-м.н., доцент кафедры прикладной математики РГСУ). Также в рамках конференции состоялись дискуссии в формате «круглого стола»: «Вопросы преподавания элементов математического моделирования в курсах экологической направленности» (модератор - д.ф.-м.н., профессор Г.С. Жукова), и «Математическое моделирование в естественных науках и науках о живом» (модератор - д.ф.-м.н., профессор М.Г. Дмитриев). (Comment on this) |
| Friday, June 8th, 2012 | |
| _2:05 am_[mrsotvertka] |
Третий квалификационный раунд Russian Code Cup 2012 состоится 10 июня Третий квалификационный раунд - последняя возможность принять участие во второй ежегодной российской олимпиаде по программированию Russian Code Cup 2012 - пройдет на сайте мероприятия 10 июня, с 11:00 до 13:00 по московскому времени. Для участия требуется регистрация на сайте – она будет открыта до 10:30 10 июня.( Collapse ) (Comment on this) |
| Wednesday, April 18th, 2012 | |
| _2:30 pm_[anubis89] |
КЛАДР. Всем доброго времени суток.На работе дали задание перестроить список адресов, как для существующих так и для свеже созданных.Теперь все будет работать по КЛАДР..С самим кладром и его иерархичностью, я разобрался я не понимаю, как реализовать это с точки зрения программиста.Почитал интернет, там сколько людей, столько и мнений.Может кто то с этим уже сталкивался, у кого то есть мысли и готовое решение.Спасибо. (5 Comments |Comment on this) |
| Tuesday, April 3rd, 2012 | |
| _7:23 pm_[coshmos] |
Быстрая сортировка Всем привет. Выполняю домашнее задание (да, наверное глупо сюда постить, но всё же). Так вот, нужно написать быструю сортировку (quicksort) и прогнать через неё массив данных (текстовый файл с числами) и посчитать количество произведённых сравнений. Вся проблема в том, что, когда основой выбирается самый левый элемент, то всё считается хорошо, а когда какой-либо другой, то всё плохо. Вот код: public static void qsort(int[] aToSort, int left, int right) { numberOfComparisons += right - left; int i = left, j = right, c = i, s = 0; int m = aToSort[left]; do { if (aToSort[i] < m) { s = aToSort[c]; aToSort[c] = aToSort[i]; aToSort[i] = s; c++; } i++; } while (i < j); s = aToSort[c]; aToSort[c] = aToSort[left]; aToSort[left] = s; if (c + 1 < j) qsort(aToSort, c + 1, j); if (c-1 > left) qsort(aToSort, left, c-1); }* This source code was highlighted with Source Code Highlighter.А это некоторые кейсы: [1, 2]First element as pivot : 1 comparisons.Last element as pivot : 1 comparisons.Median of 3 as pivot : 1 comparisons.[2, 1]First element as pivot : 1 comparisons.Last element as pivot : 1 comparisons.Median of 3 as pivot : 1 comparisons.[3, 2, 4, 1, 5]First element as pivot : 6 comparisons.Last element as pivot : 9 comparisons.Median of 3 as pivot : 6 comparisons.[3, 4, 1, 2, 5]First element as pivot : 6 comparisons.Last element as pivot : 8 comparisons.Median of 3 as pivot : 6 comparisons.[3, 2, 1, 4, 5]First element as pivot : 6 comparisons.Last element as pivot : 10 comparisons.Median of 3 as pivot : 6 comparisons.[3, 4, 5, 1, 2]First element as pivot : 6 comparisons.Last element as pivot : 7 comparisons.Median of 3 as pivot : 6 comparisons.[1, 2, 3, 4, 5]First element as pivot : 10 comparisons.Last element as pivot : 10 comparisons.Median of 3 as pivot : 6 comparisons.Я так понимаю, что при использовании в качестве опорного элемента любого, кроме самого левого, с ним необходимо что-то делать, но что? Current Mood:  apathetic (13 Comments |Comment on this) |
| Tuesday, February 7th, 2012 | |
| _12:32 pm_[sicsten] | Мысли вслух как чужой опыт сделать своим. На написание этой статьи меня вдохновило несколько примеров из жизни касающиеся массы людей, которые из воздуха пытаются сделать деньги. Эта масса частных инвесторов, программистов и других трейдеров, которые молча сидят и варятся в собственном соку, перелопачивая груду чужих полу успешных, провальных или успешных опытов игры на бирже.Первый пример это опыт двух молодых трейдеров из Москвы, автоматическая торговая система которых на соревнованиях показала несколько тысяч процентов прибыли (Лауреаты конкурса «Лучший частный инвестор 2010», организованного РТС, превратившие за три месяца 50 000 руб. в 4 млн руб.): http://finparty.ru/section/interview/record/502/.На данную статью можно посмотреть с двух точек зрения.Первая точка зрения это осознание того, что два молодых парня, приложив свои знания и трудолюбие, потратив сколько-то своего личного времени, достигли таких успехов.Вторая точка зрения это то, что РТС с помощью такого нехитрого хода пытается привлечь новых инвесторов, которые по неопытности, вдохновленные примером данных двух молодых людей вложат свои денежные средства для участия в торгах.На данной скептической ноте можно перейти к другой примечательной статье: http://www.forbes.ru/lichnye-dengi/tsennye-bumagi/17106-novye-hozyaeva-birzhi.В данной статье представляется фирма Getco (GlobalElectronicTradingCo), которая с помощью внедрения новых биржевых технологий и алгоритмов в течение года с маленькой, никому не известной компании превратилась в компанию с много миллиардными долларовыми оборотами. В данной статье также рассказывается про алгоритмы, которые без помощи и участия человека совершают миллионные операции в день. Также хотелось бы ещё обратить внимание на презентацию Кевина Слэвина: «Как алгоритмы формируют наш мир»: http://www.ted.com/talks/lang/ru/kevin_slavin_how_algorithms_shape_our_world.html.В данной презентации помимо всего упоминается Бостонская компания «Nanex», сотрудники которой, по словам Кевина Слэвина: «используют математику, магию и что-то ещё и получают доступ к данным рынка и находят, иногда, некоторые из этих алгоритмов. Когда они их находят, они их вытаскивают, и прикалывают на стену как бабочек. Они делают то, что мы всегда делали, сталкиваясь с огромным количеством данных, которые мы не понимаем. Они дают им имя и историю. … Прикол в том, что это не только на рынке. Эти вещи можно найти везде, где ни посмотри, как только научишься их искать».С помощью математиков, математики, понимания сути вещей можно найти скрытые закономерности и попробовать на этом заработать. Для этих целей необходимо создать группу единомышленников. В состав этой группы желательно чтобы входили математики, программисты, и финансовые аналитики с опытом реальных торгов на бирже.Цель создания данной группы единомышленников: без финансовых вложений (или с минимальными финансовыми вложениями), только полагаясь на свои интеллектуальные способности и затрачивая свое личное время достичь финансовых успехов на фондовых биржах.Крупные компании, которые занимаются финансовыми операциями на фондовой бирже имеют деньги на аналитиков и математиков, но также имеют риски, связанные с человеческим фактором. Математики-одиночки, программисты-одиночки либо аналитики-одиночки также имеют мало шансов, потому что такие объемы информации трудно оценить одному человеку. Причем человек-одиночка имеет однобокий взгляд на проблему, которую стоит решать. Отсутствует мозговой штурм.Отношения между участниками группы нужно отрегулировать путем принятия совместных решений по организации работы и небольшого свода, внутренних правил работы группы. Хотелось бы обсудить целесообразность создания такой группы единомышленников. (1 Comment |Comment on this) |
| Friday, February 3rd, 2012 | |
| _11:17 pm_[onery] |
Entity Resolution по русски Я начала переводить книгу John R. Talburt "Entity Resolution and Information Quality". Пересказ (это больше пересказ, чем перевод) будет публиковаться в  er_iq_ru (ER_ru оказался занят всем известной партией).Помощь, публикации других материалов и ссылок по теме Entity Resolution приветствуются.Велкам! (Comment on this) |
| Friday, December 30th, 2011 | |
| _10:18 pm_[mr_bison] |
Невычислимая величина (помогите пожалуйста полному чайнику) Для фантрассказа нужно чтоб совсем уж полную хрень не написать. А я в этой области полный и беспросветный чайник.Несколько вопросов.1) Правильно ли я понимаю, что невычислимой величиной называется число для которого принципиально не существует алгоритма который последовательно выдавал бы его цифры?2) Означает ли невычислимость некоей величины также принципиальную невозможность нахождения нескольких первых цифр данного числа?3) Если 2 верно, есть ли какой-либо способ вычислить сколько именно первых цифр невычислимой величины можно найти?4) Можно ли вычислить невычислимую величину не полностью, но со сколь угодно высокой точностью?UPD. Спасибо всем за помощь. (11 Comments |Comment on this) |
| Wednesday, November 9th, 2011 | |
| _5:22 pm_[oneq] | Сквозная нумерация независимых потоков Возможно заголовок получился неправильный, но все очень просто. Есть неограниченное количество клиентов (человек, который пользуется программой) для написания сообщений. Все похоже на форум или чат, но нет сервера, который принимает и отправляет (а значит и синхронизирует) сообщения. Нужно, чтобы общий поток имел сквозную нумерацию, чтобы:1) нельзя было изменить порядок сообщений (время появления)2) передавать сообшения целыми серями.С первым пунктов примерно понятно - нужно, чтобы сообщения отображились в том порядке, в котором были созданы, плюс-минус какое-то разумное время, но чтобы у всех участников порядок был одинаковым. Одинаковый порядок нужен для того, чтобы при запросе вновь подключившегося участника он бы мог запросить: "у меня последнее сообщение номер 1000, есть ли что-то новенькое?". Будет ли система работать (без злоумышленников), если использовать просто метку времени (хватит ли точности часов у пользователей, чтобы не было пропущенных сообщений, например). И будет ли она работать, если злоумышленник укажет меньшее время, чтобы его сообщение появилось раньше какого-либо.То есть нужна какая-то нумерация, которая привязана к уже существующим сообщениям. Сначала показалось, что можно делать хэш сообщений, которые есть у клиента и отправлять его как подпись вместе с новым сообщением, но это не снимает проблемы со "старыми" сообщениями, когда можно посчитать хэш только десяти первых сообщений вместо тысячи(текущего количества).Мне кажется, что эта проблема уже где-то была решена. Вдруг кто-то знает, как такое можно сделать? (53 Comments |Comment on this) |
| Thursday, November 3rd, 2011 | |
| _2:04 am_[rom777] |
Симметричная подматрица с максимальной суммой элементов Уважаемые, Столкнулся с такой задачей. Дана симметричная матрица размерности N; требуется найти в ней симметричную же подматрицу (не обязательно со смежными строками/столбцами) размерности К с наибольшей суммой элементов.Ближайшее, что удалось найти, это варианты на тему http://en.wikipedia.org/wiki/Maximum_subarray_problem , но это не то... (2 Comments |Comment on this) |
| Wednesday, November 2nd, 2011 | |
| _3:59 pm_[potan] |
Количество связанных графов. Посчитал точное количество связанных графов на данном множестве вершин. Непонятно зачем, но вдруг кому пригодится.( Collapse ) (7 Comments |Comment on this) |
[ << Previous 20 ]