INFOMAN брой 8
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ÞÛÛÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛ ÛÛÛÛÛ ÞÛÛ ÛÛÝ ÞÛÛÝ ÞÛ ÛÝ
ÞÛ ÞÛÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛÞÛ ÛÝÛÝ ÞÛ ÛÝ ÞÛÛÝ ÛÝ
ÞÛ ÞÛ ÛÝ ÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÜÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÛÝ
ÞÛ ÞÛ ÛÝÛÝ ÞÛÛÛÛ ÞÛ ÛÝ ÞÛ ÞÛÝ ÛÝ ÞÛÛÛÛÛÛÝ ÞÛ ÛÝÛÝ
ÞÛ ÞÛ ÛÛÝ ÞÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÛÝ
ÞÛÛÛ ÞÛ ÛÝ ÞÛ ÛÛÛÛÛ ÞÛ ÛÝ ÞÛ ÛÝ ÞÛ ÛÝ
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
ЕДИНСТЕНОТО В БЪЛГАРИЯ СПИСАНИЕ ЗА ЗАДАЧИ ПО ИНФОРМАТИКА
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
E-mail: ÜÜ Home Page:
infoman@musala.com Û Û http://infoman.musala.com/
брой 7 Ноември, 1998 ßÜÜß (c) INFOMAN Team Bulgaria
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
* web-сървъра на INFOMAN (www.infoman.org) временно не работи
СЪДЪРЖАНИЕ
ÄÄÄÄÄÄÄÄÄÄÄÄ
ТЕМА АВТОР
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄ
1. Intro. Наставления към младите информатици (Infoman)
2. Транзитивно ориентируеми графи (Васил Поповски)
3. Задача 1 от конкурса на Computer News с награда $1000 (Svetlin Nakov)
4. Информация за предстоящи състезания (Infoman)
5. Заключение (Infoman)
Наставления към младите информатици (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Здравейте информатици! Изминаха почти 2 месеца от последния излязъл брой
на INFOMAN. През това време преминаха финалните кръгове на два сериозни бъл-
гарски конкурса по информатика - конкурса на вестник ComputerNews с награда
$1000 в брой и традиционният конкурс на списание PC Magazine/Bulgaria с го-
леми награди (компютър, скенер, хардуер и книги). В този брой на списанието
ще намерите решения на някои от задачите от тези два конкурса, а в следващи-
те броеве и решения на останалите задачи. Не може да не се отбележи, че и в
двата конкурса имаше сериозни издънки. До финалния кръг на конкурса на спи-
PC Magazine / Bulgaria не бяха допуснати най-добрите български информатици,
които многократно са показвали успехи по международни и други състезания,но
на тяхно място в челната десятка за борбата за голямата награда - компютър
бяха "се каласирали" хора, които меко казано си нямат понятие от задачи по
информатика. Показателно е, че от 10 човека работеща програма за лесната за-
дача, която бе дадена на финалния кръг, бяха съставили само 4 човека. Усло-
вие на задачата и решението й ще намерите в следващия брой на INFOMAN. Няма
причина, поради която на задочния кръг да се дават първо толкова лесни зада-
чи, и второ няма причина поради която очевидно правилните и ефективни реше-
ния на задачите, изпратени от недопуснатите до участие кадърни информатици,
да се игнорират. Със сигурност някой не си беше свършил работата, но мнение-
то на информатическия елит е, че този конкурс беше тотално провелен и опоро-
чен. Втората издънка стана с конкурса на вестник ComputerNews. Поради някак-
ви причини организаторите на конкурса бяха решили, че за да допуснат когото
и да било до участие в конкурса,той задължително трябва да има абонамент за
ComputerNews на негово име до края на годината, което за участниците е свър-
зано с немалки разходи. Поради тази причина се откзаха много информатици,же-
лаещи да участват. Все пак не може да се отрече, че двете задачи от първи
задочен кръг бяха много хубави и подходящи.Финалните кръгове и на двата кон-
курса бяха проведени на едно добро ниво и бяха дадени подходящи задачи.
Поради получените в редакцията материали, които не са подходящи за публи-
куване в списанието поради неефективните алгоритми използвани в тях,редакци-
ята на INFOMAN си прави извода, че голяма част от нашите читатели не са на-
ясно с основните компютърни алгоритми като сортиране, генериране на комбина-
торни обекти, алгоритми за графи, ОЦЕНЯВАНЕ НА СЛОЖНОСТТА НА АЛГОРИТМИТЕ и
т.н.). В един от изпратените до нас материали дори беше предложен алгоритъм
за генериране на пермутации на N елемента със сложност N^N. За всеки който
някога е отварял книжка по алгоритми е ясно, че това е доста неефективно.
Ето защо редакцията на списание INFOMAN предлага на всички, които се ин-
тересуват сериозно от алгоритми и решаване на задачи по информатика да наме-
рят начин да се сдобият и да работят със следната литература:
1. Преслав Наков - "Основи на компютърните алгоритми /част 1 и 2/"
2. Софийски Университет - "Задачи по програмиране с решения на Паскал"
3. University of Monreal, Canada - "Algorithmics"
4. MIT Press - "Introduction to Algorithms", "MIT Algorithms"
5. Robert Sedgewick - "Algorithms in C++"
6. Липски - "Комбинаторика для програмистов"
7. Димитър Шишков - "Структури от данни"
Някои от тези книги е малко вероятно да се намерят по каквито и да било биб-
лиотеки в България. Книгата (1) може да се намери по книжарниците и книжни-
те борси. Книгите (3), (4) и (5) могат да се закупят on-line от световните
магазини за литература (като amazon.com и barnesandnoble.com). Учебникът (7)
може да се намери в Софийския Университет,докато (2) и (6) се намират много
трудно.
Разбира се има и още много книжки, които са доста хубави и полезни за на-
чинаещи и напреднали, но посочените тук са най-основните и горещо се препо-
ръчват на читателите на INFOMAN.
Относно получените неподходящи материали, редакцията на INFOMAN ги отхвър-
ля не за да обезсърчи авторите им, като ги опреква, че не са достатъчно доб-
ри, а защото не е полезно в INFOMAN да се публикуват материали, от които чо-
век може да се научи на неправилни неща. INFOMAN приема всякакви материали
от всеки, но стига те да са на едно добро ниво, и да съдържат полезна инфор-
мация не за начинаещи, а за напреднали информатици.
Транзитивно ориентируеми графи (Васил Поповски)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Предлагам ви една интересна и малко известна задача за транзитивна ориен-
тируемост на неориентиран граф - tro.pas.
Задача 1 от конкурса на Computer News с награда $1000 (Svetlin Nakov)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ
Задача 1 от конкурса на вестник ComputerNews за голямата награда $1000 е
една трудна задача, която може да се реши само с ефективен алгоритъм и доб-
ре подбрани структури от данни. Решението е във файла files.pas
Информация за предстоящи състезания (Infoman)
ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
ОТНОСНО ЗИМНИТЕ МАТЕМАТИЧЕСКИ ПРАЗНИЦИ
Зимните математически празници ще бъдат на 29,30,31 януари, 1999 година.
За пръв път в историята на това елитно състезание се внасят коренни промени.
По традиция турнирът по информатика за всички възрастови групи на Зимните
математичски празници е отборен. Тай като съществува световно отборно състе-
зание с традиции - световното студентско състезание на ACM, организаторите
тази година считат за полезно да проведат и нашия отборен турнир за ученици
по правилата на това състезание. Най-важните аспекти на тези правила са:
5 часа за работа. На въпросите се отговаря с "ДА", "НЕ" и "БЕЗ ОТРГОВОР".
Могат да се ползват всякакви книги, но не и дискети и собствени сорсове. Пи-
ше се на Pascal или C/C++. Имената на файловете и форматът на входа и изхо-
да трябва да са спазени абсолютно точно. При оценяване се гледа само изпъл-
нимия файл. Когато някой отбор реши някоя задача, я предава веднага.Времето
на предаване има значение. Решенията се проверяват от журито веднага с тес-
тове и на отбора се съобщава дали решението е правилно. Ако решението не е
правилно, на отбора се съобщава вероятната причина за грешка (грешка при из-
пълнение - ПРЕКЪСВАНЕ; изтичане на времето - ВРЕМЕ; грешен резултат - ГРЕ-
ШКА; неправилен формат - ФОРМАТ). Класирането е по броя на правилно решени-
те задачи. При равен брой се гледа сумарното време на предаване на задачите.
Зимните математически празници за възрастовата група 8-9 и 10-11 клас ще се
проведат таги година в град Варна на 29, 30 и 31 януари 1999.
НАЦИОНАЛЕН КОНКУРС ЗА ПРОГРАМНИ ПРОДУКТИ
ЗАДАНИЕ ЗА РАЗРАБОТКА НА ПРОГРАМЕН ПРОДУКТ
за 1998-1999 година
Трябва да се отбележи, че този конкурс се провежда от няколко години и
по традиция всяка година фондация "Еврика" дава на победителя голямата наг-
рада - стипендия в продължение на цялото обучение - 30% от минималната ра-
ботна заплата за периода на обучение в училище и 50% от минималната работ-
на заплата в периода на обучение във ВУЗ. Повече информация за конкурса за
разработка на програмни продукти можете да получите от регионалния център
за работа с деца - ЦРД (бившия пионерски дом) и от ръководителите на кръжо-
ците по информатика и програмиране на ЦУНТТ (център за ученическо научно и
техническо творчество) към регионалния ЦРД. Поставената тема трябва да се
разработи от ученика и да се предаде на ръководителя до 20 май 1999. Финал-
ния кръг на конкурса ще се проведе както всяка година в края на месец юни
и ще бъде присъствен. На него всеки участник лично ще си защитава разработ-
ката. Ето и условието на заданието:
Мрежа ще наричаме двойката (N,L), където N е съвкупност от обекти, а
L - съвкупността от всички връзки между обектите. Всяка връзка отговаря на
двойка обекти (свързва 2 обекта). Между два обекта може да няма връзка или
да има една или повече връзки. Обектите (елементите на N) ще наричаме въз-
ли на мрежата.
Да приемем, че на всеки възел се приписва някакво име или номер, за
да можем да ги различаваме. Ако между два възела има повече от една връзка,
тези връзки също ще снабдим с имена или номера, по същата причина.
Мрежите често се използват като структура от данни за моделиране на
реално съществуващи или проектни системи от най-различни видове. При това
обикновено се оказва необходимо към възлите и/или връзките между тях да се
прикрепва и друга информация.
Например можем да приемем, че възлите съответстват на населени места
от даден регион, и тогава данни за населените места могат да се прикрепват
към възлите ; тогава пък връзките могат да съответстват на пътищата между
населените места и към тях да се прикрепват данни за дължината, качеството,
пропускателната способност на всеки път. Друг пример:възлите са абонати на
съобщителна мрежа - телефонна централа, радиорелейна мрежа и т.н. - а връз-
ките между тях, където ги има са съобщителните линии. Съответните допълни-
телни данни тогава са други.
ЗАДАНИЕ:
1. Проучете различни приложения на мрежи за моделиране на системи.
2. Проучете различни алгоритми за решаване на задачи върху мрежи, на-
пример такива за намиране на пътища (последователност от връзки) между въз-
ли, определяне дали между два възела изобщо съществува път,избиране на под-
ходяща в даден смисъл подмрежа на зададена мрежа и т.н. Разгледайте мрежи
с двупосочни и еднопосочни връзки (ако от един възел към другия има връзка,
не непременно има такава и от втория към първия, а ако има - не непременно
е същата).
3. Проектирайте и съставете програма за компютри от типа IBM PC, коя-
то използва мрежа за моделиране на някоя конкретно избрана от вас система.
Програмата трябва да позволява въвеждане и изменяне на данните, които зада-
ват мрежата, показване на мрежата в подходящ вид на екрана на компютъра и
решаване на различни задачи, свързани с мрежата.
4. В писмения материал към разработката обосновете избора на модели-
раната система, нейните свойства и какви задачи за тази система решава ва-
шата програма. Ако в програмата са реализирани интересни, оригинални ваши
алгоритми, опишете ги. Ако са използвани известни алгоритми за типови зада-
чи върху мрежи - посочете кои именно.
Освен програмата разработчикът трябва да представи и подробни указа-
ния за нейното ползване и за нейното устройство. Наред с другото,трябва да
бъде ясно посочено какви готови инструментални средства са използвани при
разработката на програмата.
ДРУГИ СЪСТЕЗАНИЯ
Задочния конкурс по информатика на списание Computer продължава. Услови-
ята можете да откриете на страниците на списанието или на адрес http://www.
math.acad.bg/~keleved/eureka.html.
Наближават първите кръгове на олимпиадата по информатика за средношколци.
По традиция те се провеждат в края на февруари. Все още имате време за под-
готовка. Не пропускайте шанса си!
Заключение (Infoman)
ÄÄÄÄÄÄÄÄÄÄ ÄÄÄÄÄÄÄÄÄ
Редакцията на INFOMAN моли всички абонати да изпращат материали за списа-
нието. Умоляват се всички читетели да изпращат съвети, статии или решени за-
дачи с описание на използваните алгоритми и примерна програма. Ако някой чи-
тател има повече информация за предстоящи състезания или информация за дру-
ги конкурси и състезания, молим да ни я изпрати, за да я публикуваме. Не за-
бравяйте, че списанието е за напреднали информатици и затова статии, подхо-
дящи за начинаещи няма да бъдат публикувани. Освен това материали, които да-
ват грешен или неефективен начин за решаване на каквито и да било задачи,съ-
що няма да се публикуват.
С повечето от читетелите ще се видим на живо на 30 януари във Варна.
Успех!
File List:
tro.pas
infoman8.txt
files.pas