INFOMAN брой 15
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ÞÛÛÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛ ÛÛÛÛÛ ÞÛÛ ÛÛÝ ÞÛÛÝ ÞÛ ÛÝ
ÞÛ ÞÛÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛÞÛ ÛÝÛÝ ÞÛ ÛÝ ÞÛÛÝ ÛÝ
ÞÛ ÞÛ ÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÜÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÛÝ
ÞÛ ÞÛ ÛÝÛÝ ÞÛÛÛÛ ÞÛ ÛÝ ÞÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛÛÝ ÞÛ ÛÝÛÝ
ÞÛ ÞÛ ÛÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÛÝ
ÞÛÛÛ ÞÛ ÛÝ ÞÛ ÛÛÛÛÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ЕДИНСТЕНОТО В БЪЛГАРИЯ СПИСАНИЕ ЗА ЗАДАЧИ ПО ИНФОРМАТИКА
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
E-mail: Ü ÜÜÜÜ Home Page:
infoman@musala.com ßÛ ÛÜÜ http://infoman.musala.com/
брой 15 - Септември, 1999 Û ßÜÜß (c) INFOMAN Team Bulgaria
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
СЪДЪРЖАНИЕ
ÄÄÄÄÄÄÄÄÄÄÄÄ
ТЕМА АВТОР
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
1. Ще го има ли INFOMAN - Интро (Infoman)
2. Подборният кръг - ден 1, задача 2 Васил Поповски
3. Подборният кръг - ден 2, задача 1 Светлин Наков
4. Подборният кръг - ден 2, задача 2 Петър Петров
5. Подборният кръг - ден 2, задача 3 Васил Поповски
6. Задачата за таксиметровия шьофьор Преслав Наков
7. N-свързаност на граф Star Gruhtar
8. Малка задачка - за фалшивите монети Преслав Наков
9. Заключение (Infoman)
Ще го има ли INFOMAN - Интро (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Здравейте инфомани! Да, знаем, че този брой невероятно закъснява, но
за това си има причини. Списание INFOMAN трябваше да предоставя на своите
читатели решенията на всички задачи от всички състезания, но това вече не е
по силите на редакцията. Причината е проста. Тези, които досега движеха спи-
санието, вече или нямат време, или не се занимават с информатика, пожене са
се комерсиализирали. Така е, скъпи читатели, трябва да се работи. В качест-
вата си на главен редактор на списанието, аз Светлин Наков искам да ви бла-
годаря за съдействието, което указвахте за издаването на списанието.За съжа-
ление, то или повече няма да излиза, или ще излиза много рядко и няма да да-
ва решения на всички задачи от всички конкурси, състезания и олимпиади, за-
щото просто няма кой да изпраща решения, а в редакцията всички работят и ве-
че почти никой няма време да решава задачите от състезанията и да ги описва
подробно и в достъпен вид. Затова ако някой от вас, които четете това списа-
ние, проявява интерес да стане главен редактор, молим да изпрати едно писмо
до редакцията. Много ще се радваме списанието да продължи да излиза отново
редовно и с пълни решения на задачите от всички по-важни български състеза-
ния за ученици и студенти. Ако някой проявява интерес към спонсориране на
списанието, може да се свърже също с нас. Ние сме сигурни,че ако се намерят
средства за издавването на INFOMAN, никой от редакцията няма да спре да пи-
ше статии. И така, все пак се надяваме, че ще има поне още два броя - за ре-
шенията на задачите от балканиадата в Гърция и за решенията на задачите от
международната олимпиада в Турция.
Най-сетне, имаме решения на всикчи задачи от подборния кръг на олимпиа-
дата, провел се през май в София, 1999 г.Смятаме задачите за важни и затова
се постарахме да ги решим и опишем. Специални благодарности на Васил Попов-
ски за съдействието.
Така е, всичко хубаво има край, остаряваме бавно, неосетно почти, вече
не пишем на Паскал и C за DOS, а на Java, Oracle Developer 2000, Visual C++,
Pearl, Visual Basic, PowerBuilder, Access и т.н. Няма време за задачки, ня-
ма време и за други програмки... Така е, когато си студент в България.
Подборният кръг - ден 1, задача 2 Васил Поповски
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Нашият редовен читател Васил Поповски ни изпрати едно добро решение на
задача 2 от ден 1 от подборния кръг по информатика - София '99. Въпреки доб-
рото описание на алгоритъма, от редакцията си позволяваме да не се съгласим
с терминологията, която е използвал авторът. За нас (както и в повечето кни-
ги е дефинирано) изразът "минимално доминиращо множество от върхове в граф"
означава множество от върхове в насочен граф, такова, че до всеки един връх
в графа да има насочен път от някой връх от това доминиращо множество и вър-
ховоте в него да са минимален брой. Това, което се търси в настоящата зада-
ча (Фирмени бази) от олимпиадата е дефинирано като NP-пълен проблем в теори-
ята на графите и се нарича "вершинно покритие на неориентиран граф". Въпре-
ки тази неточност, програмата е правилна и преминава успешно всичките тесто-
ве на журито. Узловието на задачата, описанието на алгоритъма и решение на
C++ ще намерите във файла BAS.DOC (във Word 6.0 формат).
Подборният кръг - ден 2, задача 1 Светлин Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Задачата за плодовете от втория ден финалния кръг на олимпиадата беше
единствената класическа задача, т.е. задача, която може да се намери решена
в някои книги и учебници по информатика. Въпреки, че е NP-пълна за нея съще-
ствуват няколко принципно различни, но бързи алгоритъма, като всеки от тях
използва динамично оптимиране. Тази задача е частен случай на известната це-
лочислена задача за раницата (0-1 раница). Смятам, че ще интересно да разяс-
ним разликата между NP-пълни задачи и задачи, които не се решават за земно
време. Повечето млади информатици смятат, че когато един информатически про-
блем е дефиниран като NP-пълен (NP-complete), то за него не съществува бърз
алгоритъм, който може да го реши за разумно време (да кажем за 1 минута).То-
ва не е точно така. За дадения проблем не съществува полиномиален алгоритъм,
т.е. алгоритъм, скоростта на който може да се изрази чрез полином на големи-
ната (броя) на входни данни, но това не означава, че не съществува неполино-
миален, но бърз и ефективен алгоритъм. В нашия случай с плодовете,сложност-
та на алгоритъма е от порадъка на N*K,където N е бротя плодове, а K е броят
различни възможни тегла на плодовете (максималното тегло на плод).При някак-
ви ограничения на числото K моежм да получим алгоритъм, решава задачата със
сложност N*K и той ще е достатъчно бърз, за да реши задачата за разумно вре-
ме, но все пак той не може да се приеме за полиномиален, защото K не зависи
от количеството на входните данни (в случая това е броя предмети - N), а от
самите тях, т.е. не съществува полином, който може да опише сложността на
алгоритъма относно размера на входа N. За общия случай не съществува полино-
миален алгоритъм за тази задача, защото теглата на плодовете всъщност са це-
ли числа и те не зависят от N. Въпреки това понеже работим с ограничение на
теглата на плодовете до 1 кг (1000 грама), можем да дефинираме като констан-
та K=1000 и да получим алгоритъм, алгоритъм работещ със сложност 1000*N,т.е.
линеен полиномиален алгоритъм. Получи се така, че хем задачата е NP-пълна,
хем може да се реши с полиномиален алгоритъм. Второто е вярно,обаче само ко-
гато можем да ограничим максималния по големина елемент от входа с някакво
число K, което в общия случай не е известно. Внимавайте! Много есктремални
комбинаторни задачи могат да се решат ефективно с динамично оптимиране, въп-
реки че са дефинирани като NP-пълни в литературата. По мои лични наблюдения
това важи в по-голяма степен в задачи свързани с намиране на някакви подмно-
жества и по-малко при задачи с графи, които обикновено ако са NP-пълни, то-
ва означава,че се решават с някакъв изчерпващ алгоритъм и бърз алгоритъм ня-
ма. Условието и едно добро решение на задача 1 от ден 2 ще намерите във фай-
ла fruits.pas.
Подборният кръг - ден 2, задача 2 Петър Петров
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄ
Някои я смятат за лесна, други за не чак толкова, но задачата за звез-
дата от втория ден на финалния кръг на олимпиадата по информатика беше опре-
делено най-нестандартната. Решението на Петър Петров е правилно и добре ар-
гументирано - STAR.DOC.
Подборният кръг - ден 2, задача 3 Васил Поповски
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Въпреки че не беше най-трудната, задачата за звездата от втория ден на
олимпиадата по информатика беше една от най-дългите и времеотнемащи задачи.
Предлагаме ви едно елегантно решение на Васил Поповски - MOBILE.DOC.
Задачата за таксиметровия шьофьор Преслав Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Предлагам ви една известна задача, която скоро отново се беше появила
на едно състезание, поради което намирам за необходимо да я обясня на чита-
телите на INFOMAN, за да разберат в дълбочина този тип задачи. Разгледайте
файла TAKSI.DOC.
N-свързаност на граф Star Gruhtar
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄ
Тази задача илюстрира мощността на алгоритъма за намиране на максимален
поток в граф. Задачата е от известната книга на MIT - "Introduction to algo-
rithms", а решението е на нашият редовен читател и автор на интерсни статии
Star Gruhtar. Всичко се съдържа във файла N-CONNECT.PAS
Малка задачка - за фалшивите монети Преслав Наков
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
Можете да приемете тази задача и като задача по логика, но въпреки това
тя е сериозна е даже е давана на състезание по информатика.Погледнете файла
FALSHIVI.DOC.
Заключение (Infoman)
ÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Няма нужда отново да ви напомняме да изпращате статии и материали за
списанието, че имаме нужда от вашата подкрапа също ви е известно, читатели
наши, но искам да ви кажа че се надявам някой да продължи да издава INFOMAN
след като сегашната му редакция вече няма възможност да се занимава с него.
В България винаги е имало и пак ще има способни информатици, програмисти и
хакери. Не забравяйте най-важното - че информатиката е в основата на всички
компютърни науки и че програмист, който не е информатик е просто занаятчия.
Благодарим ви за отделеното време. Надяваме се нашето списание наис-
тина да ви е полезно.
Желем ви успехи.
INFOMAN
File List:
image4.gif
falshivi.html
fruits.pas
image2.gif
image3.gif
bas.html
image5.gif
infoman15.txt
mobile.html
n-conect.pas
star.html
taksi.html