Month: May 2005

Categories
разказвам

животен стек

Току що привърших задачите си за практикума на първокурсниците по-късно на обед. Условията станаха весели. Ще ги пусна след като мине. Засега ще кажа само, че бях повлиян от мечешката история от днес, на която за съжаление не присъствах, но пък легендите… :)

Та нека поизвадя малко случки от стека. Преди вкъщи беше Дивака. Не знам как се навих изобщо да отида. Впрочем знам – ниикак не ми се прибираше знам, а с някои хора, както и с радио не се спори много успешно :)

Балканджи. Fans. Както се изрази Лина по-рано: получих си дозата. Мдам. Вече нямам нужда от цялата раница хапчета срещу абстиненцията. Концертът си беше много хубав и си поскачахме и попяхме. Стана сериозна тардиция да свирят Поглед повече от веднъж. Харесва ми така. Сребърни ята също много ми харесва.

О, Lessig. За съжаление успях да посетя само последното от всичките му мероприятия, но добри и услужливи хора са записали по-ранните и ще мога да ги гледам като се encode-нат утре. Професорът е невероятен. Презентацията му беше адски изпипана, а той говореше каквото трябва и най-вече както трябва. Леко чувство за хумор. Стабилни доводи. Малко самокритика. Изкефи ме максимално.

Неделя. Олимпиадата във ФМИ. Пет часа, в които умората и следите от недоспиването ми се изпариха тотално. Обичам ги тези преживявания. Този път май се представихме малко по-добре от очакваното (но, можеше и по-добре. Мамка му, как си помислихме, че на онази задача Floyd-а ще е бавен – беше толкова лесна…). След края обаче целия ни МЯО обаче беше труп. Нито знаехме на кое място сме (в последния половин час не се обявява текущото класиране) нито искахме да знаем. Поспорихме малко с Крис и си тръгнахме преди коктейли, закривания и класиранеобявявания. Стефчо ме докара с колата до у нас. Било хубаво с кола…

Събота. Целият ден във ФМИ. Първо едно много продуктивно упражнение с първокурсниците. Даже успях да им разкажа за buffer overflow-и основните неща. Вече ще ползват cin.getline()… Следобяд (даже докъм вечерта) тествахме всички компютри за неделята. Мъка си беше. И нерви. Вируси. Глупаво PC^2. Леко заспали писачи на .bat файлове. Измъкнах се чак към 7 и половина. И вместо да си отида да спя минах да вечерям с Росен. Беше доста въодошевен от лекцията си на M$ деня по-рано и ми говори доста неща (доста от тях интересни), но аз май главно кимах. Май пак не си легнах рано. Даже не помня защо…

На семинарчето в петък ще отделя друга публикацийка. Писана по тъмно по възможност… Защото сега вече не е.

Сигурно съм изпуснал разни неща. Здраве да е. Беше ми приятно да попиша малко.

Лек ден.

Categories
разказвам

купонът2

Spending my time
Watching the days go by…

Неусетно мина една година от миналогодишния рожден ден на Васко. Също толкова неусетно си направих мъничка равносметка, но съм уморен да пиша за нея сега.

За рожденния ден снощи.
Страшно се зарадвах на реакцията на Васко когато му подадох пакетчето с After Eight. И без това си бях в добро настроение вечерта, но това наистина ме накара да се усмихна. Доста по-късно играхме фризби с него в коридора. Музиката в началото не беше съвсем на ниво, но нещата бързо си дойдоха по местата. Е, наложи се и аз малко да dj-ствам, но си заслужаваше жертвата :) Видях много хора, които исках да видя.

Тръгнах си към 6 и половина…

След малко отивам във ФМИ, зареден с много положителна енергия и с малко тъга…

Categories
аз свят

13

Обичам петък, тринадесети.
Особено когато е май. Сигурно защото Васко има рожден ден :)
Нека да ни е жив и здрав. И весел.

Categories
сметачи

рег. изр.

Някои хора обичат честичко да използват регулярни изрази. Аз също съм от тях. Понякога някои от тези хора се сблъскват със следния проблем: какъв би бил регулярен израз, който отговаря на думи несъдържащи в себе си низа баба.

След кратки справки с книги, интернет и perldoc и местни perl гуру-та стана ясно, че лесен начин наистина няма. Набързо обаче се сетих за един труден. Поне на пръв поглед труден.

Всеки регулярен израз описва един език – това е множеството от думи, които на практика този регулярен израз match-ва (български превод?). Всеки език описан с регулярен израз се нарича регулярен език (защо ли…). Езиците породени от крайни автомати се наричат автоматни.

Теорема на Клини: Регулярните езици и автоматните езици съвпадат.

Сега захождаме към съставяне на нашия регулярен израз – опитваме се да си построим краен автомат, който да описва езика, който ние искаме. Тъй като обаче някакво вътрешно чувство ни води, решаваме да си опишем езика, който включва всички думи несъдържащи в себе си ба вместо баба. От втория път успяваме да си построим едно крайно детерминирано автоматче:
Приятен краен автомат
Малка забележка: дискретната математика не вярвам да познава означението ^xyz, но в нашия случай (благодарим на perl) с това чудо означаваме множеството на всички букви от азбуката, без x, y и z.

Сега остава по този автомат да си съставим регулярния израз.
Както доста от доказателствата на теореми от дискретната математика и това на Клини е конструктивно и от него получаваме алгоритъм за намиране на регуларярен израз, съответен да даден краен автомат. Няма да се впускам в подробности. Доказателството, както и алгоритъма ги има във вероятно всеки учебник по дискретна математика. След една-две страници сметки накрая от горния автомат получаваме следния регулярен израз, записан в термините на езика perl:

(([^b]*)|([^b]*b(([^ab][^b]*b)|b)*)|([^b]*b(([^ab][^b]*b)|b)*[^ab][^b]*))

Ето и по-грозна негова версия:

( [^b]* ) |
( [^b]* b ( ( [^ab] [^b]* b ) | b )* ) |
( [^b]* b ( ( [^ab] [^b]* b ) | b )* [^ab] [^b]* )

Това е. Ето тук има примерно скриптче, което използва горния регулярен израз и проверява верността му за всички думи с дължина по-малка или равна на 5 върху азбуката {a,b,c,d}.

П.П. Подозирам, че горният израз може да се поопрости и дължината му да се намали поне наполовина. Спи ми се…
П.П.П. Нищо чудно това да може да се направи и с двадесетинасимволен израз. Не ми пука :)

Categories
свят сметачи

българско състезание

Компанията Tumbleweed организира за първи път турнир по програмиране.

  • Въпреки, че конкурсът е насочен изцяло към българи цялата информация за него е на анлглийски език. Съгласен съм, че всеки информатик трябва да владее този език не много по-зле от C и Perl, но живеем в България все пак. Описанието на проектите също трябва да е на английски. Мда. Част от журито не разбира български език, но аз лично бих предпочел в конкурс, в който могат да участват само български граждани диалогът меду тях и журито да се извършва на официалния в тази страна език. Който е забравил – това е българският.
  • Правилата за участие са единствения документ, който има версия и на български език (подозирам, че по чисто юридически причини…). Ето един немалък цитат от същите тези условия:

    Във връзка с продукта, който подавате като част от конкурса, се задължавате да предоставите на Тамбълуд неизключително, възмездно и валидно за цял свят разрешение да изготвя, продава или използва по друг разрешен от закона начин включения в офертата материал, както и всяка част от него. Неизключителното право, което се предоставя по силата на приетите от вас конкурсни Правила е с десетгодишен срок на валидност, считано от датата на подаване на офертата и се подновява автоматично за допълнителен период от десет години, освен ако не бъде прекратено от вас или Тамбълуид с предизвестие, отправено 30 дни преди изтичане на срока.

    Признавам си – не съм много наясно с някои юридически термини и учтиво ги запитах какво означава неизключително и възмезднорезрешение и какво мога да правя с написаното от мен след като им го изпратя. Получих следния отговор:

    Hello Nikolay,
    We would like to thank you for your interest in the programming contest. Please, find below the answers to your questions:

    >> Включва ли в себе си той възможността да ползвам, променям и
    >> разпространявам свободно продукта, който съм изготвил?

    With regard to an entry you submit as part of the Contest, you grant Tumbleweed a worldwide, fully paid-up, non-exclusive license to make, sell, or use in any other way not prohibited by law the work incorporated therein, as well as any part of it, which means that you can not use, change or distribute the submitted product.

    Best regards,
    Contest-Sofia

    Върнаха ми го с леко развален от encoding-и subject, но сигурно аз съм си виновен след като изпращам писма със subject в windows-1251. Както се забелязва – върнаха ми го на английски език. Наглост.

    Иначе очаквах, че няма да мога разпространявам и използвам свободно творението си. Разбираемо е…

Дали скоро няма да започнат да се появяват повечко подобни състезания. Не цената на, на пръв поглед скъпи награди, се получават доста разнородни и свежи идеи и много, много код, в по-голямата си част работещ и качествен.