Thursday, December 20, 2012
«Машина», которая видит всё
По наводке блога Дневник кризиса.
Ниже есть продолжение.
За вами наблюдают. Правительство разработало секретную систему – «Машину», которая следит за вами ежедневно и ежечасно. Я знаю об этом, потому что я ее создал. Я спроектировал «Машину» для борьбы с терроризмом, но она видит все. Преступления, связанные с обычными людьми. Такими, как вы.
Ниже есть продолжение.
Этими словами начинается вышедший в 2011 году американский сериал Джонатана Нолана «Person of Interest». Однако этот текст не про кино, а про «Машину», о которой рассказывается в фильме.http://slon.ru/future/za_vami_nablyudayut_pryamo_seychas_i_eto_ne_kino-865379.xhtml
Подавляющее большинство смотревших фильм считает историю про «Машину» чистой выдумкой. Более осведомленные вспоминают в этой связи «Эшелон» – древний проект тотальной прослушки всех каналов коммуникации с выделением ключевых слов, негласно запущенный в прошлом веке в США, а потом повторенный многими странами...
...
«Машина» из фильма «Person of Interest» существует. И зовут ее Palantir – система для анализа и визуализации данных, разработанная калифорнийской компанией Palantir Technologies (один из ее главных инвесторов – Питер Тиль, основатель PayPal и первый инвестор Facebook). Чтобы убедиться в том, что именно система Palantir стала прообразом «Машины», достаточно сравнить описание того, как работает «Машина», с описанием того, как работает система Palantir.
Вот как рассказывается о том, как работает «Машина», в фильме «Person of Interest» (далее текст из фильма):
«Гордон Курцвайль, сотрудник разведки Минобороны США, имеющий высочайший уровень секретности и уже 20 лет работавший на ФБР, готовился завершить операцию по продаже 12 кг урана иранскому правительству. Операция была так тщательно и искусно законспирирована, что ни одна из спецслужб США не имела ни малейшей информации о ней, а сам Курцвайль был абсолютно вне подозрений. Выявить предателя и тем самым предотвратить передачу урана смогли не федеральные агенты, а «Машина» – суперпрограмма, разработанная компьютерным гением, не работавшим ни на одну из спецслужб США.
«Машина» выявила, что Гордон Курцвайль 18 раз заправлял автомобиль на одной заправке под городом Таусон в штате Мэриленд. Он заезжал туда каждый третий четверг каждого месяца, даже если заправлялся заранее. В 3 из 18 случаев внедорожник, зарегистрированный на имя жены турецкого нефтепромышленника, был там же за два часа до него.
Этот нефтепромышленник, как выявила «Машина», в свое время заплатил за авиабилеты некоего иранца, подозреваемого во взрыве еврейского центра в Буэнос-Айресе в 1994 году. Тончайшая нить между Курцвайлем и его связным, – но машина ее увидела. Она знала и была права. И она следит так за всеми нами».
А вот описание того, как работает Palantir, процитированное в публикации Businessweek со слов его разработчиков:
«В октябре иностранный гражданин по имени Майк Фикри приобрел билет в один конец на самолет из Каира в Майами, где он снимал квартиру. В течение нескольких недель до того он неоднократно снимал ощутимые суммы со счета в российском банке и много раз звонил нескольким абонентам в Сирию. Совсем недавно он арендовал грузовик, поехал в Орландо и в одиночку посетил Диснейленд. Там, как показывают многочисленные видеозаписи камер наблюдения, он не резвился среди веселых аттракционов и прочих достопримечательностей, а провел почти весь день, фотографируя на переполненной площади при входе в Диснейленд.
Ни одно из этих действий само по себе не вызывает подозрений. Многие арендуют грузовики. Многие покупают билет в один конец. Многие имеют связи в Сирии. Немало иностранцев хранят деньги в российских банках. И есть среди них немало угрюмых бук, не умеющих веселиться даже в Диснейленде. Однако все эти факты, только будучи взятые в комплексе, наводят на подозрение, что он, возможно, что-то замышляет.
Несколько лет назад этот комплексный взгляд был невозможен. Аналитик ЦРУ обратил бы внимание на билет в один конец из Каира в Майами, агент ФБР увидел бы серию банковских проводок из российского банка. Но ничто не могло помочь аналитику и агенту связать эти факты вместе. Не говоря уж об их увязке с данными об аренде грузовика и о поездке в Орландо. А про увязку всего названного с анализом видео с камер наблюдения Диснейленда нечего и говорить. Все это было невозможно еще несколько лет назад.
А сейчас это не просто возможно, а работает на задачи безопасности. Благодаря программе, созданной компанией Palantir Technologies, ставшей любимицей спецслужб США».
Сравнив эти два описания, не трудно понять принцип работы «Машины» и системы Palantir. Он один и тот же (за одним маленьким отличием, о котором скажу чуть позже).
1. Идет сбор потоков данных со ВСЕХ доступных информационных каналов обо ВСЕХ регистрируемых событиях, касающихся ВСЕХ людей: покупка и аренда (билеты, авто, недвижимость, лодки и т.д.), банковские транзакции, транзакции по кредиткам с привязкой к локатору местоположения и характеру покупки (например, оплата на конкретной автозаправке), телефонные звонки, электронная почта, информация со ВСЕХ камер видеонаблюдения, информация о транзакциях во всех федеральных и муниципальных базах данных (полиция, пожарные, госпитали и т.д.) и много что еще.
2. В каждом потоке данных средствами интеллектуального анализа данных Data Mining выявляются необычные события, вероятность которых мала (например, 18 заправок на одной станции в конкретный день месяца), и события из наперед заданных «тревожных списков» (например, переводы из российских банков).
3. Дальше самое сложное в «Машине» – объединение и увязка через специальные адаптеры информации о необычных событиях из разных баз.
4. Если расчетная вероятность всего комплекса связанных необычных событий окажется ниже некоего заданного порога вероятности (допускающего, что связка событий хоть и редкая, но чего не бывает), выдается сигнал тревоги, указывающий на конкретного человека, с которым связан весь комплекс событий.
Теперь о единственном отличии в том, как работают «Машина» и система Palantir. Я специально называю это системой, а не программой. Эта система состоит из комплекса программ и человека – аналитика, взаимодействующего с программой. Программа выдает информацию о комплексе связанных необычных событий в специальной визуальной форме, предназначенной для так называемого визуального интеллектуального анализа данных Visual Data Mining...
Такой анализ человек делает во много раз быстрее любого компьютера за счет своей уникальной возможности воспринимать визуальную информацию (любой суперкомпьютер в сравнении с человеком пока что отдыхает) и интуиции (тут компьютеру пока вообще делать нечего). Авторы «Person of Interest» не стали усложнять жизнь для зрителей этим отличием, – пусть «Машина» сама, без помощи человека указывает подозреваемого. Да и, в конце концов, какая разница? Ведь указывает же!
Справедливости ради нужно отметить, что система Palantir ничего не смогла бы найти, не будь у нее выхода на колоссальный объем информации, собираемой о каждом человеке. Для сбора и накопления такой информации за последние 20 лет было создано много специализированных систем. Это, помимо уже упоминавшегося «Эшелона» (Echelon), система «Хищник» (Carnivore), система «Эйнштейн» (Einstein), а также хранилища информации, собираемой по технологии «Буря» (Tempest) – электронная слежка, и NGI (Next Generation Identification) – биометрическое распознавание человека.
Информация обо всех людях, собираемая названными системами, а также информация из баз данных банков, процессинговых центров, авиакомпаний и т.д. сваливается и сплавляется в так называемых «плавильных центрах» (Fusion Centers). Ну а подключившись к этим центрам, «Машина» может творить чудеса, выискивая среди сотен миллионов людей подозреваемых в чем-то, что грозит национальной безопасности.
Но помимо этих подозреваемых, «Машина», говоря словами фильма «Person of Interest», «видит все. Преступления, связанные с обычными людьми. Такими, как вы». Спецслужбы такая информация не интересует, но ее можно использовать для весьма хитроумных целей вплоть до предсказания преступлений «обычных людей». И теперь, надеюсь, вы понимаете, что сюжет фильма «Person of Interest» не такая уж и фантастика (лишь чуть-чуть для интересности прибавили).
Конечно, есть энтузиасты – борцы за экономию бюджета, считающие, что миллиарды, выделяемые на «плавильные центры», бросаются на ветер. Даже двухпартийное расследование по этому поводу только что провели. Но «Машина» работает и будет работать дальше.
Что же до фильма «Person of Interest», то можно подбросить дров в костер паранойи: есть мнение, что фильм – чистая пропаганда «Большого брата». И что будто бы главной целью фильма было программирование общественного мнения на толерантное отношение к «Машине», осуществляемое с помощью другой «машины», под названием Predictive Programming.
20.12.2012 Бойня в Ньютауне: от нас что-то утаивают?
По наводке блога Дневник кризиса.
...А в США уже запустили второй фронт. В Нью Йорке мэр Блумберг, в Чикаго мэр Рам Эмануэл и в сенате представитель от Калифорнии Диана Фильштейн и от Коннектикута Джо Либерман немедленно требуют ввести запрет на эффективное оружие (которое реально можно использовать для защиты себя, а не для походов в тир). И введут.http://log2stas.livejournal.com/750483.html
Сначала заберут оружие, а потом детей начнут забирать, которые промывке мозгов не поддаются. Если сын растёт не толерантный значит родители плохо воспитывают - отобрать. Общество должно быть с промытыми мозгами. Если не хотят родители промывать мозги - будут отбирать детей у таких родителей. Следующее поколение должно быть воспитано на либеральных ценностях, на ценностях покорности власти и её идеалам. А с оружием схема то ясна. Устроить две-три провокации очень мощных и под шумок, последних прав лишить. Оно так и будет. Всё у них похоже в этот раз должно получится. А то, что в этих провокациях все шито белыми нитками, так то не важно, народ же верит новостям, хоть те и врут каждый день на разный лад, что даже предыдущее враньё с новым никак не сходится.
Wednesday, December 19, 2012
Закат среднего класса: будущее семьи, занятости и экономики в США
...Сегодняшняя экономика пробуксовывает. Её способность повышать качество жизни независимо от уровня доходов понижается, если вообще не находится под большим знаком вопроса...
Ниже есть продолжение.
РАЗРЫВhttp://hvylya.org/analytics/society/zakat-srednego-klassa-budushhee-semi-zanyatosti-i-ekonomiki.html
Обратимся к графику № 1. Он показывает одно из важнейших для любой экономики взаимодействий – между производительностью труда и его оплатой (почасовой). Производительность показывает ценность товаров (тормозных колодок, биржевых транзакций и проч.), изготовленных работником, скажем, за день. Оплата включает в себя и такие блага, как медицинская страховка. Диаграмма показывает уровень оплаты труда всех американских рабочих, а особенно – рабочих, занятых на производстве и офисного персонала (так называемые «синие воротнички» и «офисный планктон»).
Десятилетиями производительность труда и уровень его оплаты росли в тандеме. Ихняя взаимосвязь была основой общественного договора между экономикой и населением: если ты работаешь больше и лучше, то ты и твоя семья лучше обеспечены. Но в течение последних нескольких десятилетий, а особенно – за последние 10 лет или около того, эти линии расходятся. Вот вам и разрыв № 1: производительность труда работников растет, а оплата – нет.
Правда, средний уровень оплаты труда по-прежнему растет. Но повышение очень неоднородно. Рабочие, занятые на производстве и офисный персонал – занятые на заводах и фабриках, в розничной торговле, например – почувствовали разрыв между ростом производительности их труда и уровнем компенсации гораздо раньше и ощутили удар сильнее, чем руководители и специалисты. За последние 30 лет или около того уровень оплаты их труда вряд ли поднялся вообще.
«То, что сейчас происходит – устоялось в течение многих лет и действительно уходит корнями в экономику, и это очень плохо. В наличии существенный разрыв. И проблема не в том, что экономика не производит достаточно дохода, чтобы сделать жизнь каждого лучше, а в том, что экономика устроена таким образом, который не выгоден большинству», — говорит Лоуренс Мишел, президент Economic Policy Institute, либерального аналитического центра в Вашингтоне. Или, если попытаться высказать свою точку более деликатно, большинство американцев уже не выигрывают от роста производительности, как это получалось у их родителей, бабушек и дедушек.
...График № 3 как раз показывает, что же именно происходит. С конца Второй мировой войны и до 1980-х 2/3 от каждого заработанного экономикой доллара отходили рабочим в виде зарплат и пособий. Начиная с середины 1980-х доля рабочих начала понижаться и в последнее десятилетие упала до 58%. Разница ушла держателям акций и другим инвесторам, представляющим капитал, а не труд...
...Это – разрыв № 4: малозарабатывающие мужчины все меньше способны образовывать стабильные семьи. Это в свою очередь наносит вред их детям и общинам. «Социальный капитал распадается, если у вас совпадают падение занятости и распад браков», – говорит Чарльз Мюррей, консервативный ученый из American Enterprise Institute и автор книги «Руина: государственность «белой» Америки в 1960 -2010».
Рассматривая такие разные экономические показатели среди мужчин из верхней и нижней части графика образованности, можно предположить, что такая самовоспроизводящаяся тенденция приведет к чему-то вроде классового разделения. И это верно. «Если вы оглянетесь на 50 лет назад, то никакого классового разделения при заключении браков не было», говорит Брэд Уилкокс.
Сегодня, как показывает график № 6, вступление в брак и уровень доходов коррелируют. В 1970 году более 3/4 мужчин, независимо от того, сколько они зарабатывали, были женатыми, мужчины из нижнего уровня шкалы доходов имели лишь немного больше шансов жить в одиночестве, чем мужчины из самого верха. Сегодня почти половина малозарабатывающих мужчин являются холостяками, по сравнению с лишь 1/7 мужчин с высокими доходами.
Именно семья является одной из главных причин, но в то же время и главной жертвой все возрастающего классового разделения общества. На вершине его находятся полные семьи с двумя добытчиками, у обоих из которых имеется высшее образование, с детьми, которые без сомнения тоже в будущем получат, как минимум степень бакалавра и хорошую работу. Внизу – неполные семьи с единственным кормильцем-женщиной, не окончившей колледж, незамужние, чьи дети растут изолировано от мира, где бывает хорошая работа и высшее образование. И оба этих мира отдаляются друг от друга все сильнее...
Иранская пресса сообщает о поставках в Сирию российских ракетных комплексов «Искандер» (English, Hebrew, Russian)
Первоисточник המקור Original source English Mashregh, Iran
Dekba Hebrew
Hours after NATO agreed on Tuesday to send Patriot missiles to Turkey because of the crisis in Syria, Russia delivered its first shipment of Iskander missiles to Syria.http://hamsayeh.net/world/2550-russia-arms-syria-with-powerful-ballistic-missiles.html
Иранская пресса распространила информацию о том, что через несколько часов после того, как совет НАТО одобрил 11 декабря отправку ракет "Пэтриот" в Турцию из-за кризиса в Сирии, Россия поставила Дамаску первую партию ракетных комплексов "Искандер".http://warsonline.info/siriya/iran-soobschaet-o-postavkach-v-siriiu-raket-iskander.html
Race Against the Machine (English)
McAfee brings together a range of statistics, examples, and arguments to show that technological progress is accelerating, and that this trend has deep consequences for skills, wages, and jobs. He makes the case that employment prospects are grim for many people today, not because technology has stagnated, but instead because we humans and our organizations aren't keeping up.http://www.youtube.com/watch?v=GPaf9YGz6Es
Три задачи по программированию - решение
Полные условия задач, находятся тут.
1. Бесконечная ж/д с 2 паровозами с парашютами.
2. Запрограммировать лифт.
3. Отсортировать большой файл в бесконечной файловой системе.
Ниже приведено детальное руководство к решение этих задач. Рекомендую прежде, чем смотреть решение, попытаться решить самостоятельно. Если не получится, прочитать первую подсказку, подумать ещё. Если всё равно не получается, прочитать следующую подсказку. В некоторых местах, шаги решения, возможно, слишком детализированы, это сделано умышленно, так как возможно, вам будет достаточно лёгкого толчка, чтобы найти решение. С другой стороны, возможно, вам надо будет прочитать несколько подсказок подряд. В некоторых местах подсказки разбиты на подпункты.
Ниже есть продолжение.
Подсказки.
1. Бесконечная ж/д с 2 паровозами с парашютами.
2a. Попробуйте решить упрощённый вариант сначала без ограничения языка, чтобы получить некоторое начальное представление (спорная подсказка).
2b. Посмотрите на используемые ваши средства выражения языка. "Считать шаги" тоже нельзя.
2c. Код программы должен быть конечен (это относится к "считать шаги").
2d. Попробуйте другой подход. Помните, что код в обоих паровозах должен быть идентичен, однако у вас есть if(isOtherParachuteFound)...
2e. Попытайтесь сначала найти парашют другого паровоза...
2f. Как после этого, найти другой паровоз? Запомните, что вы делали после того, как нашли парашют.
3a. Каким образом, вы можете гарантировано найти парашют.
3b. Если вы будете идти в одну сторон, то один из паровозов обязательно наткнётся на другой парашют.
3c. Где при этом будет второй паровоз?
3d. Как ему можно "сообщить", о том, что вы только нашли его парашют?
4. Вместо того чтобы увеличить скорость паровоза в два раза, можно уменьшить первоначальную скорость паровоза.
2. Запрограммировать лифт.
1. Тут главное понять условие задачи, и что от вас требуется. Представьте обычный дом с одним лифтом. Вы подходите к лифту и хотите добраться до какого-то этажа. Как лифт себя ведёт. Почему? Сымитируйте его действия.
2. Представьте конкретные примеры. Ниже приведены несколько, читайте по одному и возвращайтесь к решению задачи, придумывайте свои примеры:
а) Вы стоите на входе. Лифт находится на 5 этаже. Вам надо на 2. Вы нажимаете "вверх". Лифт опускается до 0 этаже. Вы входите, нажимаете 2, лифт поднимается до 2.
б) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно выйти из здания.
в) Развёрнутый б) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно выйти из здания. Вы нажимаете "вниз". Лифт доезжает до 7 этажа, из него там выходит другой человек, затем он едет в вам на 4 этаж, вы нажимаете на кнопку 0, лифт едет вниз до входа из здания, вы выходите.
г) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно на 6 этаж.
д) Развёрнутый г) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно на 6 этаж. Вы нажимаете "вверх". Лифт доезжает до 4 этажа, останавливается, вы туда заходите, нажимаете на 6. Лифт продолжает ехать вверх, доезжает до 6 этажа, останавливается, вы выходите. Лифт продолжает ехать до 7 этажа, чтобы довести другого человека.
е) Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно на 8 этаж.
ж) Структура данных 2 связанных списка с указателями в начало и конец списка (Deque).
з) Зная ж) перечитайте д) и е). Всё должно стать очевидным.
3. Отсортировать большой файл в бесконечной файловой системе.
1. Фраза При этом a/b не является O(1) является в условии задачи является своего рода подсказкой.
2. Игнорируйте на данном этапе I\O. Вас ограничили в оперативной памяти, но у вас сколько угодно места на диске. Используйте диск.
3. Вы можете отсортировать 10Mb чисел.
4. Вы можете получить 2048 "стопок" (файлов!) по 10Мb чисел в каждом.
5. Вы можете отсортировать каждую "стопку чисел" по отдельности.
6. Две "стопки чисел"=две колоды карт, которые нужно слить в одну.
7а. Напишите два списка отсортированных чисел, подумайте как их можно объединить в один список.
7б. Это можно сделать за O(n+m), где n и m - длины списков. При этом если a/b не является точной степенью 2 n может в точности не равнятся m и может быть, что количество списков будет нечётным. Но это ничего не меняет. Подумайте почему.
7с. За сколько операция объедений списка можно слить все "стопки чисел" в одну "стопку"?
8. Вспомните про I\O. Подумайте как можно уменьшить перемещение головки записи диска по всему диску (количество r\w при этом практически не изменится).
9. Нужно выбрать "стопку" с наименьшим "верхним" числом (среди всех "верхних" чисел). Следующая "стопка" должна быть со "следующим" "верхним" числом. Как при этом не потерять связь между числом и "стопкой" из которой он был взят?
10. Вспомните, что k=a/b=2048 "большое число" (не константа), как в таком случае, можно сделать пункт 8 за O(k*log k)?
1. Бесконечная ж/д с 2 паровозами с парашютами.
2. Запрограммировать лифт.
3. Отсортировать большой файл в бесконечной файловой системе.
Ниже приведено детальное руководство к решение этих задач. Рекомендую прежде, чем смотреть решение, попытаться решить самостоятельно. Если не получится, прочитать первую подсказку, подумать ещё. Если всё равно не получается, прочитать следующую подсказку. В некоторых местах, шаги решения, возможно, слишком детализированы, это сделано умышленно, так как возможно, вам будет достаточно лёгкого толчка, чтобы найти решение. С другой стороны, возможно, вам надо будет прочитать несколько подсказок подряд. В некоторых местах подсказки разбиты на подпункты.
Ниже есть продолжение.
Подсказки.
1. Бесконечная ж/д с 2 паровозами с парашютами.
2a. Попробуйте решить упрощённый вариант сначала без ограничения языка, чтобы получить некоторое начальное представление (спорная подсказка).
2b. Посмотрите на используемые ваши средства выражения языка. "Считать шаги" тоже нельзя.
2c. Код программы должен быть конечен (это относится к "считать шаги").
2d. Попробуйте другой подход. Помните, что код в обоих паровозах должен быть идентичен, однако у вас есть if(isOtherParachuteFound)...
2e. Попытайтесь сначала найти парашют другого паровоза...
2f. Как после этого, найти другой паровоз? Запомните, что вы делали после того, как нашли парашют.
3a. Каким образом, вы можете гарантировано найти парашют.
3b. Если вы будете идти в одну сторон, то один из паровозов обязательно наткнётся на другой парашют.
3c. Где при этом будет второй паровоз?
3d. Как ему можно "сообщить", о том, что вы только нашли его парашют?
4. Вместо того чтобы увеличить скорость паровоза в два раза, можно уменьшить первоначальную скорость паровоза.
2. Запрограммировать лифт.
1. Тут главное понять условие задачи, и что от вас требуется. Представьте обычный дом с одним лифтом. Вы подходите к лифту и хотите добраться до какого-то этажа. Как лифт себя ведёт. Почему? Сымитируйте его действия.
2. Представьте конкретные примеры. Ниже приведены несколько, читайте по одному и возвращайтесь к решению задачи, придумывайте свои примеры:
а) Вы стоите на входе. Лифт находится на 5 этаже. Вам надо на 2. Вы нажимаете "вверх". Лифт опускается до 0 этаже. Вы входите, нажимаете 2, лифт поднимается до 2.
б) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно выйти из здания.
в) Развёрнутый б) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно выйти из здания. Вы нажимаете "вниз". Лифт доезжает до 7 этажа, из него там выходит другой человек, затем он едет в вам на 4 этаж, вы нажимаете на кнопку 0, лифт едет вниз до входа из здания, вы выходите.
г) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно на 6 этаж.
д) Развёрнутый г) Вы стоите на 4 этаже. Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно на 6 этаж. Вы нажимаете "вверх". Лифт доезжает до 4 этажа, останавливается, вы туда заходите, нажимаете на 6. Лифт продолжает ехать вверх, доезжает до 6 этажа, останавливается, вы выходите. Лифт продолжает ехать до 7 этажа, чтобы довести другого человека.
е) Лифт находится на 1 этаже и едет вверх до 7 этажа (внутри есть другой человек, которому нужно туда). Вам нужно на 8 этаж.
ж) Структура данных 2 связанных списка с указателями в начало и конец списка (Deque).
з) Зная ж) перечитайте д) и е). Всё должно стать очевидным.
3. Отсортировать большой файл в бесконечной файловой системе.
1. Фраза При этом a/b не является O(1) является в условии задачи является своего рода подсказкой.
2. Игнорируйте на данном этапе I\O. Вас ограничили в оперативной памяти, но у вас сколько угодно места на диске. Используйте диск.
3. Вы можете отсортировать 10Mb чисел.
4. Вы можете получить 2048 "стопок" (файлов!) по 10Мb чисел в каждом.
5. Вы можете отсортировать каждую "стопку чисел" по отдельности.
6. Две "стопки чисел"=две колоды карт, которые нужно слить в одну.
7а. Напишите два списка отсортированных чисел, подумайте как их можно объединить в один список.
7б. Это можно сделать за O(n+m), где n и m - длины списков. При этом если a/b не является точной степенью 2 n может в точности не равнятся m и может быть, что количество списков будет нечётным. Но это ничего не меняет. Подумайте почему.
7с. За сколько операция объедений списка можно слить все "стопки чисел" в одну "стопку"?
8. Вспомните про I\O. Подумайте как можно уменьшить перемещение головки записи диска по всему диску (количество r\w при этом практически не изменится).
9. Нужно выбрать "стопку" с наименьшим "верхним" числом (среди всех "верхних" чисел). Следующая "стопка" должна быть со "следующим" "верхним" числом. Как при этом не потерять связь между числом и "стопкой" из которой он был взят?
10. Вспомните, что k=a/b=2048 "большое число" (не константа), как в таком случае, можно сделать пункт 8 за O(k*log k)?
Tuesday, December 18, 2012
Три задачи по программированию
1. Бесконечная ж/д с 2 паровозами с парашютами.
2. Запрограммировать лифт.
3. Отсортировать большой файл в бесконечной файловой системе.
Ниже есть продолжение.
Условия задач.
1. Бесконечная ж/д с 2 паровозами с парашютами. Дана прямая ветка ж/д неограниченной длинны, без петель. На неё в не заданный заранее местах садятся с парашютом два паровоза. После приземления, они отстёгивают парашют и он остаётся лежать в точке приземления. Требуется написать программу, две идентичных копии которой будут бежать в этих 2 паровозах. Цель программы, найти другой паровоз. При этом между паровозами на расстоянии нет никакой связи. Чтобы ещё больше усложнить задачу, задан очень ограниченный язык имеющий
moveLeft - поехать влево
moveRight - поехать враво
if(isOtherParachuteFound){
...
{ else {
...
}
- это единственный доступный оператор ветвления (if)
Более того, ваша программа должна быть внутри
while(!meet){
_PUT_YOU_CODE_HERE_
}
Пока паровозы не столкнулись, сделать что-то. Вместо что-то должна быть ваша программа.
Подчеркну: Переменных никаких нет, if-ов нет, кроме одного, приведенного выше, циклов - тоже нет.
2. Запрограммировать лифт. Дан лифт в многоэтажном доме. Пронумеруем этажи 0 (вход),1,2,...,n. На каждом этаже есть кнопки вверх и вниз. В самом лифте есть кнопки с указанием номера этажа. Если человек, хочет поехать вверх он нажимает, на кнопку вверх, если он хочет поехать вниз-вниз. Лифт должен развести всех людей, которые пользуются лифтом, совершая как можно меньше изменений в движении (каждое изменение, вместо того, чтобы ехать вверх-едем вниз, вместо того, чтобы ехать вверх-едем вниз, приводит к большой трате электроэнергии, а мы хотим её сэкономить). Опишите структуру данных, которую вы будете при этом использовать.
3. Отсортировать большой файл в бесконечной файловой системе. У вас есть очень большой файл, размером a (к примеру a=2 Gb) содержащих, к примеру, целые числа разделённые между собой с помощью \n. Весь файл целиком не помещается у вас в оперативной памяти, размером порядка b (скажем, у вас всего b~10 Mb памяти). При этом a/b не является O(1). Но у вас есть неограниченная в размерах файловая система, вам разрешается свободно писать и читать в неё, создавать сколько угодно новых файлов, менять уже существующие и т.п. Нужно отсортировать этот файл. Это может быть как существующий файл, так и новый, где все числа отсортированы в порядке возрастания.
Подсказки к решению задач, находятся тут.
2. Запрограммировать лифт.
3. Отсортировать большой файл в бесконечной файловой системе.
Ниже есть продолжение.
Условия задач.
1. Бесконечная ж/д с 2 паровозами с парашютами. Дана прямая ветка ж/д неограниченной длинны, без петель. На неё в не заданный заранее местах садятся с парашютом два паровоза. После приземления, они отстёгивают парашют и он остаётся лежать в точке приземления. Требуется написать программу, две идентичных копии которой будут бежать в этих 2 паровозах. Цель программы, найти другой паровоз. При этом между паровозами на расстоянии нет никакой связи. Чтобы ещё больше усложнить задачу, задан очень ограниченный язык имеющий
moveLeft - поехать влево
moveRight - поехать враво
if(isOtherParachuteFound){
...
{ else {
...
}
- это единственный доступный оператор ветвления (if)
Более того, ваша программа должна быть внутри
while(!meet){
_PUT_YOU_CODE_HERE_
}
Пока паровозы не столкнулись, сделать что-то. Вместо что-то должна быть ваша программа.
Подчеркну: Переменных никаких нет, if-ов нет, кроме одного, приведенного выше, циклов - тоже нет.
2. Запрограммировать лифт. Дан лифт в многоэтажном доме. Пронумеруем этажи 0 (вход),1,2,...,n. На каждом этаже есть кнопки вверх и вниз. В самом лифте есть кнопки с указанием номера этажа. Если человек, хочет поехать вверх он нажимает, на кнопку вверх, если он хочет поехать вниз-вниз. Лифт должен развести всех людей, которые пользуются лифтом, совершая как можно меньше изменений в движении (каждое изменение, вместо того, чтобы ехать вверх-едем вниз, вместо того, чтобы ехать вверх-едем вниз, приводит к большой трате электроэнергии, а мы хотим её сэкономить). Опишите структуру данных, которую вы будете при этом использовать.
3. Отсортировать большой файл в бесконечной файловой системе. У вас есть очень большой файл, размером a (к примеру a=2 Gb) содержащих, к примеру, целые числа разделённые между собой с помощью \n. Весь файл целиком не помещается у вас в оперативной памяти, размером порядка b (скажем, у вас всего b~10 Mb памяти). При этом a/b не является O(1). Но у вас есть неограниченная в размерах файловая система, вам разрешается свободно писать и читать в неё, создавать сколько угодно новых файлов, менять уже существующие и т.п. Нужно отсортировать этот файл. Это может быть как существующий файл, так и новый, где все числа отсортированы в порядке возрастания.
Подсказки к решению задач, находятся тут.
Уважаемые египетские мятежники! (ЮМОР)
В ходе своих выступлений постарайтесь не снести пирамиды.
Новые мы вам строить не будем.
Евреи.
Найдено на просторах интернета.
Monday, December 17, 2012
חוב של טריליון דולר (ЮМОР)
Найдено на просторах интернета.
יש המשך למטה.
Ниже есть продолжение.
רבים בוודאי תוהים מה עלה בגורלי בעקבות החוב בן טריליון (ויותר) השקלים שהתרגש עליי בפתאומיות אמש. לא מעטים אף ביקשו באופן מפורש שאפרסם כאן את המשך השתלשלות העניינים. ובכן, הנה הוא לפניכם:
יש המשך למטה.
Ниже есть продолжение.
נציגת שירות: שלום, כיצד אוכל לעזור?
אנחנו: שלום (מוסר פרטים אישיים להזדהות), הגיע אליי מכתב קצת מוזר מכם.
נציגת שירות: מה הגיע?
אנחנו: כתוב שגביתם ממני סכום גדול יחסית עבור שימוש ב"מנהרות הכרמל", בהוראת קבע.
נציגת שירות: כן, אני רואה ששלחנו לך מכתב על גביית הוראת קבע.
אנחנו: העניין הוא שהסכום גדול. מאוד.
נציגת שירות: מה זאת אומרת?
אנחנו: כתוב שזה טריליון, 121 מיליארד, 201 מיליון ו-200 אלף שקל.
נציגת שירות: כמה??
אנחנו: טריליון, 121 מיליארד, 201 מיליון ו-200 אלף שקלים. חדשים.
נציגת שירות: (שותקת)
אנחנו: זה פשוט הרבה כסף... אני לא בטוח שאני יכול לעמוד בזה. זה גם לא נראה לי הגיוני.
נציגת שירות: רגע, אבל אני רואה שכבר שנה וחצי אתה נוסע במנהרות ומשלם מדי חודש בהוראת קבע.
אנחנו: נכון.
נציגת שירות: אז איך אתה יודע שזו טעות?
אנחנו: זה נכון, אני נוסע במנהרות, אבל לא כל כך הרבה. נאמר, ב-30 שקל בחודש בערך. לא טריליון, 121 מיליארד, 201 מיליון ו-200 אלף שקל.
נציגת שירות: כמה??
אנחנו: טריליון, 121 מיליארד, 201 מיליון ו-200 אלף שקלים. חדשים. זה פי ארבעה מתקציב המדינה לשנה.
נציגת שירות: מה תקציב המדינה?
אנחנו: לא משנה. בקיצור, זה לא הגיוני.
נציגת שירות: אני מבינה אותך, באמת שאני מבינה אותך, אבל אתה בטוח שלא נסעת יותר מהממוצע החודש? כי היו חגים וכאלה.
אנחנו: יכול להיות שנסעתי יותר, אבל כדי להגיע לסכום כזה צריך להקיף 8 מיליון פעם את כדור הארץ סביב קו המשווה. דרך מנהרות הכרמל. במהלך חודש אחד. חגים, לא חגים, 8 מיליון פעם קו המשווה.
נציגת שירות: מה קו המשווה?
אנחנו: לא משנה. בקיצור, זה לא הגיוני!
נציגת שירות: אני מבינה אותך, באמת שאני מבינה אותך. יודע מה? אני צריכה לאשר את זה עם האחראי שלי, אבל אני יכולה לנסות לפרוס את החיוב ל-6 תשלומים ללא ריבית.
אנחנו: של 200 מיליארד שקל כל אחד?!
נציגת שירות: רגע, תמתין.
(מתקתקת במחשב, שואלת את האחראי, שומעים הד של קול גברי סמכותי. חוזרת לשפופרת)
נציגת שירות: זה יוצא 186 מיליארד, 866 מיליון, 666 אלף, 666 שקל ו-66 אגורות. נעגל נגיד ל-187 מיליארד.
אנחנו: את מעגלת במאה מיליון שקל??
נציגת שירות: באחוזים זה ממש מעט.
אנחנו: אבל זה לא הגיוני!!!
נציגת שירות: טוב, אם אתה מעדיף תשלום אחד זו בחירה שלך.
אנחנו: מה תשלום אחד?? אני לא חייב לכם טריליון שקל!
נציגת שירות: טריליון, 121 מיליארד, 201 מיליון ו-200 אלף שקל.
אנחנו: זה יותר מהשווי של כל עתודות הנפט של כווית!
נציגת שירות: מה כווית?
אנחנו: לא משנה. זה המון!!! זה... זה לא הגיוני!!!
נציגת שירות: נו מה אני אעשה, זה מה שכתוב במחשב.
אנחנו: אז מה עושים?
נציגת שירות: לא יודעת. דבר עם הבנק, זה כבר עניין שלך, אני לא אכנס לך לכיס.
אנחנו: הבנתי.
נציגת שירות: אז לפרוס לך לתשלומים?
אנחנו: לא, תשלום אחד, בעשירי לחודש... כשנכנסת המשכורת.
נציגת שירות: אוקיי. ביצעתי.
אנחנו: יופי, תודה. אהה, יש לי עוד עניין לסדר אצלכם, אם אנחנו כבר על הקו.
נציגת שירות: כן, בבקשה?
אנחנו: אני צריך להגדיל את מסגרת האשראי בכרטיס. ל... נאמר... טריליון, 121 מיליארד, 201 מיליון ו-200 אלף שקל.
נציגת שירות: אתה בטוח?
אנחנו: כן, בטוח.
נציגת שירות: אבל זה לא הגיוני, זה פי ארבעה מתקציב המדינה...
(שיחה קפקאית שכמעט והתקיימה עם שירות הלקוחות של חברת האשראי).
Sunday, December 16, 2012
Эфраим Кишон. Победа в Совете Безопасности (1968)
Фельетон.
Ниже есть продолжение.
Пакистанское предложение осудить Израиль за оккупацию Чехии Красной Армией было подано дежурному председателю Совета позавчера под утро, и с тех пор продолжаются контакты между делегациями с целью сформировать единую позицию. Из закулисных бесед выясняется, что большинство, необходимое для осуждения, труднодостижимо, т.к. только 8 стран безоговорочно поддерживают его: Польша, СССР, Нигерия, Алжир, Югославия, Саудовская Аравия и собственно Пакистан. По слухам, делегация США возражает против возложения полной ответственности на Израиль, а Бельгия и Канада просили отложить обсуждение для достижения приемлемого для всех компромисса.
Перед откладыванием заседания наш представитель, г-н Йосеф Ткоа, успел разъяснить Совету позицию нашего правительства:
- Не Израиль вторгся в ЧССР, а Россия со своими сателлитами - и надо осудить Россию, а не нас.
Ниже есть продолжение.
Яков Малик, представитель СССР, демонстративно покинул зал с красным от гнева лицом, крикнув г-ну Ткоа:http://mar-shim.livejournal.com/37082.html
- Геббельсовкие приёмы вам теперь на помогут! Вы играете с огнём!
Турецкий председатель остановил речь г-на Ткоа, чтобы дать время для закулисных переговоров. Из секретных сообщений выясняется, что Никарагуа, Бельгия и Канада проявляют сдержанное понимание израильской позиции по существу оккупационного режима в Чехии, но с другой стороны, как объяснил бельгийский представитель в интимной беседе с израильской делегацией, нет смысла представлять позицию, у которой нет шансов пройти голосование. «В конце концов» - отметил бельгийский представитель, - «мы не дети». Французский представитель выразил недовольство отсутствием в Чехии наблюдателя ООН для отчёта о происходящем и запросил разъяснений из Парижа.
В отличие от них, отношение американской делегации было умеренно-дружественным.
- Может, было бы справедливо осудить СССР, - признал глава делегации в беседе с глазу на глаз, - но у русских есть, как известно, право вето. Так что надо видеть происходящее как часть глобальной стратегии США, сохраняющей престиж ООН.
Г-н Ткоа обратил внимание главы делегации на то, что у США есть такое же право вето, как у русских, но американский представитель резко отверг «любое сравнение с этими бандитами».
Атмосфера в кулуарах накалилась, после того как Алжир распространил язвительную листовку, где Израиль был назван «вымогателями», а «Правда» возобновила нападки на «нацистскую солдатню из Тель-Авива, опьянённую оккупациeй».
Израильская делегация не сидела сложа руки и представила в президиум Совета фотографии русских бронемашин, разъезжающих по улицам Праги, но американский представитель, сдерживая гнев, просил изъять снимки, которые «показывают банальные факты, никак не способствующие прояснению ситуации». Закулисные переговоры дошли до кипения: Югославия и Нигерия сформулировали новое предложение, обвиняющее Израиль в геноциде, но обнаружив затруднение собрать 9 голосов - ограничились совместным с Саудовской Аравией заявлением и назвали Израиль «неофашистскими работорговцами, убийцами чешского народа».
«Не ввязывайтесь в спор» -глава делегации США написал успокаивающую личную записку израильской делегации, - «мы действуем за кулисами».
И действительно, решительная позиция наших заморских друзей сделала своё дело, и в последний момент СССР отступил от требования прямого осуждения Израиля в обмен на обещание Запада поддержать смягчённую польскую формулировку:«Совет Безопасности выражает сожаление в связи с актами агрессии в Восточной Европе, Совет предостерегает Израиль от нарушения в будущем принципов ООН.» Перед закрытием заседания была внесена поправка Белоруссии: «Кроме того, Израиль должен прекратить причинять землетрясения в Иране». Но всё это не меняет того факта, что не были упомянуты никакие санкции, как отметили МИДовские круги. «Резолюция не связывает прямо события в Чехии с Израилем, т.к. 2 предложения разделены запятой». Кроме того они отметили, что слово «причинять» в связи землетрясениями в Иране не содержит прямого обвинения в злом умысле Израиля, а оставляет возможность толкования как случайность. И наконец, не забудьте, Совет выразил «сожаление», а не «глубокое сожаление» - и тут хорошо видно смягчающее влияние американской делегации.
- Предложение осудить Израиль из-за оккупации Чехии окончательно провалилось - подытожил министр иностранных дел достижения делегации перед членами правительства. - Эта дипломатическая победа достигнута благодаря трём факторам: а)широкая разъяснительная деятельность, б)твёрдая поддержка дружественной державы, в)справедливость.
Дисклеймер:
* Не нашёл перевода, так шо звиняйте за кустарщину.
* Красная Армия, Россия, Чехия - так в оригинале.
Subscribe to:
Posts (Atom)