Дървовидни структури – учебен материал по програмиране: обхождане, операции, балансирани дървета и кодиране на Хъфман, с код на C++

Осем страници, в които една структура от данни е разгледана от определението до три готови алгоритъма с код – точно каквото трябва за изпит по програмиране. Материалът е конспектен, но не е сбит до неразбираемост. Всяко понятие е въведено с определение и онагледено с пример, а алгоритмите не са само описани – дадени са с реален код и с проследено числено изпълнение. Първата част е терминологична и обхваща в плътна последователност всичко, което се пита: определението за граф, разликата спрямо дървото, видовете дъги и графи, инцидентност и съседство, степен на връх с отделните ѝ разновидности при ориентиран граф, път, дължина, прост път, цикъл, свързаност и подграфи. Означенията са въведени поред и се използват последователно нататък. Втората част е за представянето в паметта и е разделена на три подхода. Статичните са три на брой, всеки с приложена схема. Динамичното е дадено с готови структури, а комбинираното – с още една декларация. Тук е и бележката кога кой подход е за предпочитане. Следва списък с осемте основни операции, а веднага след него – деветте аксиоми, при които те са определени. Последната аксиома важи само за единия вид графи и това е изрично уточнено. Такова изброяване рядко се среща събрано на едно място. Средището са трите алгоритъма и всеки е разгърнат по един и същи начин. Първият е за най-къс път и е представен с постановка, с описание на работата чрез поддържане на множество, с числен пример и с масивите, използвани в него, а после и с пълен програмен код. Накрая е дадена сложността при двата начина на представяне. Вторият е за топологично сортиране. Тук е обяснено защо резултатът рядко е единствен, приведени са няколко възможни подредби, дадени са трите стъпки и е посочен обратният вариант на същия алгоритъм. Третият е за най-дълъг път и започва с практическа задача от разработването на програмен продукт, преведена в термините на графа. След трите стъпки и сложността следва напълно проследено числено изпълнение по стъпки, а накрая – указание как алгоритъмът се реализира рекурсивно. За преподавателя това е готова опора за няколко учебни часа, която не изисква подготовка. Трите алгоритъма вършат работа и поединично – като материал за упражнение или като тема за самостоятелна работа. За студента ползата е ясна: целият изпитен въпрос е събран на едно място, а програмният код и проследените числени примери спестяват търсенето по няколко източника. Материалът се преговаря непосредствено преди изпит и върши работа при курсова задача.

Целият конспект по един предмет, сведен до девет страници. Онова, което в обичайните записки заема тридесет и седем, тук е събрано в една четвърт от обема — без да е изпуснато съществено. Именно това сгъстяване е смисълът на материала. Той не е предназначен за първо запознаване с предмета, а за последния преговор, когато времето не стига и е нужно всичко да се обхване наведнъж. Съкращаването е постигнато по два начина. Първият е шрифтът — основният текст е с размер шест пункта, а част от него дори с пет. Вторият са съкращенията: над двеста в целия текст, при това последователно прилагани. Съкратени са и заглавията на самите въпроси, така че всяко се побира на един ред. Обхватът следва конспекта. Началото е с основните понятия, свойствата на алгоритъма и класификациите му по няколко признака. Следват математическите основи, рекурсията с нейните типове и опасности, а после и същинският анализ — означенията, определенията и правилата. Отделни въпроси прилагат тези правила върху конкретни случаи: цикли, вложени цикли, рекурсия и многократна рекурсия. Средището са структурите. Дърветата заемат няколко последователни въпроса — понятия и класификации, свойства на двоичните, обхождане и рекурсивни алгоритми върху тях. Оттам следват сортировките, а после и групата за подходите: разделяй и владей, динамичното програмиране в два въпроса, постъпателните алгоритми с техните приложения и връщането назад, включително при игри. Финалната група е за графите — общи понятия, представяне, топологично сортиране, най-къс път, пропускателна способност и минимално обхващащо дърво. Особено ценни са деветдесет и трите чертежа. При такова сгъстяване те носят голяма част от обяснението — дървета, графи, схеми и таблици, вмъкнати направо между редовете. Материалът е готов за печат в този вид. Не се нуждае от преформатиране, а разположението е съобразено с разрязване на отделни ленти. Преподавателят може да го използва като бърз преглед какво влиза в изпита. Студентът получава целия материал в най-сбит възможен вид. Годен е за преговор в последните часове преди изпит, когато е нужно освежаване, а не четене.

Комплект, който не се чете от кора до кора, а се отваря при нужда. Всеки от тридесет и петте файла решава една конкретна задача и се използва в мига, в който тя е зададена. Материалите вървят по трудност и повтарят пътя на един семестър – от най-простото пресмятане до алгоритми, които се преподават чак в края на курса. Първото равнище е за начинаещи. Тук са задачите, при които програмата чете няколко числа и извежда резултат: работа по формула, избор между стойности, извеждане на отделна цифра, повторение чрез цикъл. Всяка от тях е кратка и е подходяща за първите часове, когато езикът още се усвоява. Второто равнище е работата с масиви и заема почти една трета от целия комплект. Едномерните са застъпени с четири решения, а двумерните – с осем, което е сериозна разлика. Причината е ясна: двумерните затрудняват най-много, а тук са покрити всички обичайни случаи, включително обхождане по диагонал и по периметър, преминаване между двата вида масиви и една задача с многосъставно условие. Третото равнище е рекурсията – единадесет решени задачи, най-голямата група в комплекта. В нея са всички класически примери, които се падат на изпит, а също и няколко проверки върху число, масив и редица. Достатъчно е ученикът да прегледа тази папка, за да види как една и съща идея работи в различни случаи. Четвъртото равнище са трите пълни упражнения. Първото събира алчните алгоритми, работата с низове и цяла поредица от методи за сортиране, всеки с име и с готов код. Второто е за двоичните дървета, графите и построяването на оптимално дърво. Третото е теоретично и разглежда вероятностните алгоритми по видове, с примери и с раздел за генераторите на случайни числа. Именно тези три файла отличават комплекта от обикновена сбирка със задачи: те дават теорията, върху която стъпват най-трудните теми. Оформлението е еднакво навсякъде: условие с едно изречение, после пълен изходен код, готов за компилиране. Езикът е един и същ през целия комплект, а стилът на писане не се променя от файл на файл – което улеснява четенето на чужд код. За преподавателя това е готов набор за упражнения през целия семестър. Файловете се раздават поединично или по теми, без нужда от подготовка, а трите упражнения вършат работа като материал за лекция. За студента ползата е в подредбата по трудност: подготовката може да върви от началото към края или да започне направо от темата, която предстои да се изпитва. Готовият код служи за образец при писане на собствено решение по курсова задача.

Кратък конспектен въпрос, чиято сърцевина е един алгоритъм. Той е разписан в шест стъпки, но повечето от тях се разклоняват на подстъпки — и на места разклоненията стигат до четвърто равнище. Именно тази многостепенна подредба прави материала практичен. Той не разказва как се проектира, а изброява какво се прави и в какъв ред, така че може да се следва като указание. Темата е проектирането на техническо изделие и е събрана на две страници. Началото изброява четирите основни задачи, които се решават при проектиране, и веднага след това четирите съществуващи метода, всеки назован поименно. Оттам изложението се съсредоточава върху последния от тях, с уточнение за какво е предназначен — за изделие, което се проектира наново, а не се преработва. Средището е самият алгоритъм. Първата стъпка е за формулирането на задачата. Тя минава през три подстъпки, като най-полезна е последната — преформулиране на вече определената задача. Похват, който често се пропуска, а промяната на формулировката отваря нови възможности за решение. Втората стъпка определя основната функция и изходящия поток. Третата е най-разгърнатата и изброява шест различни начина за търсене на решение. Освен обичайните са посочени и обръщането към патентната литература, разглеждането на съществуващи сходни изделия и използването на различните формулировки от първата стъпка. Именно това изброяване е най-ценното в материала. То превръща търсенето на решение от вдъхновение в подредена работа. Петата стъпка е най-дълбоко разклонената. Тя изисква за всеки избран вариант да се извърши разлагане по функции, да се състави таблица с възможните решения, а после за всяка съставна част да се уточнят изискванията към материала, съседните части и връзките помежду им. Финалната стъпка е за работната документация. Изложението е конспектно, с многоравнищни изброявания и с препратки между отделните точки по номер. Използвани са и няколко съкращения, въведени в текста. За преподавателя това е готов кратък урок, а алгоритъмът върши работа и като раздавателен лист при курсова задача. Студентът получава темата в завършен вид. Обемът позволява преговор за минути преди изпит.

Готов лабораторен протокол с три решени задачи. Всяка е дадена изцяло – условие, блокова схема и работеща програма, готова за въвеждане и изпробване. Именно тази пълнота го отличава. Студентът не получава указания как да реши задачата, а вижда завършеното решение и може да го сравни със своето. Материалът е първи протокол по програмиране и обхваща десет страници. Първата задача е за пресмятане на корените на уравнение от втора степен. Тя е и най-обширната, защото условието изрично изисква да се разгледат всички възможни стойности на коефициентите. Именно това я прави най-полезната от трите. Решението не се ограничава до обичайния случай, а обхожда последователно пет положения: когато два от коефициентите са нула, когато е нула само единият, когато е нула свободният член и накрая трите възможности според знака на дискриминантата. Особено ценна е частта за отрицателна дискриминанта. Тук програмата не спира с грешка, а пресмята комплексни корени, като реалната и мнимата част се въвеждат като отделни променливи още преди разклонението. Втората задача е за прост калкулатор с четирите основни действия. Решението стъпва на конструкция за избор по стойност на един знак, при която всеки случай е даден на отделен ред. Предвиден е и случаят, в който въведеният знак не съвпада с нито един от очакваните. Именно тази задача е удобна за начинаещи – кратка е, но показва две неща наведнъж: работа със символна променлива и разклонение с повече от два изхода. Третата задача е за пресмятане на функция, зададена с три различни израза в зависимост от това в кой участък попада входната стойност. Решението е изградено с последователни проверки, като при всеки случай се извежда и самият израз, по който е пресметнато. Всяка от трите програми е с еднакво устройство: обявяване на променливите, въвеждане с подкана към потребителя, пресмятане и извеждане на резултата, накрая спиране преди затваряне на прозореца. Приложена е и блокова схема към първата задача. Преподавателят получава готов протокол, годен за мерило при проверка, а трите задачи вършат работа и поединично като упражнения в час. Студентът получава три работещи решения, които може да въведе, да изпробва и да преработи според собственото си условие.

Четиридесет и пет въпроса, разработени един след друг — целият конспект по един предмет, събран в един файл. Обемът надхвърля сто и шестдесет хиляди знака. Именно тази пълнота прави материала стойностен. Студентът не търси по няколко източника за отделните теми, а разполага с готов текст за всяка от тях. Материалът е върху синтеза и анализа на алгоритми и е събран на тридесет и седем страници. Началото поставя основите — какво представлява алгоритъмът, по какви начини може да бъде записан и кои са неговите свойства. Изброени са пет отделни свойства, а после и няколко признака, по които алгоритмите се делят на видове. Оттам изложението върви по конспекта, като темите са подредени по нарастваща сложност. Първата голяма група е за основните структури от данни — дървета с техните свойства и обхождания, списъци, стек, опашки и хеш таблици. При всяка е дадена и представа за начина, по който се реализира. Средището са сортировките. Разгледани са седем различни метода в отделни въпроси, като при няколко от тях е показано и как алгоритъмът може да се подобри. Особено ценна е групата за подходите. Тук са разделяй и владей, постъпателните алгоритми с три отделни приложения, динамичното програмиране, връщането назад и алгоритмите от теорията на игрите. Финалната група е за графите — представяне, топологично сортиране, най-къс път по два начина, пропускателна способност и минимално обхващащо дърво по два известни алгоритъма. Изложението е конспектно и удобно за преговор. Определенията са кратки, стъпките са номерирани, а на много места е приведен и примерен код с обяснение под него. При голяма част от въпросите е дадена и оценката на сложността, изразена със съответното означение — точно онова, което се пита на изпит. Материалът съдържа осемдесет и осем изображения — блокови схеми, дървета, графи и таблици. Преподавателят получава готов набор от разработени въпроси, който върши работа като мерило при проверка. Студентът разполага с целия конспект в готов вид — удобно за подготовка в последните дни, когато времето не стига за четене на лекции. Всеки въпрос се преговаря самостоятелно, а подредбата позволява да се тръгне направо от онзи, който предстои.