Олимпиада по программированию

Нашел одну олимпиаду по программированию, проводимую факультетом управления и прикладной математики МФТИ. Правда она вроде как для школьников, но и нам можно потренироваться. Олимпиада проводится до 15 23 января (продлена).

В контесте 20 задач. Олимпиада проводится по кировской системе (то есть баллы приносит даже решение, которое проходит только часть тестов) на Ejudge. Языки: C, C++, basic (компилятор yabasic), perl, pascal, Java, C#, ruby, python, fortran. На проверку отправляется исходный текст программы (не исполняемый и не файл проекта). Проверка автоматическая, так что никаких окон и приглашений к вводу делать не надо, а вот строгое соответствие формату данных, указанному в задаче, требуется. Ввод из стандартного потока ввода (с клавиатуры), вывод в стандартный поток вывода (на экран).

Задачи разного уровня от самых простых (из контрольных работ для начинающих и пробных туров олимпиад) до совсем сложных (уровня полуфинала чемпионата мира по програмимрованию ACM ICPC). Составители контеста — тренеры и часть состава команды mipt_waterogers, финалиста ACM ICPC 2010-2011 и 2011-2012 годов.

Вот собственно этот сайт, где проводится олимпиада: judge.mipt.ru. Будем участвовать?

Новогодние снежинки! топик-ссылка

С помощью онлайн-редактора каждый может вырезать собственную, неповторимую снежинку, чтобы поделиться своим праздничным настроением со своими друзьями и близкими. Также снежинку можно сделать реальной, распечатав ее на принтере – для этого здесь есть все инструкции. С Наступающим!

Чудесайт - сайт новогоднего настроения топик-ссылка

Соверши маленькое новогоднее чудо - поздравь совершенно незнакомого человека с Новым годом и совершенно незнакомый человек поздравит тебя! Ты не увидишь его улыбки, никогда не узнаешь, тронули ли его твои тёплые слова, не услышишь благодарности, но обязательно почувствуешь её. И обязательно обрадуешься, получив такое же случайное, наполненное новогодним настроением сообщение! Уже отправлено 2849 таких поздравлений. С наступающим!

Обработка малых чисел

Эта публикация родилась из обсуждения одной задачки в блоге Команда ФПИ по программированию.
Итак, недавно, столкнулся с двумя похожими ситуациями, когда заведомо известный результат не получается при вычислении его программным образом.
Ситуация 1: Excel не дает ноль для тригонометрической функции cos(Pi/2).
Ситуация 2. FreePascal не дает ноль для функции frac(log2(128)) Команда ФПИ по программированию — функция log2.

Я и раньше встречался с подобными ситуациями. Особенно опасны они ненахождением решения в ситуации проверки равенства двух вещественных чисел. Разберемся, почему всё это происходит? Очевидно, что по причине ограниченности разрядной сетки числа. Например, посмотрим про вещественные типы данных в справке Delphi:
Type		Range	                        Significant digits
Real48		2.9x10^-39 .. 1.7x0^38			11-12
Single		1.5x10^-45 .. 3.4x10^38			7-8
Double		5.0x10^-324 .. 1.7x10^308		15-16
Extended	3.6x10^-4951 .. 1.1x10^4932		19-20

И сделаем два вывода:
1) нельзя задать сколь угодно малое или сколь угодно большое вещественное число, так как есть ограничение на порядок числа;
2) точность представления числа ограничена мантиссой (количеством значащих цифр).

Отсюда важное для программиста заключение: сравнивать вещественные числа так: «x>y» или так: «x<y» можно, но так: «x=y» — опасно.
Когда-то давно решал я подобную проблему, связанную с заполнением до предела (типа задачи «о заполнении рюкзака», ru.wikipedia.org/wiki/Задача_о_ранце) и столкнулся с проблемой сравнения двух решений, представленных вещественными числами.
— — — — — — — — — — Для текущего изложения я придумал несколько примеров, достаточно простых, но демонстрирующих суть проблемы. Несколько итераций позволят нам выйти на приемлемое решение обсуждаемой проблемы.
program Zero_01;
{$APPTYPE CONSOLE}
uses
  SysUtils,Math;
var argE: double;
    argR,arg: single;
    argR48: Real48;
begin
        arg:=Pi;      // Pi - Returns 3.1415926535897932385
                      // всего 20 значащих цифр
                      // у arg - тип single - 7 значащих цифр
        argR48:=Pi;
        writeln('Pi=',#9,Pi);
        writeln('arg=',#9,arg);
        writeln('argR48=',#9,argR48);
        writeln('__________');
        writeln(' sin=');
{1}     writeln(#9,sin(Pi));

{2}     writeln(#9,sin(arg));
        argE:=sin(arg);  // argE: double;

{3}     writeln(#9,argE);

          argR:=argE/1E30;
          argR:=argR*1E30;
{4}     writeln(#9,argR);

          argR:=argE/1E39;
          argR:=argR*1E39;
{5}     writeln(#9,argR);

        readln;
end.

Вот результаты этой программы:
Обработка малых чисел
Первое что мы увидим — число Пи представлено 20-ю значащими цифрами. Но мы то знаем, что оно иррациональное. Отсюда уже будут возникать ошибки в расчете тригонометрических функций.
Далее видим, что присвоение Pi переменной может еще ухудшить ситуацию: в переменной типа single несовпадения с Pi начинаются с 8-й значащей цифра, а для Real48 — с 13-ой;
Соответственно и вычисления синуса от разных Пи будут отличаться. Но и само значение sin(Pi) окажется отличным от нуля во всех случаях. Однако, отличие от нуля для значения Pi, представленного константой проявляется порядком E-20, а для значения Pi, представленного переменной типа single — Е-08. То есть в подсчет через переменную дает результат в 10^12 раз менее точно.

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

program Zero_02;
{$APPTYPE CONSOLE}
uses
  SysUtils,Math;
var arg: single;

function comparing1(arg1: single; arg2: single): boolean;
begin
  result:= abs(arg1-arg2)<1E-6;
end;

function comparing2(arg1: single; arg2: single): boolean;
var temp: single;
begin
  temp:=abs(arg1-arg2)/1E39;
  result:= temp*1E39 = 0;
end;

begin
        arg:=Pi;
        writeln('Pi=',#9,Pi);
        writeln('arg=',#9,arg);
        writeln('__________');
        writeln(' sin=');
{1}     writeln(#9,sin(2*Pi));
{2}     writeln(#9,sin(2*arg));
{3}     if comparing1(sin(2*arg),0)
                then writeln(#9,'=0')
                else writeln(#9,'<>0');
{4}     if comparing2(sin(2*arg),0)
                then writeln(#9,'=0')
                else writeln(#9,'<>0');

        readln;
end.

Вот результаты этой программы:
Обработка малых чисел
Как видите, константа Pi и переменная всё так же отличаются, как и результаты посчитанные для величины 2*Pi. Результаты всё так же отличаются не только друг от друга, но, что более печально, и от нуля. Однако в последних двух строчках программы нули таки выводятся. Тут я применил два подхода, обозначенных ещё в самом начале этого изложения по поводу ограничений на порядок числа и на точность, заданной мантиссой числа.
Функции сравнения comparing1 и comparing2 разными путями приходят к одинаковому результату: если числа отличаются ненамного, значит их можно признать равными. Только первая функция напрямую сравнивает, можно сказать, порядок несовпадения чисел, а вторая — отсекает все значащие цифры из мантиссы делением/умножением. Деление на порядок 39 выбрано, конечно, не случайно — надо ведь дотянуть до границы в Single 1.5x10^-45.
Итак, этот подход можно применять для работы с малыми числами или для сравнения двух малоотличающихся чисел.

Пойдём дальше и попробуем применить подход к какой-нибудь задаче. Я особо времени не тратил на изобретение задач, а взял задачу с заведомо известным результатом (для того чтобы заранее знать ответ).
Пусть нужно найти точки пересечения двух функций: cos(x/2) и sin(2*x), в диапазоне изменения x от 2,5 до 3,5. Нетрудно догадаться, что при x=Pi значения функций равны. Но только не для вычислителя — см. рисунок:
Обработка малых чисел
Обратите внимание, что косинус и синус для обозначенного значения в Excel не равны нулю.
Так же следует учитывать, что мы считаем значения с определенной дискретностью (шаг на рис. равен 0,01), то есть мы можем просто не попасть точно в точку пересечения функций. Как же быть?
Проведем первый эксперимент, имитируя Excel — просто запустим цикл с определенным, фиксированным шагом 1E-06:
program Zero_03;
{$APPTYPE CONSOLE}
uses SysUtils,Math;

function comparing1(arg1: single; arg2: single): boolean;
begin
  result:= abs(arg1-arg2)<1E-5;
end;

var low,hi,i,z1,z2: single;
    k: word;

begin
  low:=2; hi:=4;
  i:=low; k:=0;
  repeat
    z1:=cos(i/2);
    z2:=sin(2*i);
    if z1=z2 then writeln(#9,i);
    if comparing1(z1,z2)
              then
              begin
                writeln(#9,'z1=',z1);
                writeln(#9,'z2=',z2);
                inc(k);
              end;
    i:=i+1E-06;
  until i>hi;
  writeln(#9,k,' solutions');
  readln;
end.

Обратите внимание — я оставил строку «if z1=z2 then writeln(#9,i);» для того, чтобы удостовериться, что прямое сравнение вещественных чисел не даст желаемого результата.
Вот результаты работы программы:
Обработка малых чисел
Итак, прямой перебор всего диапазона даст нам 8 решений с заданной точностью. Видимо такой подход не оптимален, особенно по причине большого перебора, зависящего от величины диапазона и точности вычисления. Классическим способом преодоления указанной проблемы считается использование метода половинного деления с постепенным сужением диапазона.
program Zero_04;
{$APPTYPE CONSOLE}
uses SysUtils,Math;
const error=1E-6;
var low,hi,i,z1,z2: single;
    k: word;

function comparing1(arg1: single; arg2: single): boolean;
begin
  result:= abs(arg1-arg2)<error;
end;

begin
  low:=2; hi:=4; k:=0;
  // в начале на нижней границе  z1>z2
  // в начале на верхней границе z1<z2
  i:=(low+hi)/2;
  z1:=cos(i/2);
  z2:=sin(2*i);
  while not comparing1(z1,z2) do
  begin
    inc(k);
    i:=(low+hi)/2;
    z1:=cos(i/2);
    z2:=sin(2*i);
    if z1>z2
      then low:=i
      else hi:=i;
  end;
                writeln('Pi=',#9,Pi);
                writeln('i=',#9,i);
                writeln('z1=',#9,z1);
                writeln('z2=',#9,z2);
                writeln('k=',#9,k);                
  readln;
end.

Вот результаты работы программы:
Обработка малых чисел
Что видим: решение (точка пересечения двух функций) с заданной точностью (error) найдено за 21 шаг для аргумента близкого к Пи (отличия проявляются лишь в 8-ой значащей позиции мантиссы аргумента).

==========================================
summary
1) вещественные числа сравнивать операцией "=" не правильно;
2) переменные вещественного типа дают результат с ограниченной точностью;
3) если в задаче не указано с какой точностью найти решение, надо самому об этом позаботиться.
==========================================
P.S.1. Я мог что-то не заметить, что-то упустить — желающие могут оставить свои комментарии…
P.S.2. Программы апробировались на Delphi 7 и Delphi 2010.

Выбор хостинга для сайта

Хо́стинг (англ. hosting) — услуга по предоставлению вычислительных мощностей для физического размещения информации на сервере, постоянно находящемся в сети (обычно Интернет). Хостингом также называется услуга по размещению оборудования клиента на территории провайдера с обеспечением подключения его к каналам связи с высокой пропускной способностью (колокация, от англ. collocation).

Лично у меня первые сайты были на narod.ru и другие бесплатные хостинги.

Бесплатный хостинг хорош, тем что он бесплатен, и если вы хотите попробовать создать сайт и изучить структуру управления сайтом, основы html это то что вам нужно. Второе если вы не хотите затрачивать деньги.

Платный хостинг, имеет массу преимуществ по сравнению с бесплатным.

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

-профессиональное оборудование которое доступно 24 часа в сутки.

-классифицированная поддержка, при возникновении проблем.

-и многое другое.

Мой выбор остановился на хостинге majordomo.ru, по приглашению друга. Пользуюсь не первый год, цены устраивают, работает 24 часа, тех. поддержка очень дружественная даже поможет решить задачи не связанные с ними.

Кто хоть опробовать хостинг прилагает промокод: BHR44203 (указать при регистраций, на счет будет получен бонус в размере 150 рублей.)

Продолжение следует :)

Моя жизнь на ФПИ и рядом

to blog or not to blog
Как то на данном сайте началось всё с тематических блогов… Но как же на счет личных?
Вот я решил, что раз уж у меня началась уже четвертая жизнь, то уж я постараюсь полноценно её тут прожить :)
Почему четвертая, а вот почему:
— первая была в далеком таежном городе, где я был школьником, ездил на Буране и гонял на Обь-М на двух Вихрях, ловил сетями стерлядь и кормил комаров, занимался зимней рыбалкой и охотой, встречал рассвет на кроне кедра, сбрасывая огромные шишки вниз…
— вторая была во времена моей службы в армии, в РВСН (14 лет)
— третья уже в МВД (8)
— и вот я тут :), чему и рад, был рекрутирован на 22 года и вернулся так сказать «к себе» — в том смысле, что еще в школе стал заниматься алгоритмизацией, сначала в машинных кодах на МК-61, потом уже на Ямахе какой-то на Бейсике дошел до написания шахматной программы, где фигуры отображались Спрайтами, перешагнул через Спектрумы с магнитными лентами и всякие специализированные вычислители, но работа моя не была связана с моим хобби и только теперь…
А тут я буду общаться — о студентах на занятиях на Кафедре ИС, об организации учебного процесса, о моих требованиях к уровню подготовленности студента, о моем отношении к факультету и людях на нем, о моих впечатлениях. Видимо будут фото и видео :)

Ненормальное программирование (cерия 1). Проверка на нечетность

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

Казалось бы, нет ничего проще, чем проверить остаток от деления на 2, но не тут-то было. Мы провели серию опытов, в которых сравнили 3 алгоритма проверки числа на нечетность:

  1. Собственно, проверка остатка от деления на 2.
  2. Побитовая конъюнкция исходного числа и единицы (в случае, если в результате получим единицу, то исходное число является нечетным).
  3. Побитовый сдвиг исходного числа на 1 бит вправо и на 1 бит влево (в случае, если число при этом изменится, то оно нечетное).

Помимо этого, для компиляторов Delphi и FPC проверялось использование стандартной функции Odd из модуля System.

Тестирование проводилось с использованием 4 компиляторов:

  • C++/CLI (Visual Studio 2010, .NET Framework 4.0)
  • C++ (Qt 4.7)
  • Delphi (Embarcadero Delphi 2010 Architect)
  • FPC (Free Pascal 2.4)

на следующей машине:

  • Intel Core 2 Duo E7500 с частотой 2,93 ГГц
  • 2 Гбайт оперативной памяти
  • под управлением ОС Microsoft Windows XP Service Pack 3

Тестирование производилось в 10 заходов при проверке по 1 млрд. значений в каждом. Все результаты даны в миллисекундах.

Таблица результатов C++/CLI
Таблица результатов C++ (Qt)
Таблица результатов Delphi 2010
Таблица результатов Free Pascal
Ну и те же самые результаты в графическом представлении:

График результатов C++/CLI
График результатов C++ (Qt)
График результатов Delphi 2010
График результатов Free Pascal
Даже при беглом анализе полученных данных становится понятно, что широко используемый алгоритм проверки остатка от деления на 2 является далеко не самым быстрым.

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

Победителем у нас сегодня оказывается Delphi 2010 с ее результатом в 2,5 секунды. Аутсайдером же становится C++/CLI с результатом работы алгоритма с использованием сдвигов более 31,5 секунд.

На сегодня это все. Старайтесь писать быстрый код… ;)

Другие сайты о ПГСХА

Привет всем, кто сейчас это читает! Захотелось мне собрать коллекцию ссылок на другие сайты, так или иначе связанные с нашей академией. Кто что знает интересного — пишите в комментариях. Интересуют как приличные неофициальные сайты факультетов и групп, так и открытые активные группы в социальных сетях. Все они будут размещены на отдельной странице, а самые достойные (на мой взгляд) еще и попадут в DMOZ:
www.dmoz.org/World/Russian/Страны_и_регионы/Европа/Россия/Субъекты_Федерации/Пермский_край/Пермь/Образование/Высшее/Академии/Пермская_государственная_сельскохозяйственная_академия/

Qg, или К чему может привести безделье

Летом было такое время, когда работы особо не хватало, а грузить чем-то мозг хотелось, что приводило к непредсказуемым последствиям. Одним из таких «последствий» является язык программирования Qg, который был сработан за пару недель.

Qg 0.1 для Linux

Дистрибутивы интерпретатора для разных ОС (о даже как мозг закрутило) можно скачать тут:


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

В комплекте с интерпретатором имеется пара написанных на Qg программ (конечно, «Hello, World!», а также программа перемножения двух чисел), поэтому можно посмотреть примерно, как там что устроено.

Невидимые виртуальные машины

Ни для кого не секрет, что такое виртуальная машина и для чего она используется. Одним из способов использования возможностей виртуализации является создание виртуальных серверов, для чего бы то ни было.
 
Преимущества такого решения перед тем, чтобы использовать в роли сервера собственную реальную машину, в принципе, очевидны:
  • простое распределение аппаратных ресурсов между несколькими серверами (если оно, конечно, нужно);
  • независимость одного виртуального сервера от другого;
  • повышение безопасности (ведь даже если кто-то что-то взломает и получит доступ к Вашему «серверу», то реальная машина затронута не будет);
  • повышение надежности (вместо того, чтобы создавать ежедневных бэкап данных, конфигураций и различных файлов, достаточно создать снапшот и жить спокойно, ведь при какой-то поломке можно будет мгновенно вернуться назад).
 
Собственно именно на такой виртуальной машине с использованием Oracle VM VirtualBox 4.2 и запущен сервер с Contester 2.4, про который упоминал в комментариях в соседнему топику.
 
Не буду рассказывать, как создавать или настраивать виртуальные машины, это, скорее всего, умеют делать уже даже дети. Сегодня затрону несколько другую сторону, которая тоже проста, но не столь очевидна, а точнее совсем не видна.
 
Любой сервер должен работать постоянно (ну или хотя бы большую часть времени), а это значит, что на вашем рабочем столе постоянно должно висеть окно виртуальной машины? Согласитесь, это, по меньшей мере, неудобно и хочется избавиться от этого. Сделать это совсем просто:
  1. Завершаем работу виртуальной машины (или сохраняем ее состояние).
  2. Запускаем утилиту командной строки VBoxManage, которая лежит в папке с установленным VirtualBox’ом, со следующими параметрами:
    VBoxManage startvm "<наименование_машины>" --type headless

 
И все. Виртуальная машина будет запущена, но на экране не появится. Таким образом, данную команду запуска виртуальной машины можно добавить в список автозагрузки реальной системы, чтобы все необходимые сервера запускались уже при входе.
 
Для управления работой запущенной в фоне виртуальной машины можно использовать различные параметры утилиты VBoxManage, а можно предварительно настроить что-то вроде сервера RDP, VNC или SSH, чтобы управлять виртуальной машиной удаленно (что значительно удобнее :) ).