Ръководство по АСЛС

Ръководството е предназначено за провеждане на лабораторни упражнения по дисциплината “Анализ и синтез на логически схеми”, изучавана от студентите от специалности КСТ и АИУТ при ТУ Варна. Участието на авторите е както следва: теми от 1 до 5 са разработени от гл.ас. Юлка Петкова, темите от 6 до 12 - от гл.ас. Сава Иванов, а последните 4 теми - от гл.ас. Стоян Каров.

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

1. Да се намери най-простата двустъпална реализация на схемата. 7. Да се реализира зададената функция само с 3 мултиплексора 2-1. K (1,2,4,5, 9,10,12,13). 8. Да се реализира зададената функция само с 3 мултиплексора 2-1. K (0,1,5,6, 8,9,13,14). 9. Да се реализира зададената функция само с 3 входови ПЛМ.

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

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

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