Здравейте.
Има въпроси от студенти -- какво да се пише по теми 10 (рек. уравнения) и 19 (схеми от функц. елементи).
За тема 10: това, което сме говорили на лекции, включително и подходящи примери за рек. уравнения с решения. По принцип на изпит не се дават примери; примери се дават при обучение, а изпитът не е обучение (предполага се, че преподавателят знае тези неща). За въпроси 10 и 19 обаче, ако ви се паднат, ще дадете примери. За рекурентните уравнения не сме давали теоретична обосновка на алгоритъма за решаване, така че, ако не дадете и примери, не остава почти нищо. Е, трябва да кажете какво разбирате под "рекурентно уравнение" и да опишете алгоритъма за решаване, но това не е достатъчно. Хубаво е да има и подходящи примери.
За тема 19: както казах, трябва пример. Напълно достатъчен е примерът с двоичния суматор.
!! На лекции не съм дал формална дефиниция на схема от функционални елементи. Дефиницията в учебника е твърде сложна и неясна. Няма да ви искам задължително дефиниция, щом не съм дал такава, но ще е ваш плюс да направите формална дефиниция на това понятие. Ето пример за формална дефиниция на "схема от функционални елементи". И то в прост вариант: само над конюнкция, дизюнкция и отрицание (в учебника се разглежда общия вариант на схема над произволно м-во булеви ф-ии). Фиксираме крайно множество от булеви променливи X={x0, x1, ..., xt}. СХЕМА ОТ ФУНКЦИОНАЛНИ ЕЛЕМЕНТИ НАД X е ориентиран граф без контури, в който всеки връх има ТИП, като типовете са следните:
-- връх тип "вход". Всеки такъв връх е маркиран с точно една променлива от X. Всеки такъв връх има полустепен на входа нула и полустепен на изхода единица.
-- връх тип "функция". Всеки такъв връх е маркиран с точно една функция от конюнкция, дизюнкция и отрицание. Полустепента на входа е равна на броя на променливите на функцията (една или две), а полустепента на изхода е точно единица.
-- връх тип "разклонение". Всеки такъв връх има полустепен на входа точно единица и полустепен на изхода две или повече.
-- връх тип "изход". Има точно един такъв връх. Той има полустепен на входа единица и полустепен на изхода нула.
Ориентираните ребра са сложени съгласно следните правила. От всеки връх-вход реброто е или към връх тип разклонение, или към връх тип функция. От всеки връх тип функция реброто е или към друг връх тип функция (контури не може да има, така че няма и примки), или към връх тип разклонение, или към върха тип изход. От всеки връх тип разклонение всяко излизащо ребро е към връх тип функция.
Това, че настояваме схемата да е граф, е важно. Не може да има "висящи изходи" от елементи (жици, които не отиват никъде), понеже в ориентиран граф всяко ребро има начален връх (родител) и краен връх (дете). По същата причина не може да има "висящи входове" (жици, които не идват от никъде). Единствените елементи с полустепен на входа нула са променливите. Единственият елемент с полустепен на изхода нула е изходът.
Строго формално, схемата на двоичния суматор от лекцията не отговаря на тази дефиниция, защото имаше три изхода, а не един. Но това е козметична дреболия...
------
Това е само синтактичната част от дефиницията, но за изпита стига и това. Ако искате, измислете и семантиката на схемата. Семантиката на такава схема е булева функция, естествено. Тъй като синтактичната дефиниция не е индуктивна, може да не е ясно как да се дефинира функцията-семантика на схемата.
Поздрави,
ММ