[te/upp-2023/a1] Added exercise for additional practice

2 files changed, 270 insertions, 0 deletions

diff --git a/src/teaching/upp-2023/additional1/index.md b/src/teaching/upp-2023/additional1/index.md
new file mode 100644
index 0000000..51209e8
--- /dev/null
+++ b/src/teaching/upp-2023/additional1/index.md
@@ -0,0 +1,269 @@
+# Допълнително упражнение 1 - УПП, 04.11.2023
+
+GitHub classroom: [classroom.github.com/a/nlFuKALw](https://classroom.github.com/a/nlFuKALw)
+
+При изображението &&question трябва да спрете, да помислите и да си отговорите на дадения въпрос.
+Почти винаги ако не може да отговорите, ще имате проблеми в бъдеще с решаването.
+Понякога ще ви спираме и ще ви питаме за тези въпроси.
+
+## Задача - База гаднни
+
+&&warn **Нямате** право да използвате каквито и да е функции, които вие не сте написали, както и неизучаван материал като двуизмерни масиви или динамична памет.
+**Не** употребявайте търсачки, ако ви трябва информация за нещо, ще може да си я изкарате с една проста тестова програма или калкулатор.
+
+<br>
+
+Ще работим върху нещо като база данни, може да си го представете като един файл на Excel.
+Имаме две таблици, за удобство първата ще я наричаме "Таблица А", а втората "Таблица Б".
+Таблица А има максимум 16 реда, като всеки ред е едно цяло число с 9 цифри.
+Таблица Б има максимум 8 реда, като всеки ред е число между 1 и 4294967295.
+
+&&question В какъв тип ще запазим всяка таблица?
+
+В задачата винаги номерираме редовете (числата) на всяка таблица, започвайки от индекс 1.
+Чрез различни комбинации на ред в таблица А и ред в таблица Б получаваме различни стойности.
+Целта на задачата е да направите една система, чрез която може коректно да обработите и "изкарате" стойности от базата данни.
+
+Задачата наистина е голяма, затова е разделена на много стъпки и са дадени примери на всяка стъпка.
+Тествайте обилно!
+
+### Формат на редове в таблици
+
+Гледайки десетичния запис на число (ред) от таблица А, най-лявата цифра е ред в таблица Б, цифрата след нея е тип и останалото е просто някаква стойност.
+Тоест в "531009864", "5" е реда в таблица Б, "3" е типа и "1009864" е някаква стойност.
+Поглеждаме типа и според него правим нещо със стойността от таблица А и реда от таблица Б.
+
+Имайте предвид, че ще наричам "стойност от таблица А" последните 7 цифри, "ред от таблица А" всички 9 цифри.
+Стойност и ред в таблица Б означават едно и също, и отговарят на цялото число от таблицата.
+
+Стойностите от таблица А са винаги ограничени отгоре с най-големия брой битове, които комфортно може да поберем в 7 цифри.
+Тоест 9999999 не е валидна стойност от таблица А, докато 8388608 e.
+
+&&question Колко най-много *битове* можем със сигурност да поберем в 7 цифри?
+
+Понеже редовете са от 1 до 9, ако в таблица А имаме ред 0 правим нещо специално, но това ще видите в бъдеще.
+
+&&question Разбрахте ли как таблиците "изглеждат"?
+
+### a) разделяне на реда от таблица А
+
+Преди да започнем, трябва да имплементираме функция, която разделя дадения ред от таблица А на трите му компонента (ред, тип и стойност):
+
+`getRow` - приема ред от таблица А и указатели към променливи за ред, тип и стойност; не връща нищо  
+В подадените указатели пази съответните стойности от реда
+
+&&question Защо приемаме указатели към променливи? Каква е "сигнатурата" на функцията?
+
+<br>
+**Примери:**
+
+|Извикване|Резултат|
+|---------|--------|
+|getRow(1234567, &row, &type, &value)|row = 0, type = 0, value = 1234567|
+|getRow(12345678, &row, &type, &value)|row = 0, type = 1, value = 2345678|
+|getRow(123456789, &row, &type, &value)|row = 1, type = 2, value = 3456789|
+
+### б) обикновенно число
+
+Ако типа е цифрата "0", тогава стойността в базата данни е някакво число с плаваща запетая.
+Самото число е разделено на две части: цифрите преди запетаята се намират в стойността от таблица А, докато цифрите след запетаята са в реда от таблица Б.
+
+&&question В какъв тип данни трябва да запазим числото? Как ще "слепим" двете му части.
+
+Имплементирайте функция:
+
+`parseNumber` - приема стойност от таблица А и ред от таблица Б; връща полученото число от тези стойности
+
+<br>
+**Примери:**
+*Възможно е отклонението на последния пример да бъде повече от 2 единици*
+
+|Извикване|Резултат|
+|---------|--------|
+|a = parseNumber(1, 5)|a = 1.5|
+|a = parseNumber(0, 37)|a = 0.37|
+|a = parseNumber(913, 0)|a = 913.0|
+|a = parseNumber(8388607, 18446744073709551615)|a = 8388607.18446744073709551615|
+
+### в) числов текст (част едно)
+
+Ако типа е "1", тогава стойността в базата данни е някакъв низ (последователност от букви), която е кодирана в числата.
+Всеки 5 бита в реда (от дясно на ляво) от таблица Б определя буква, като:
+
+|Битове|Десетично число|Буква|
+|------|---------------|-----|
+|00000 |0              |A    |
+|00001 |1              |B    |
+|00010 |2              |C    |
+|...|||
+|11001 |25             |Z    |
+|11010 |26             |*шпация*|
+|11011 |27             |.    |
+|11100 |28             |,    |
+|11101 |29             |:    |
+|11110 |30             |?    |
+|11111 |31             |!    |
+
+Тоест ако в нашия тип данни запазваме само 10 бита, тогава числото "2" ще бъде `0000000001` и имаме низа "AC".
+Игнорирайте старшите битове, които остават като "остатък" (по-малко от 5 бита ширина).
+
+&&question Колко бита наистина запазваме в нашия тип данни? Колко бита ще трябва да игнорираме? Колко най-много букви може да поберем?
+
+Имплементирайте функция:
+
+`decodeNumberText` - приема ред от таблица Б и указател към "низ"; не връща нищо  
+Записва декодиран текстът от реда в указателя
+
+&&question Нарочно има кавички около думата "низ", какъв трябва наистина да е типа на указателя?
+
+<br>
+**Примери:**
+
+|Извикване|Резултат|
+|---------|--------|
+|decodeNumberText(2, decodedText)|decodedText = "AAAAAAAAAAAC"|
+|decodeNumberText(257104811188071551, decodedText)|decodedText = "HELLO WORLD!"|
+|decodeNumberText(1148238614786569150, decodedText)|decodedText = "!. ,:?!. ,:?"|
+
+### г) числов текст (част две)
+
+Дотук добре, обаче не сме свършили съвсем.
+От гледна точка на сигурност, искаме дори някой да получи достъп до таблица Б, да не може да разбере текста дори след като е използвал `decodeNumberText`.
+
+Ще използваме [шифъра на Цезар](https://en.wikipedia.org/wiki/Caesar_cipher): един много прост шифър, където отместваме позицията на всяка буква с няколко места "напред".
+Тоест, при отместаване 3, буквата A става D, B става E, и так. нат.
+Как декодираме?
+Отместваме буквите назад, тоест ако имаме текста "KHOOR" и ви кажа, че съм го кодирал като съм отместил всяка буква напред с 3 позиции, тогава при декодиране от K става на H, от H става на E, от О става на L и от R става на O.
+
+&&question Какво става със знака "!"? Има ли лесен (математически) начин да дешифрираме всяка буква?
+
+Текстът, преди да е въведен в нашата база данни, ще бъде кодиран с шифъра на Цезар, като броя позиции с които сме отместили буквите се намира в стойността в таблица А.
+
+Промененте функцията:
+
+`decodeNumberText` - приема ред от таблица Б, стойност от таблица А и указател към "низ"; не връща нищо  
+След като декодира текста от реда от Б, дешифрира го със стойността от таблица А
+
+<br>
+**Примери:**
+
+|Извикване|Резултат|
+|---------|--------|
+|decodeNumberText(0,  2,                   decodedText)|decodedText = "AAAAAAAAAAAC"|
+|decodeNumberText(0,  257104811188071551,  decodedText)|decodedText = "HELLO WORLD!"|
+|decodeNumberText(0,  1148238614786569150, decodedText)|decodedText = "!. ,:?!., :?"|
+|decodeNumberText(17, 632247276719883827,  decodedText)|decodedText = "AAAAAAAAAAAC"|
+|decodeNumberText(3,  368677860020992194,  decodedText)|decodedText = "HELLO WORLD!"|
+|decodeNumberText(30, 1073856582231288700, decodedText)|decodedText = "!. ,:?!., :?"|
+|decodeNumberText(32, 1148238614786569150, decodedText)|decodedText = "!. ,:?!., :?"|
+
+### д) масив (част едно)
+
+Ако типа е "2", тогава в реда от Б сме вложили масив от стойности (числа).
+Всеки 4 бита определят една стойност, като първия елемент е старшите (най-левите) битове, докато последния е младшите (най-десните) битове.
+
+&&question Коколо на брой елемента пазим в реда от Б?
+
+Имплементирайте функцията:
+
+`decodeArray` - приема ред от таблица Б и указател към масив; не връща нищо  
+Декодира елементите от реда и ги запазва в указателя
+
+<br>
+**Пример:**
+
+|Извикване|Резултат|
+|---------|--------|
+|decodeArray(846406911526255600, arr)|arr = { 0, 11, 11, 15, 0, 10, 9, 10, 0, 0, 15, 5, 3, 11, 15, 0 }|
+
+### е) масив (част две)
+
+От гледна точка на сигурност или оптимизране на памет, искаме да "лимитираме" какви стойности са валидни, и всички невалидни да станат някоя друга стойност по подразбиране.
+Така може да запазим няколко различни масива на едно и също място, спестявайки малко памет, или да "вмъкнем" ненужни стойности, така че дори някой да получи масива, да не знае кои стойности са истински и кои фалшиви.
+
+В старшите 20 бита от стойността в таблица А ще пазим общо 5 възможни валидни стойности, а в останалите (младши) 3 бита ще пазим индекс към тези стойности, който индекс (започвайки от 1) определя стойността по подразбиране.
+
+Пример: ако имаме побитово `1111100000100011101101010101`, тогава:
+
+- валидните числа са `11111, 00000, 10001, 11011 и 01010`
+- числото по подразбиране е 5-тото (`101 = 5`), което е числото `01010`
+- ако от реда в Б изкараме `11011`, тогава го запазваме, обаче ако изкараме примерно `11000` тогава го превръщаме в стойността по подразбиране, а именно `01010`
+
+Разширете функцията:
+
+`decodeArray` - приема стойност от таблица А, ред от таблица Б и указател към масив; не връща нищо  
+Декодира елементите от реда, като всички невалидни стойност се превръщат в стойността по подразбиране, и ги запазва в указателя
+
+<br>
+**Примери:**
+
+|Извикване|Резултат|
+|---------|--------|
+|decodeArray(360537, 846406911526255600, arr)|arr = { 0, 11, 11, 11, 0, 11, 11, 11, 0, 0, 11, 11, 11, 11, 11, 0 }|
+|decodeArray(3119812, 846406911526255600, arr)|arr = { 8, 8, 8, 15, 8, 8, 8, 8, 8, 8, 15, 5, 3, 8, 15, 8 }|
+
+### ж) компресирани стойности
+
+Ако редът в таблица А е 0, тогава цялата стойност в базата данни е побрана в стойността на таблица А.
+Очевидно само в стойност на таблица А имаме по-малко битове, отколкото в стойност на таблица А плюс ред в таблица Б, затова се налага по някакъв начин да "компресираме" информацията, така че да се побере.
+
+&&question Колко бита побираме в стойност на таблица А? Колко бита ни трябват общо, за да обработим една стойност в базата данни?
+
+Ще го направим така: в стойността от таблица А ще пазим индекси, и всеки индекс ще съответства на някакво по-голямо число, което се съдържа в друг масив, който ще наричаме криптографски ред.
+
+Пример (всички числа са представени двоично; стойностите не са напълно валидни за базата данни, но са логически коректни):
+
+<!--                   000    001    010    011    100    101 -->
+- Kриптографски ред е `00000, 10101, 11011, 10001, 01101, 10100`
+  - Индексираме от 0 до 5, което побитово е от 000 до 101
+- Стойност в таблицата А е `011001000001101101`
+  - Разделяйки го на индекси, това са `011, 001, 000, 001, 101, 101`
+- Слепвайки от криптографския ред на тези индекси получаваме `100011010100000101011010010100`
+
+Във вашата програма ще се наложи да направите още една променлива, в която пазите криптографския ред.
+Всяка стойност в реда ще съдържа 21 бита.
+Първите (най-левите) три бита от стойността в таблица А не са индекси, а трябва да се копират дословно.
+След тях има 4 индекса, всеки с по 5 бита.
+
+&&question Как е разделена побитово една стойност от таблица А? Кои индекси за кои стойности ще се ползват? Достатъчно ли е всеки индекс към криптографския ред да бъде само 5 бита (тоест може ли да има повече от 2&#8309; числа в реда)? Защо имаме само 4 индекса?
+
+Напишете функция:
+
+`decompress` - приема стойност от таблица А, криптографски ред, указател за запазване на декомпресираната стойност от таблица А и указател за запазване на декомпресирания ред от таблица Б; не връща нищо
+
+<br>
+**Примери:**
+
+|Извикване|Резултат|
+|---------|--------|
+|crypt = { 0, 2, 5 }<br>decompress(32770, crypt, &decompA, &decompB)|decompA = 1, decompB = 5|
+|crypt = { 2097151 }<br>decompress(7340032, crypt, &decompA, &decompB)|decompA = 8388607, decompB = 18446744073709551615|
+
+### з) входни данни
+
+В началото на програмата получавате броя на редове от таблица А (между 1 и 16), след това толкова "реда".
+След това броя редове от таблица Б (между 1 и 8), след това толкова реда.
+Накрая получавате размера на криптографския ред (между 1 и 64) и толкова стойности.
+
+### и) четене от базата данни
+
+След това получавате команди (знак):
+
+- `g X`: изкарвате на екрана стойността в базата данни, започвайки с ред X от таблица А
+- `i`: Връщате информация за базата данни
+- `q`: спиране на програмата
+
+### й) заявки
+
+- `t X`: връщате броя и след това всички редове от таблица А с тип X
+- `r X`: връщате броя и всички редове от таблица А, които използват реда Х  
+  Ако реда е 0, тогава трябва да върнете и размера на криптографския ред
+
+### к) презаписване в базата данни
+
+- `w T R V`: запазвате (презаписвате) стойност V в таблица Т (може да бъде `A` или `B`) на ред R
+- `s T V`: запазвате стойност V от тип Т в базата данни  
+  Пробвате се да я запазите, използвайки и двете таблици, но ако Б вече е запълнена, добавяте я като компресирана стойност в таблица А.
+  Ако и А е запълнена, изкарвате съобщение за запълнена база данни и не запазвате стойността.
+
+&&question Какво трябва да направите, ако получите компресирана стойност за таблица А?
diff --git a/src/teaching/upp-2023/index.md b/src/teaching/upp-2023/index.md
index 943f701..d7ff895 100644
--- a/src/teaching/upp-2023/index.md
+++ b/src/teaching/upp-2023/index.md
@@ -22,3 +22,4 @@
 |3 |20.10.2023|[Преговор](./week3/revision.html?a) \|\| [Задачи](./week3) \|\| [Решения](https://github.com/Syndamia/upp-2023-solutions/tree/main/week03)|
 |4 |27.10.2023|[Преговор](./week4/revision.html?a) \|\| [Задачи](./week4) \|\| [GitHub classroom](https://classroom.github.com/a/jqKaO1ny) \|\| [Решения (само 1ва)](https://github.com/Syndamia/upp-2023-solutions/tree/main/week04)|
 |5 |03.11.2023|[Преговор](./week5/revision.html) \|\| [Задачи](./week5) \|\| [GitHub classroom](https://classroom.github.com/a/3KoIQ71H)|
+||04.11.2023|[Допълнително упражнение 1](./additional1/) \|\| [GitHub classroom](https://classroom.github.com/a/nlFuKALw)|