Di Zad2012

Задачи и решения от изпита през 2012

Тази страница бе започната, защото от университета не пожелаха да дадат задачите от миналата година(2011), когато те бяха поискани. Задачите са плод на добрата памет на авторите, така че е възможно да има грешки и неточности. Ако някой забележи такива, моля да ги поправи.

Общият брой точки от задачите е 110 т., като за отличен е над 60 точки. Времето за работа - 3 астрономически часа.

1 Задача (10 т.)

Имаме масив от летища A[1…n]. За всяко летище A[i] имаме даден списък на съседите, чрез който се предоставя информация до кои летища A[i] има директна връзка, като всяко едно летище не може да има директно връзка със себе си. Да се напише възможно най-бърз алгоритъм (асимптотически), който извежда "Yes" в случай, че съществува летище, такова че ако тръгнем от него, то след няколко директни прехода ще стигнем отново до него, и "No" в противен случай.

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

2 Задача (10 т.)

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

Пример: имаме 6 предмета с цени: 1 8 6 3 2 4
Възможно разбиване е {1, 6, 3, 2} и {8, 4}, тъй като 1 + 6 + 3 + 2 = 8 + 4.

Решение:

покажи

Този тип алгоритмични задачи спада към категорията динамично програмиране. Примерно решение в случая е, ако използваме схемата на Задачата за раницата, като в случай обемите на предметите ще съвпадат с техните цени, а обемът на раницата ще бъде (цената на всички предмети / 2). Естествено, сумарната цена на предметите трябва да е четно число, иначе няма какво да търсим.

3 Задача (10 т.)

Даден е сортиран масив от цели числа. Имаме клас Node (Java вариант), предоставящ възел в двоично дърво:

class Node {
    public int Data;
    public Node Left;
    public Node Right;
}

Да се напише функция buildTree(int[] array), която построява двоично балансирано дърво за търсене, съдържащо елементите на масива.
Езикът за програмиране може да е C++/Java.
Припомняме какво е двоично балансирано дърво за търсене:
- всеки връх има най-много 2 наследника;
- всички възли, намиращи се вляво от конкретен възел, са по-малки или равни на него (относно полето Data), а всички вдясно - по-големи или равни на него;
- разликата между височината на лявото поддърво и тази на дясното е най-много едно.

Решение:

покажи

Примерна Java имплементация:

public Node buildTree(int [] array)
{
     return buildTree(array, 0, array.length - 1);
}

public Node buildTree(int[] array, int start, int end)
{
     int middle = (start + end + 1) / 2;
     Node node = new Node();
     node.Data = array[middle];
     if (middle - 1 >= 0)
     {
           node.Left = buildTree(array, start, middle - 1);
     }

     if (middle + 1 < array.length)
     {
           node.Right = buildTree(array, middle + 1, end);
     }

     return node;
}

4 Задача (10 т.)

Да се напише на езика Scheme или на Haskell (по избор) процедурата countLists, която при подаден списък от списъци - връща броя на списъците, които съдържат поне по един елемент от другите списъци. Ето пример:
(countLists '((1 2 3) (3 4 5) (3 6 7) (4 1 8) (3 2 1))) -> 3

Забележка: С риск да объркам някого - хората искаха да покажем броя на тези елементи на фамилията от множества, които всъщност са трансверзали за фамилията (справка за трансверзала - логическо програмиране / теория на множествата)

Решение:

покажи

Примерно решение на Haskell. Кодът може са се подобри.
Github gist с решението, за по-цветно - https://gist.github.com/3487437

import Data.List

-- Фунцкията проверява дали между двата списъка има поне 1 общ елемент
-- пример - между [1,2,3] и [4,5,6] няма да има общ елемент и няма да съвпада с условието на задачата
-- функцинята nub връща списък от уникални елементи
containsOneElement :: Eq a => [a] -> [a] -> Bool
containsOneElement a b = (length (a ++ b) /= length (nub (a ++ b)))

-- фунцията проверява дали check изпълнява условието с всеки един от подсписъците на [[a]]
checkEach :: Eq a => [a] -> [[a]] -> Bool
checkEach check [] = True
checkEach check (x:xs) = (containsOneElement check x) && (checkEach check xs)

-- тъй като ни интересува дали всеки списък отговаря на условията
-- рекурсията добавя текущият списък към края на списъкът от списицъ, за да не губим елементи
-- поради тази причина, тази функция следи с параметъра counter дали сме минали всички елементи
-- функцията връща отговора на задачата
solve1 :: Eq a => [[a]] -> Int -> Int -> Int
solve1 (x:xs) len counter
    | len == counter = 0
    | checkEach x xs  == True = 1 + (solve1 (xs ++ [x]) len (counter + 1))
    | otherwise = 0 + (solve1 (xs ++ [x]) len (counter + 1))

-- основната функция, която се вика с аругмент списък от списъци
solve :: Eq a => [[a]] -> Int
solve a = solve1 a (length a) 1

5 Задача (15 т.)

Да се дефинира абстрактен клас, представящ обекта превозно средство - информацията, която се съхранява, е годината на производство на превозното средство. Да се имплементират класове, представящи обектите кола и автобус (наследявайки базовия клас). Класът за кола съхранява параметър, определящ типа на колата - седан, кабрио или комби. Класът за автобус има параметър, съхраняващ информация за максималния брой пътници, които може да събере. И двата класа имат член, извличащ тяхната такса при престой на паркинг. При автомобил таксата се определя по следния начин: година на произвеждане се умножава по 2, в случай че типът на колата е седан или кабрио, или по 3, ако типът е комби. При автобусите: годината на произвеждане се умножава по броя пътници.
Да се предостави вътрешен начин за извличане на общия брой създадени превозни средства в цялата йерархия от класове.
Да се имплементира клас, представящ обекта паркинг. Паркингът има параметър, указващ максималния брой места. Да се дефинират методи за добавяне (в края на паркинга) и изтриване (от края на паркинга) на превозно средство. Да се дефинира метод, който изчислява таксата на всички превозни средства, стоящи на паркинга в момента.

Език за програмиране: Java/C++

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

6 Задача (10 т.)

Даден е двоичен файл и в него са записани обекти от тип:

struct Person {
    int Age;
    char[40] Name;
}

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

Забележка: тъй като не бяхме учили C и такъв курс не присъства в нашия учебен план, комисията позволи да се ползва Java като обектът Person би трябвало да приеме вида:

class Person {
    public int Age;
    public String Name;
}

7 Задача (10 т.)

Нормална задача по бази от данни, както от миналите години. Задачата се състои от две подточки и се пита при всяка една от тях - коя заявка е правилна (отговаря на дадено условие), като има по 4 възможни отговора. Базата, която се използваше, беше известната SHIPS.

8 Задача (10 т.)

Нека $\mathcal{L}$ е език на предикатно смятане от 1ви ред с единствен триместен предикатен символ $p$. Нека $A_n$ е множество от структури за $\mathcal{L}$ с универсум $\{1, 2, \ldots, n\}$. Нека $B_n$ са онези от тях, в които е вярна формулата $\forall x p(x, x, x)$. Да се намери границата $\lim_{n \to \infty} \frac{A_n}{B_n}$
Решение:

покажи

Знаем, че структурата представлява наредена двойка от универсум и интерпретация. В случая универсума ни е фиксиран и нека си го означим с $C_n = \{1,2, \ldots, n\} =>$ трябва да преброим само възможните интерпретации за структурите в $A_n$ и $B_n$. $\mathcal{L}$ има само един триместен предикатен символ => за всяка интерпретация от структура за $\mathcal{L}$ е вярно, че
$I(p) \subseteq C_n x C_n x C_n =>$ всички възможни наредени тройки за предиката $p$ в $I$ са $|C_n x C_n x C_n| = |C_n|*|C_n|*|C_n| = n * n * n = n^3$, но ние търсим броя на всички подмножества от този тип => възможните интерпретации са $2^{n^3} => A_n = 2 ^{n^3}$

Разсъждаваме за $B_n$ аналогично. Нататък по - късно

9 Задача (15 т.)

Дадена е матрицата:

(1)

\begin{align} A = \begin{pmatrix} 0 & 1 & -1 & 1 \\ 1 & 0 & 1 & -1 \\ -1 & 1 & 0 & 1 \\ 1 & -1 & 1 & 0 \end{pmatrix} \end{align}

Да се намерят диагонална матрица $D$ и ортогонална матрица $T$, такива че $D= TAT^{-1}$.
Решение:

покажи

Алгоритъмът за решаването на тези задачи е следният:
1. Намираме характеристичните корени на матрицата $A$ (тъй като $A$ е симетрична, то те са реални числа):

(2)

\begin{align} f_A(\lambda)=det(A-\lambda E) = \begin{vmatrix} -\lambda & 1 & -1 & 1 \\ 1 & -\lambda & 1 & -1\\ -1 & 1 & -\lambda & 1\\ 1 & -1 & 1 & -\lambda \end{vmatrix}=p^4-6p^2+8p-3=(p-1)^3(p+3). \end{align}

Така получаваме трикратен корен $\lambda_{1,2,3}=1$ и еднократен $\lambda_4 = -3$. Тези корени са все още известни с името собствени стойности на оператора $\varphi$, чиято матрица е матрицата $A$. По главния диагонал на търсената матрица $D$ стоят намерените корени, като всеки от тях участва толкова пъти, колкото е кратността му, т.е.

(3)

\begin{align} D= \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -3 \end{pmatrix} \end{align}

2. За всеки характеристичен корен $\lambda$ на матрицата $A$ намираме ортонормиран базис на пространството $V_{\lambda}= \{a|Aa^t=\lambda a\} = \{a|\varphi(a)=\lambda a\}$, т.е. намираме собствените вектори на оператора $\varphi$ посредством намиране на фундаментална система решения (ФСР) на хомогенната система с матрица $A-\lambda E$, след това ортоганилизраме получените вектори по метода на Грам-Шмид и накрая ги нормираме:
- За $\lambda_{1,2,3}=1$ получаваме решението $(p-q+r,p,q,r)$, т.е. ФСР на системата тук е линейната обвивка на векторите:
$a_1 = (1,0,0,1), a_2 = (-1,0,1,0)$ и $a_3 = (1,1,0,0)$. Ортоганилизараме тези вектори по метода на Грам-Шмид:
$b_1 = a_1 = (1,0,0,1)$
$b_2 = a_2 - \frac {(a_2, b_1)} {(b_1, b_1)} b_1= \frac {1}{2} (-1,0,2,1)$
$b_3 = a_3 - \frac {(a_3, b_1)}{(b_1, b_1)} b_1 - \frac {(a_3, b_2)}{(b_2, b_2)} b_2 = \frac {1}{3}(1,3,1,-1)$
Нормираме и окончателно получаваме:
$e_1 = \frac{1}{\sqrt2}(1,0,0,1)$
$e_2 = \frac{1}{\sqrt6}(-1,0,2,1)$
$e_3 = \frac{1}{2\sqrt3}(1,3,1,-1)$
- За $\lambda_4=-3$ получаваме решението $(p,-p,p,-p)$, т.е. примерна ФСР тук е линейната обвивка на вектора $a_4 = (1,-1,1,-1).$
Нормираме и получаваме $e_4 = \frac{1}{2}(1,-1,1,-1)$. Както знаем, собствените вектори, съответстващи на различни собствени стойности, са ортогонални помежду си, следователно $e_4$ е ортогонален на $e_1, e_2, e_3$.

3. Търсената матрица $T$ всъщност представлява матрицата на прехода от стандартния базис към базис, в който матрицата на оператора $\varphi$ е диагоналната матрица $D$. Тази матрица се състои от получените собствени вектори:

(4)

\begin{align} T= \begin{pmatrix} \frac{1}{\sqrt2} & -\frac{1}{\sqrt6} & \frac{1}{2\sqrt3} & \frac{1}{2} \\ 0 & 0 & \frac {\sqrt3}{2} & -\frac{1}{2} \\ 0 & \frac{2}{\sqrt6} & \frac{1}{2\sqrt3} & \frac{1}{2} \\ \frac{1}{\sqrt2} & \frac{1}{\sqrt6} & -\frac{1}{2\sqrt3} & -\frac{1}{2} \end{pmatrix} \end{align}

Тъй като матрицата $T$ е ортогонална, то $T^{-1} = T^t$, с което задачата е приключена.

10 Задача (10 т.)

Да се реши неопределения интеграл:

$\int \frac{dx}{x(ln^2x + 1)^2}$
Решение:

покажи

Задачата не е трудна, по - скоро неочаквано дадоха интеграл за разлика от минали години. Решението е следното:

(5)

\begin{align} \int \frac{dx}{x(ln^2x + 1)^2} = \int \frac{dlnx}{(ln^2x + 1)^2 } \stackrel{t=lnx}{=} \int \frac{dt}{(t^2+1)^2} = \int \frac { (t^2-t^2+1)dt}{(t^2+1)^2} = \int \frac {(t^2+1)dt}{(t^2+1)^2} - \int \frac {t^2} {(t^2+1)^2} = \int \frac {dt}{t^2+1} -\frac {1} {2} \int \frac {tdt^2}{(t^2+1)^2} = \end{align}

(6)

\begin{align} arctgt - \frac {1} {2} \int \frac {td(t^2+1)}{(t^2+1)^2} = arctgt +\frac {1} {2} \int t d \frac {1}{1+t^2} \stackrel{ИЧ}{=} arctgt + \frac {1} {2} \frac {t}{1+t^2} - \frac {1}{2} \int \frac {dt}{1+t^2} = \frac {1}{2} (arctgt + \frac {t}{1+t^2}) = \frac {1}{2}(arctglnx + \frac {lnx}{1-(lnx)^2}) + const \end{align}