Глава 0
Компютърна информатика, алгоритми, програмиране

“Think of all the psychic energy expended in seeking a fundamental distinction between ‘algorithm’ and ‘program'”.

~ Epigrams in Programming

Според една добре известна теория [Adams-1980] планетата Земя представлява един огромен компютър, построен с единствената цел да разкрие въпроса за “смисъла на живота, Вселената и всичко останало”. Тази щура мисъл, родила се в главата на Дъглас Адамс още през 1975 (докато се е излежавал в тръстиката), може би не е най-точното описание на състоянието на нещата, но, както и други негови “хипотези”, проектира една обща допирателна между минало, настояще и бъдеще. Ще отбележим, че построяването на обща допирателна през повече от два, и то не толкова закръглени, обекта, каквито са състоянията на времето, е една доста трудна и често нерешима задача.

Трудно е да се избегнат клишетата, когато трябва да се описва ефектът, който ком­пю­тър­ните системи и технологии оказват върху съвременното общество. Забележителните им темпове на развитие оставят дълбока следа в организационните и оперативните процеси в ин­дустрията, бизнеса, управлението и обучението. Целта на настоящата уводна глава не е разсъждения върху това как след 10 години компютрите ще се хранят и [цензурирано, ред.] вместо нас, а да запознае накратко читателя с аспектите на съвременните компютърни тех­но­ло­гии, както и да го подготви за света на компютърните алгоритми, който ще изследваме на стра­ниците на тази книга.

В основата на развитието на компютърните технологии стои компютърната ин­фор­ма­ти­ка — термин, който многократно ще използваме по-нататък. Ще отбележим, че в английски език (особено в американски английски) се предпочита използването на термина computer science, който се превежда на български буквално като компютърна наука. В Европа има по-различно разбиране, например: в бившия социалистически блок (руски и български: информатика), във Франция (френски: informatique), Германия (немски: informatik) и др. Тук свободно циркулира и английското название informatics — вероятно първоначално появило се като буквален превод някъде извън Великобритания, но с тенденцията да се наложи. Въпреки това, informatics е силно дискриминирано: липсва в повечето речници на съвременния английски език, университетската специалност във Великобритания най-често се нарича computer science (макар напоследък да се използва и информатика), дори вградената в Microsoft Word стандартна програма за правописна корекция в момента систематично подчертава с червено тази дума. Въпреки това понятието постепенно се налага и на международно ниво: така например международната олимпиада е по информатика (англ. International Olympiad in Informatics), така е и с Балканиадата (англ. Balkan Olympiad in Informatics). В САЩ обаче про­дъл­жават категорично да отричат правото му на съществуване… В основата на понятието ин­фор­матика стои осъзнатият факт, че всъщност става въпрос за по-широкия процес на об­ра­бот­ва­не на информация, докато от американска гледна точка е важна не информацията, а кон­крет­но­то средство за обработката й — компютърът.

0.1. Перспективни направления в компютърната информатика

Областите, в които има поле за по-нататъшно развитие и научно-изследователска дей­ност през следващото десетилетие, могат условно да бъдат разграничени както на фигура 0.1. (Защо са оставени празни полета? Какво би могло да стои там?)

Фигура 0.1. Основни области на компютърната информатика.

0.1.1. Връзка компютър-потребител

Когато се използва добре известното клише “компютрите са навсякъде”, в най-голяма сте­­­пен се има предвид връзката между компютър и потребител. Макар за момента да не съ­щес­твува общоприета дефиниция какво обхваща, това е една от най-важните области на ком­пю­тър­ната информатика. Жизнено необходимо е по-нататъшното й развитие, тъй като нас­то­я­щи­те ограничения при това взаимодействие се чувстват осезателно. Съвсем естествено е же­ла­ни­е­то за много по-интерактивно взаимодействие с компютъра: да може да разбира печатен и ръ­ко­пи­сен текст, човешка реч и жестове, както и да изразява свои собствени идеи в общуването си с нас. В момента възможностите за подобно “общуване” са тромави, неудобни или най-малкото бавни. Въпреки някои опити за подобрения в тази насока засега практиката определя ком­пю­тър­ните сис­те­ми като “слепи” и “глухи”.

Компютърна графика

Може би най-разпространеното схващане за компютърна графика е: “почти всичко, свър­з­ано с компютрите, което не е текст и звук”. На практика става въпрос за сериозна научна об­ласт, свързана с редица традиционни математически науки като: линейна алгебра, аналитична гео­ме­т­рия, диферен­ци­ал­на геометрия, диференциални уравнения, (комплексен) анализ и други, както и с мно­жество фун­даментални компютърни алгоритми. Целите, поставени в тази насока, включват раз­витието и експлоатацията на графични хардуерни и софтуерни системи, както и съставянето на нови методи за моделиране, рендериране, симулиране, визуализиране и др. (виж фигури 0.1.1а., 0.1.1б. и 0.1.1в.).

Фигура 0.1.1а. Рендериране: визуализиране на модели на обекти така, че да изглеждат триизмерни.

Фигура 0.1.1б. Някои от най-често използваните техники за засилване на реализма на компютърни графични обекти: прозрачност, отражение и сянка.

Фигура 0.1.1в. Проследяване на лъча, светлоусещане и светлоотражение.

0.1.2. Компютърни комуникации и сигурност

Компютърната комуникация е процес, при който се създават, разменят и получават дан­ни и информация, като се използват компютърни системи, свързани в мрежа. Например вза­имо­дейс­твията между различни “локални” изчислителни процеси, компютърни конференции, електронни бюлетини, глобалната мрежа Интернет (във всички аспекти, включително прости неща като електронната поща). Основните проблеми тук са начинът на кодиране, предаване, транспортиране и декодиране на данните, изпращани по мрежата, абстракцията на предаваните съобщения (про­то­ко­ли) и др. Разпределянето и организирането на информацията са обект на усилени из­след­ва­ния, а едно от челните места заема въпросът за сигурността на предаваните данни.

Компютърна сигурност

В ранните дни на “компютърната ера”, поради ограничения достъп до компютърните сис­те­ми, както и поради малкия им брой, проблемите, свързани със сигурността, почти не се раз­глеждат. Първите “пробиви” датират от средата на века, когато се поставя въпросът за по­ве­ри­тел­ност­та и личната неприкосновеност на информацията. Малко по-късно Ма­са­чузетският тех­но­ло­ги­чен институт, наред с множеството постижения в областта на компютърните системи и тех­но­ло­гии, става известен и с първия хакер. Ще отбележим, че понятията хакер (от англ. hacker, hacking) и кракер (от англ. cracker, cracking) често се бъркат. Днес в значението на последното се влага сми­съл на извършване на незаконни действия, докато за първото това не е задължително. От тази гледна точка (поверителност и лична неприкосновеност), под сигурност на информацията се раз­би­рат, грижите, полагани за “опазването” й.

В настоящия момент защитата на компютърната информация е от първостепенно зна­че­ние  както по отношение на операционните системи, така и на целия ком­пю­тъ­рен соф­ту­ер.

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

0.1.3. Новаторски компютърни архитектури

През последните 10 години важно място в изследванията в областта на компютърната ин­фор­­матика заемат компютърните архитектури и в частност т.нар. асинхронни архитектури. Ста­ва въпрос за част от по-общия модел на Фон-Ноймановата архитектура на паралелните системи (име­то на Джон Фон-Нойман, както ще стане дума по-нататък в текста, се свързва с първото фор­мал­но описание на структурата на изчислителна система).

При паралелните системи определен, често доста голям, брой компютри или само про­це­со­ри се свързват заедно и оперират като една голяма изчислителна машина. Съществува широк клас от задачи, които са свързани с този аспект на компютърната информатика: раз­ра­бот­ване на тех­ники за програмиране в асинхронни среди, анализиране на ефективността на па­ра­лелни решения и др.

Други новаторски компютърни архитектури ще бъдат разгледани в последния параграф, отнасящ се за изкуственият интелект.

0.1.4. Моделиране на сложни феномени

Изследването на явления и структури от различни области на науката и живота, както и си­му­лацията на реални функции, поведение и процеси от природата са изключително важна част от ком­пютърната информатика. Компютърни игри като “Сим”-серията на Maxis и много други комерсиални продукти допринасят значително за популяризирането на областта.  На­пре­дъ­кът и раз­витието в областта на компютърното моделиране на процеси в химията, биологията, ме­ди­ци­на­та и други науки неминуемо ще доведе до множество важни открития. Така например, в био­ло­гията специфични техники от компютърната информатика могат да се използват за из­след­ва­не на пре­носа на информацията в клетките, централната нервна система и други. В социално-ико­но­ми­чес­ки аспект компютърното изследване и разпознаване на образци в сложни фи­нансови сис­теми мо­же да се използва за ориентиране в икономическа ситуация и пред­виж­да­не на бъде­що­то й раз­ви­тие.

0.1.5. Изкуствен интелект

Изкуственият интелект е добре известна материя, но спорове за това какво обхваща тя и какво точно представлява не липсват и днес. Въпросът в каква степен “интелектът” е свързан с компютърния потенциал е основен и в момента доминират главно две направления, които могат да бъдат обобщени накратко така:

• Силно направление: Задачата на изкуствения интелект е да изследва, разбира и моделира процеса на разумно мислене.
• Слабо направление: Задачата на изкуствения интелект е да моделира системи, в които определени действия могат да бъдат изпълнявани със същата успеваемост, както ако се изпълняват от човека.

Границата между двете направления е условна и теоретически всяка разглеждана задача и всеки получен резултат може да се интерпретира от двете гледни точки: силна (доколко точно начинът на работа на системата моделира мисленето и действията на човека върху същата за­дача) и слабо (доколко успешна е машината). Същественото различие е, че силното направление изисква машината да работи и мисли така, както се предполага, че го прави човекът, докато слабото не се интересува от начина, а от резултата. В частност при слабото направление е напълно допустимо и дори силно желателно машината да се справя по-добре от човека, ако това е възможно, докато силното направление не толерира това: ако човекът често прави определен вид логическа грешка в разсъжденията си, машината също трябва да я прави.

Силното направление се занимава главно с проблеми като разбиране и интерпретиране на ес­тес­твените езици, както и философски въпроси като: “Какво да разбираме под инте­ли­ген­т­на ма­шина?” В допълнение, съществува връзка с логическото мислене, когнитивната наука, пси­­хо­ло­гията, лингвистика  и др.

При слабото направление засега е постигнат доста по-сериозен напредък. Един кон­кре­тен успешен пример в това отношение са експертните системи. Най-общо, те раз­глеж­дат въ­про­са за раз­прос­транение на знания и опит на специалисти в определена тясно специализирана област. Съ­щес­твуват редица успешни реализации на експертни системи за търсене на (ценни) суровинни на­ходища, медицински системи за диагностика на определени заболявания, системи за помощ при ин­тер­пре­тиране и прилагане на закона и други.

Като цяло идеите и на двата “противоположни лагера” заемат централно място в из­след­ва­нията на съвременната компютърна информатика и пред тях непрекъснато се откриват нови възможности за разширение и бъдещо развитие.

Следващата тема е тясно свързана с някои вече разгледани аспекти на компютърната ин­фор­матика, в това число и изкуствения интелект.

0.1.6. Нетрадиционни методи за изчисление

Невронни мрежи

Проблеми като разпознаване по образец, разпознаване на говор, разпознаване на образи и др. са някои задачи, при които се счита, че невронните мрежи могат да се прилагат успешно. Без да се задълбочаваме в тази насока, ще скицираме съвсем накратко идеите, върху които се основава ед­на невронна мрежа: това е техника за обработване на данни, вдъхновена от начина, по който то­ва се извършва в човешкия мозък. Изкуствената невронна мрежа е математически модел, със­та­вен от набор отделни елементи, които симулират някои наблюдавани свойства на биологичните нев­ронни системи (както и процесите на адаптивно биологично усвояване на нови знания и уме­ния). Съвременният модел на невронна мрежа е композиция на добре взаимодействащи си еле­мен­ти (аналог на невроните) и свързващите ги канали (аналог на синапсите). Основно свой­с­тво на невронните мрежи е самомодификацията (самообучението) дотогава, докато бъде постигнат оп­ре­делен желан резултат.

Генетични алгоритми

Генетичните алгоритми също черпят своите идеи от природата. Като цяло те се ос­но­ва­ват на принципа на естествения подбор (оцеляване на най-доброто) при последователно ге­не­риране на “поколения” до решаване на поставената задача. Техниката наподобява процесите на генетично ниво при живите организми и все по-успешно се използва за решаването на трудни из­числителни за­да­чи. В настоящия момент изследванията в тази насока са свързани с раз­би­ра­не­то и поставянето на теоретична основа за генетичните алгоритми, както и разширяване на приложението им.

Квантови изчисления

Квантовите изчисления се основават на идеи от физиката. Анализира се потенциалното им приложение в нетрадиционна компютърна архитектура, която може да се окаже значително по-ефективна от сега съществуващите. Изследванията в тази област на този етап са строго те­о­ре­тични и често се ограничават до дискутиране на връзката между съвременната теоретична физика и ком­пю­тър­ната информатика.

0.1.7. Фундаментална компютърна информатика

След краткия увод за периферията на компютърните технологии и информатика ще се на­сочим към основния предмет на настоящата книга: “ядрото” на компютърните технологии — фундаменталната компютърна информатика. Образно казано, “плътността” на това ядро е съ­сре­доточена в компютърните алгоритми — главната движеща сила и най-важният механизъм за успешното функциониране на целия компютърен свят.

Съществуват два основни термина при разглеждането на “поведението” на компютъра: пред­ставяне и трансформиране на информацията. Информация е всичко, което носи някакъв сми­съл (числа, думи, имена, понятия и др.). Компютърът от своя страна работи със символно пред­ставяне на информацията под формата на последователност от двоични цифри, което е прието да се нарича данни. Следва да се отбележи, че данните са носител на информация, но сами по себе си не са информация. Така например, за компютъра, както и за всеки незапознат, числото 25 не оз­на­чава нищо конкретно. Едва когато в него се вложи някакъв смисъл, например цена на чаша кафе в стотинки, може да се говори за информация.

Представянето на информацията се състои в символното кодиране на смисъла, заложен в нея. Трансформирането — това са стъпките  на алгоритъма за достигане на определена цел. По­лу­ча­ваме следната неформална дефиниция на компютърен алгоритъм:

Компютърният алгоритъм е схема на последователност от компютърни изчисления за решаване на определена задача (достигане на определена цел).

Преди да преминем към кратък преглед на историята на възникване на алгоритмите, както и към материала, разглеждан в книгата по същество, ще направим кратко лирично отклонение: есе, чиято цел е да представи по малко по-нетрадиционен начин (както читателят сам ще се убеди) ползата от изучаването и разбирането на компютърните алгоритми.

0.2. Понятието леймър

Често са ни задавали въпроса какво означава леймър (от англ. lamer), когато се из­пол­з­ва като определение по адрес на някой програмист. Отново, без да даваме формална де­фи­ни­ция, ще обясним понятието, като използваме въведение ала Карл Май [May-1893].

На първо място, най-важната характеристика за един леймър е, че той не подозира, че е такъв.

По-нататък, едно от най-разпространените определения за леймър, е програмист, който пише програми в колонка и който, като чуе за рекурсия, получава леко разстройство.

Леймър е програмист, който знае няколко езика за програмиране, но няма никакво понятие от алгоритми.

Леймър е програмист, който ако изобщо слага коментари в програмите си, те са главно от следния вид:

i++; /* увеличаваме i с единица */

Леймър e програмист, който не знае, че зад простичката игра Minesweeper за Windows се крие една от най-сериозните задачи в информатика, за разрешаването на която университетът Станфорд е определил награда от 1 милион долара [Prize-2000].

Леймър е програмист, който може да напише бързо сортиране единствено, ако го научи наизуст. Нещо повече, истинските програмисти рядко могат да го запомнят и напишат бързо, но за сметка на това за 10 минути могат сами да си го “измислят”. Нашата цел е читателят да достигне това ниво, при което решаването на сложни задачи се свежда до просто упражнение на интуицията му.

Леймър е програмист, който не знае, че “събирачът на боклук” (от англ. garbage collector)  не е измислен, специално за да събира “труповете” на “починалите” обекти на Java, а зад него стои мощна и красива теория, представена още в средата на XX век.

Леймър е програмист, който не знае, че най-ефективната търсеща машина в Интернет Google дава толкова релевантни резултати, защото се основава на новаторски методи от те­о­ри­я­та на графите.

Леймър е програмист, който не знае, че формулата за ефективната реализация на про­из­во­лен компютърен проект е малко спецификации + много и ефективни алгоритми.

Леймър е програмист, който не може да проумее защо една програма, за която “някой бил казал, че има сложност Q(n²)”, е по-бърза от друга със сложност Q(n³), след като n³ > n².

Леймър е програмист, който може да програмира на Cи и който може да намери най-малко общо кратно на две числа на лист, но не може да си напише програма за това.

Леймър е програмист, който не може да си обясни защо като се компресира един файл, и после се компресира още веднъж, той не намалява още повече.

Леймър е програмист, който знае, че това е дърво, но не подозира, че то­ва  също е дърво, както и това  . И, че всъщност той са­мият, като програмист, също е едно младо и зелено дърво.

Леймър е програмист, който за 10 минути може да направи дадена програма 10 пъти по-бавна, без да се притесни, че някой преди него е загубил 10 часа в оптимизиране, за да я направи с 10% по-бърза.

Леймър е програмист, който brute-force-ва ftp (от англ. File Transfer Protocol — протокол за пренос на файлове в компютърна мрежа) пароли, без да съобрази, че при сегашната скорост на Интернет трудно би могъл да hack-не парола, по-дълга от 5 символа (а за това е необходимо едно съвсем просто комбинаторно изчисление), освен ако не извади луд късмет.

Леймър е програмист, който трудно може да проумее асоциация на хубава вечеря с хубава програма (а тяхното качество зависи предимно от рецептата/алгоритъма, който се използва).

Леймър е програмист, който не знае, че най-краткото разстояние между две точки не винаги е правата линия (понякога, то се намира по алгоритъма на Дейкстра).

Леймър е програмист, за когото двоично търсене означава търсене в двоични файлове.

Леймър е програмист, който се възхищава на програмни фрагменти като този:

(0x000000FF & (i >> 24);

често, просто защото си няма понятие какво точно означават и панически преминава на след­ва­ща­та страница, когато види “йероглиф” от вида:

Леймър е програмист, който не е чувал за динамично оптимиране. Всъщност, един от на­ис­ти­на добрите начини да разбиете в спор някой леймър, е да му заявите: “Хей, ами тази задача е до­бре известна и се решава лесно, елегантно и ефективно с динамично оптимиране”.

В началото, както всички начинаещи програмисти, и ние не бяхме нищо повече от едни мла­ди и зелени леймъри. С течение на времето с хубави книги и статии, и най-вече с упорит труд по решаване на алгоритмични проблеми, започнахме да надрастваме това ниво. Днес сме готови да по­могнем и на теб, драги ни читателю, да избягаш от стерилитета на занаятчийското про­гра­ми­ра­не.

Ще завършим настоящия параграф с една от прекрасните мисли на друг знаменит автор (Марк Твен):

“Когато искам да прочета нещо хубаво, сядам и си го написвам”.

Целта на настоящата книга е да доведе теб, читателю, до положение, при което да имаш са­мо­чувствието да заявиш:

“Когато искам да видя хубава програма, сядам и си я написвам”.

0.3. Развитие на алгоритмите

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

0.3.1. Произход на думата “алгоритъм”

Думата алгоритъм идва от името на арабския математик al-Khowarizmi, който през VIII век описва откриването на десетичната бройна система и представя редица важни концепции в книгата си Al-jabr wa’l muqabala (заглавие, от което по-късно е образувана още една добре известна дума – алгебра). Това е най-разпространената хипотеза за появата на думата ал­го­ри­тъм, въпреки че съществуват и други: по името на арабския  математик Al-Khashi, който през XV век предлага метод за изчисляване на константата p с точност 16 знака след десетичната запетая.

Истината, както винаги, е някъде по средата. Това не означава, че в средата на XII-ти век тре­ти арабски математик Al-* е предложил някаква нова и зашеметяващата за времето си схема за изчисляване на “нещо” — просто, когато се поставя въпросът за произхода на думата алгоритъм, не съществува друг отговор, освен множество хипотези, някои от които се налагат повече от други [Knuth-1/1968].

“Историческото” развитие на компютърните алгоритми, доколкото може да се говори за та­­кова, условно може да се раздели на три етапа:

• намиране на начин за символно представяне на информацията под формата на данни;
• формулиране на алгоритми, използващи данните за решаване на изчислителни за­дачи;
• създаване на механични изчислителни машини, които могат да изпълняват алгорит­ми­те ефективно.

Първият въпрос (за представянето на данните) най-добре може да се илюстрира, като се раз­гледат различните начини за представянето на числата (някои, от които датират от най-дълбока Древност). Най-простото представяне е като редица от идентични символи, например чертички. Така всеки уважаващ себе си затворник отбелязва върху стената на килията броя на годините, които е прекарал лишен от свобода. Следващ добре известен пример е представянето на числа с рим­ски цифри. По-нататък, наред с начините за представяне на числата започват да се появяват и пра­­вила за манипулиране с тях — аритметични операции, както и първите форми на прости из­чи­сли­­телни машини — сметало и др.

Следващата кратка хронология показва някои проекти и събития, имащи пряка връзка с компютърните алгоритми, като се започне от Древността и се стигне до средата на XX век.

0.3.2. Алгоритмите през вековете

300 г. пр. н. е. Евклид предлага алгоритъм, който намира най-големия общ делител на две естествени числа m и n:

1)      Ако стойността на m е по-малка от тази на n, разменяме стойностите им.

2)      На m даваме нова стойност: остатъка от делението на m с n.

3)      Ако m е различно от 0, преминаваме към стъпка 1), като използваме новите стойности на m и n.

4)      Резултатът (най-големият общ делител на двете числа) е равен на n.

250 г. пр. н. е. Простите числа, както и методите за тяхното намиране, са в основата на най-старите изчислителни задачи. Алгоритъмът на Ератостен, известен като решетото на Ера­тос­тен, датира още от 250 г. пр. н. е. Оттогава, до днес (с малки изключения), в методите за тър­сене на прости числа не е постигнат съществен напредък. Наскоро обаче беше направен про­бив при сходна задача: намерен беше ефективен алгоритъм за проверка дали дадено число е  прос­то.

780-850 г. Както вече споменахме, това е периодът, през който Abu Ja’far Mohammed Ben Musa al-Khwarizmi публикува “Hisab al-jabr w’al-muqabala“.

1424 г. Годината, през която Ghiyath al-Din Jamshid Mas’ud al-Kashi изчислява p с точност 16 знака след десетичната запетая.

0.3.3. Анализ на алгоритмите

1845 г. Гейбриел Лейм (Gabriel Lame — Името му няма нищо общо с понятието леймър, въ­преки че, ако можеше да прочете описанието от предишния параграф, прочутият математик вероятно би се обърнал в гроба) показва, че алгоритъмът на Евклид извършва брой деления, не повече от 5 пъти броя на десетичните цифри на по-малкото число.

1910 г. Поклингтън дефинира сложност на алгоритъм като полином, зависещ от броя на цифрите в двоичното кодиране на обработваните данни.

0.3.4. Изчислимост

1900 г. Дейвид Хилберт поставя въпроса за намирането на процедура за решаване на диофантови уравнения (полиноми с цели коефициенти) и по този начин полага основите на по-късно появилите се формални дефиниции за изчислимост.

1920-30 г. Пост предлага прост унарен модел за изчисления, известен като машина на Пост.

1930 г. Алонсо Чърч представя ламбда-смятането.

1936 г. Алън Тюринг публикува статия, където представя машината на Тюринг — формален модел за изчислимост, който освен това е физически осъществим. (Всъщност почти осъществим, тъй като формалният модел изисква неограничен размер на паметта.)

Последната дата се смята за рождена на съвременния компютър.

От средата на XX век (по обясними причини) теоретичната компютърна ин­фор­ма­ти­ка започва да се развива с изключително бързи темпове, за да достигне днешния си вид. Из­хож­дайки от “неизвестността на бъдещето”, никой не може да бъде сигурен, че тя ще затвърди своя блестящ старт с нови успехи. Въпреки това, авторите на тази книга биха се обзаложили, че през настоящия XXI век това, което ще определя и променя облика на планетата ще бъдат именно компютърните и информационните технологии. И без още да знаем каква ще бъде следващата фун­даментална научна теория, която ще преобърне представите ни за света, ние ще се по­ста­ра­ем да ти осигурим, драги ни читателю, летящ старт в надбягването с времето.

0.4. програмиране = ++алгоритми

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

• за кого е предназначена книгата;
  • какво е естеството на представяния материал;
  • защо избрахме езика Cи за реализациите на алгоритмите, както и няколко думи по конвенцията на предложените изходни текстове;
  • нашите благодарности, както и адресите за връзка с нас.

Забележка: Ти, любознателни читателю, вероятно вече си се замислил над заглавието на книгата? Ако не си, ти предлагаме да се опиташ да си отговориш на следните въпроси:

1. Защо заглавието е “програмиране = ++алгоритми”, а не “програмиране = алго­рит­ми++”.

2. Замисли се отново и над понятието леймър.

3. Опитай се да сравниш заглавието на книгата с името на езика Си++: защо не е ++Си и каква е връзката с нашия случай.

0.4.1. За кого е предназначена книгата

Целта на настоящата книга е да запознае читателите с най-разпространените техники на про­грамиране. Наред с представянето на широкоизвестни методи за решаване на алгоритмични за­да­чи (и анализ на техните свойства, приложения, предимства и недостатъци), се разглеждат и сто­ти­ци конкретни алгоритмични проблеми, обръща се внимание на анализа на алгоритмичната слож­ност на предложените решения, прави се сравнение между различни подходи и други. В кни­га­та се засяга широк спектър от теми, както в теоретичен, така и в чисто приложен аспект. Ма­те­риалът е ориентиран по-скоро към приложната страна и реализацията на разглежданите ал­го­рит­ми за сметка на чисто теоретични изследвания и доказателства за коректност (като все пак цел­та е да се обхванат в някаква степен най-актуалните съвременни научни резултати в съ­от­вет­на­та об­ласт).

Книгата е подходяща за всички, които са избрали програмирането за своя професия и по някакъв начин то е свързано със Си, Си++, Java. Тъй като техниките, които се разглеждат, са фундаментални и обикновено не разчитат на определени характеристики на езика (и средата) за програмиране, то съответните алгоритми са приложими във всеки език за програмиране от високо ниво.

Книгата представлява полезно ръководство за участниците в състезанията по про­гра­ми­ра­не, ученици и студенти. Като дългогодишни участници в “подобен род мероприятия” ние се по­ста­рах­ме да систематизираме и подредим материала по такъв начин, че той да бъде от максимална полза тогава, когато се налага да се решават алгоритмични задачи бързо и без “право на греш­ки”.

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

Съдържанието на книгата покрива почти целия материал, необходим за провеждането на съответен университетски курс по алгоритми и/или структури от данни, като е наблегнато основно на алгоритмите. Освен най-разпространените и полезни алгоритмични техники на редица места се засяга по-специфична тематика и, като цяло, материалът трудно може да се преподаде в рамките на един учебен семестър. Такъв курс по алгоритми (ПрАнКА — Проектиране и Анализ на Компютърни Алгоритми) се чете в Софийски университет “Св. Климент Охридски”, като съ­дър­жа­нието му и по-подробна (и актуална) информация за него може да бъде намерена на някои от ад­ресите на книгата в Интернет или с e-mail до авторите (виж коментари и въпроси по-долу).

0.4.2. Кратко представяне на съдържанието

Глава 1. “Въведение в алгоритмите” разглежда някои по-важни математически понятия, фун­к­ции и техни свойства, както и основни програмистки техники — рекурсия и итерация, ге­не­ри­ра­не на комбинаторни конфигурации и др.

Глава 2. “Въведение в структурите от данни” запознава читателите с най-важните струк­ту­ри от данни или, казано с други думи, със “скелета” на всяка една програма.

Глава 3. “Сортиране” и

Глава 4. “Търсене” са важни теми от “всекидневието” на програмиста. Засегнати са както ши­­роко известни, така и някои екзотични (но често изключително полезни) техники на ма­ни­пу­ла­ция с “подредени” данни.

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

глава 5. “Теория на графите”

глава 6. “Търсене с връщане. NP-пълни задачи”

глава 7. “Разделяй и владей”

глава 8. “Динамично оптимиране”

глава 9. “Алчни алгоритми”

глава 10. “Компресиране”

0.4.3. Защо Cи?

Изборът на език за програмиране за реализацията на разглежданите алгоритми се пре­до­пре­деля от няколко основни фактора.

Езикът Си (и неговият “upgrade” Си++) е традиционен, както в обучението, така и в средите, където се разработва приложен софтуер. Не може да се подмине и все по-нарастващата (и незатихваща) популярност на “по-малкия брат” на Си — Java. В основата си двата езика са много близки и, тъй като в настоящата книга се разглеждат и реализират конкретни алгоритмични проблеми, без да се навлиза в специфични “приложни” детайли, програмните фрагменти без особени проблеми могат да се използват в средата на Java (Вероятно понякога с някои дребни модификации).

Изборът на език е съобразен и с целите на книгата: освен да изведе обикновения про­гра­мист до висините на изкуството на ефективното алгоритмично мислене, да представлява и свое­об­раз­на “енциклопедия” по алгоритми за ученици и студенти, участващи в състезания по про­гра­ми­ра­не (където езикът Си е доминиращ). Не на последно място, отскорошна практика във висшите учеб­ни заведения (особено за информатика и сродните й специалности) е да се изучава Си като ос­новен език за програмиране. Впрочем, подобна тенденция се наблюдава и в средното обра­зо­ва­ние. Там обаче този процес е по-бавен поради липсата на достатъчно подготвени педагогически кадри, владеещи Си — вероятно тепърва трябва да бъдат произ­ве­де­ни от висшите учебни за­ве­де­ния.

Си е ефективен и гъвкав, позволява почти всичко, което е необходимо на един про­гра­мист, като често е изключително полезен и при теоретични изследвания — ефективен е при ем­пи­рични експерименти и др.

И все пак, защо не използвахме Си++? Ами защото “upgrade”-ът на Си няма какво по­ве­че да ни предложи, освен може би синтактични удобства в някои ограничени случаи. При това, из­ползването на Си++ определено би ни тласнало в посока на обектноориентирано про­гра­ми­ра­не, което би било не само изкуствено, а просто вредно, когато става дума за алгоритми. На­­ис­тина, смисъл от въвеждане на обекти може да има при някои структури от данни: дър­ве­та, спи­съци, хеш-таблици и други, но едва ли при алгоритми. Така например, Робърт Седжуик, автор на пре­въз­ходната книга “Algorithms in Pascal”, по-късно издаде варианти на Си, Си++ и Java. На не­убе­де­ния във вредата от обектите читател предлагаме да сравни вариантите на книгата на Си и Си++.

И все пак, защо не Паскал? За съжаление, Паскал е вече почти мъртъв език. И двамата автори са силно пристрастни към него: той е по-прост от Си, крие по-добре подробностите по вътрешната реализация на определени операции, има вградена обработка на грешки, поради което е по-толерантен към неопитния програмист, и най-важното: по-удобен е за обяснение на алгоритми. Никлаус Уирт, неговият създател, го е замислил именно като език за обучение и тук е ос­новната му сила. Тук е обаче и основната му слабост: езикът се оказа недостатъчно гъвкав и изразителен (например по отношение на Си), когато става въпрос за реално програмиране, поради което постепенно беше изоставен преди повече от 10 години. Днес Паскал е в основата на средата за програмиране Delphi. Езикът на системата обаче все повече се отдалечава от първоначалния вариант на Уирт и все повече се утвърждава като самостоятелен, различен от Паскал. Подобно на понятието informatics, днес Паскал е обект на предразсъдъци и сред програмистките среди има репутацията на “несериозен” език. От Borland International съзнаваха това добре, но дълго време се опитваха да се борят за репутацията на езика. Докато накрая и те се предадоха и се принудиха да сменят името му на Delphi по чисто търговски съображения. Днес влиянието на Паскал се ограничава до Macintosh (системата е разработена на този език, но той постепенно е изтласкван и оттам) и до отделни групи ентусиасти под Linux, Unix и ДОС.

Не е така със Си: нито Си++, нито Java, успяха да го “детронират” и вече няколко де­се­ти­летия той е един от основните езици за програмиране. Впрочем, фактът че дори най-съ­вре­мен­ните специализирани езици за програмиране в Интернет като Java, Javascript, Perl, PHP и дру­ги имат Си-подобен синтаксис говори сам по себе си за влиянието на езика в про­гра­мис­ткия свят: разчита се на привличане главно на програмисти, владеещи Си.

0.4.4. Конвенция на изходните текстове

Стилът на изходните текстове (подравняване, отместване, именуване на променливи, фун­к­ции и т.н.), използван при реализация на алгоритмите в настоящата книга, не се отличава съ­щес­т­ве­но от широко възприетите и за читателя едва ли ще представлява трудност “четенето” на пред­ло­жените програми.

Всички програми са компилирани и тествани както под DOS (с Borland C++ 3.1), така и под Windows (с Visual C++ 6.0). Записани са с разширение на програми на Си и не се от­кло­ня­ват от стан­дартите на ANSI за езика. Възможно е обаче при някои  входни данни дадена про­грама да ра­бо­ти коректно под Windows, но не и под DOS, поради ограниченията на раз­ме­ри­те на про­мен­ли­ви­те и/или на наличната адресируема памет.

0.5. “Следговор”

Посвещение

Панайот посвещава тази книга на Силвия, малката Никол и останалите 66,666% (бъдещи) епсилон-члена на семейството ни.

Преслав я посвещава на Петя с благодарност за разбирането и под­кре­пата за на­чи­на­нието.

0.5.1. Благодарности

На първо място благодарим на научния си редактор Емил Келеведжиев от БАН за под­кре­пата, която ни оказа във всички етапи от разработването на книгата, за неколкократното задъл­бо­че­но изчитане на материала, съпътствано с множество ценни забележки, предложения и корекции.

Сърдечни благодарности на Райко Чалков, който “прецака жестоко всички скатаващи се тихомълком” сгрешени индекси (и не само). Убедени сме, че някой ден ще бъдем изключително горди, че подобен научен талант е участвал в редакцията на нашата книга.

Тук е мястото да изразим и признателността си към нашите колегите от SAP Labs и Rila Solutions за оказаната подкрепа и прекрасните условия за творческа дейност. Съчетаването на дей­нос­ти като четене на спецификации, писане на код (на килограм), оптимизиране и дебъгване ни най-малко не си пречеше с “литературните” ни занимания, дори напротив — двете неща се до­пъл­ва­ха по особено очарователен начин (освен в периодите, когато наближава deadline на проект. То­га­ва времето от 22:20 до 01:55 е особено ценно.).

Благодарим на доц. Красимир Манев от СУ “Климент Оридски” — гръбнакът на бъл­гар­ска­та компютърна ин­фор­ма­тика през последните няколко години (в съвременният световен сми­съл на думата). Курсът (и учебникът) по дискретна математика, който се чете във Факултета по ма­те­матика и ин­фор­ма­ти­ка на Софийски университет, е едно от нещата, заради които човек си заслужава да бъде сту­дент в България (Останалите са общоизвестни — повечето са производни на ат­мосферата в Сту­ден­тски град.).

Специални благодарности на доц. Асен Рахнев от ПУ “Паисий Хилендарски”, който се за­поз­на отблизо с книгата в нейния почти финален вариант, даде своите ценни препоръки и любезно се съгласи да напише рецензия.

Редакциите и дискусиите с всички наши колеги и приятели беше изключително полезна и без­ценна, за да придобие материалът финален вид. Още един път изказваме нашата сърдечна бла­го­дарност на Станислав Овчаров, Иво Маринчев, Светлин Наков, Павлин Добрев, Васил По­пов­ски, Петко Минков, Петър Петров, Деян Ламбов, Кирил Арабаджийски, Иван Пейков и Валентин Ба­­коев.

Специална благодарност на всички студенти от курса по ПрАнКА, воден по работен ва­ри­ант на настоящата книга, и изобщо на всички, които съзнателно или несъзнателно дадоха своя при­нос.

Много хора ни помогнаха без ни най-малко да подозират (последната фраза е из­пла­ги­ат­с­т­ва­на, без авторът й да подозира — благодарности и на него). Това са много от  приятелите ни (как­то и приятелките ни), които ни припомняха къде се намираме в моментите на хронична ши­зо­фре­ния.

Параграфът няма да бъде пълен, ако пропуснем благодарностите за нашите семейства. Не на последно място, и без да правим изявления в стил “негър при връчване на Оскар” като из­реж­да­ме всичките си роднини, ще отбележим с bold специфичната подкрепа, която получихме от най-близ­ките си хора.

0.5.2. Коментари и въпроси

Материалът в настоящата книга е препрочитан и коригиран внимателно в продължение на ня­­колко години. Въпреки това, както във всеки сериозен труд, допускането на грешки е за­дъл­жи­тел­но и авторите не са и помисляли да отнемат удоволствието на внимателния читател от нами­ра­не­то на сгрешени индекси, неточности и двусмислия. Разбира се, надяваме се и ти, драги ни чита­те­­лю, да не ни лишиш (нас, както и останалите читатели) от възможността да разберем за допус­на­ти­те грешки (и да ги поправим за следващото издание), като ни пишеш на някой от следните ад­ре­си:

[email protected]; [email protected]; [email protected]

[email protected]; [email protected]; [email protected]

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

Най-актуалният вариант на списъка с корекциите може да бъде намерен на страницата на книгата в Интернет на адрес:

http://www.algoplus.org

На посочения адрес може да бъде намерена много допълнителна информация: решения на задачите за упражнение и изходните кодове на всички програми; части от книгата в електронен вид, свободни за разпространение; списък с корекции; различни промоции и конкурси; новини; както и препратки към най-разнообразни алгоритмични ресурси.