Държавен изпит на Компютърни Науки

http://www.fmi.uni-sofia.bg/exams

КОНСПЕКТ ЗА ДЪРЖАВЕН ИЗПИТ ЗА СПЕЦИАЛНОСТ "КОМПЮТЪРНИ НАУКИ"

konsp_DI_KN.pdf

(това е линк, кликни на картинката)

ОСНОВИ НА КОМПЮТЪРНИТЕ НАУКИ

1. Основни комбинаторни принципи и формули. Рекурентни отношения.
2. Графи. Дървета. Обхождане на графи.
3. Булеви функции. Пълнота. Съкратена ДНФ на БФ.
4. Крайни автомати. Регулярни изрази. Теорема на Клини.
5. Контекстно-свободни граматики и езици. Стекови автомати.
6. Сложност на алгоритъм. Асимптотично поведение на целочислени функции (О-, -, Θ-, ο- и ω-нотация). Сложност на рекурсивни програми.
7. Алгоритми в графи с тегла на ребрата. Оценки за сложност.
8. Динамично програмиране. Оценки за сложност.

ЯДРО НА КОМПЮТЪРНИТЕ НАУКИ

9. Компютърни архитектури. Формати на данните. Вътрешна структура на централен процесор – блокове и конвейрна обработка, инструкции.
10. Структура и йерархия на паметта. Сегментна и странична преадресация. Система за прекъсване – приоритети и обслужване.
11. Файлова система. Логическа организация и физическо представяне.
12. Управление на процеси и междупроцесни комуникации.
13. Компютърни мрежи и протоколи – OSI модел. Канално ниво. Маршрутизация. IP, TCP, HTTP.
14. Процедурно програмиране - основни информационни и алгоритмични структури.
15. Обектно ориентирано програмиране. Основни принципи. Класове и обекти. Наследяване и инкапсулация. Параметричен полиморфизъм.
16. Структури от данни. Стек, опашка, списък, кореново дърво. Основни операции върху тях. Реализация.
17. Обща характеристика на функционалния стил на програмиране. Дефиниране и използване на функции. Модели на оценяване. Функции от по-висок ред. Списъци. Потоци и отложено оценяване.
18. Термове и формули на предикатното смятане от първи ред. Хорнови клаузи. Унификация. Mетод на резолюцията в предикатното смятане от първи ред.
19. Релационен модел. Нормални форми.
20. Търсене в пространството от състояния. Генетични алгоритми.

МАТЕМАТИКА И ПРИЛОЖЕНИЯ

21. Симетрични оператори в крайномерни евклидови пространства. Основни свойства. Теорема за диагонализация.
22. Симетрична и алтернативна група. Действие на група върху множество. Теорема на Кейли и формула за класовете.
23. Теореми за средните стойности ( Рол, Лагранж и Коши). Формула на Тейлър.
24. Определен интеграл. Дефиниция и свойства. Интегруемост на непрекъснати функции. Теорема на Нютон-Лайбниц.
25. Уравнения на права и равнина. Формули за разстояния.
26. Итерационни методи за решаване на нелинейни уравнения.
27. Дискретни разпределения. Задачи, в които възникват. Моменти – математическо очакване и дисперсия.

ЛИТЕРАТУРА

1. Азълов, П., Бази от данни. Релационен и обектен подход, Техника, София, 1991.
2. Боянов, К., Хр. Турлаков, Д. Тодоров, Л. Боянов, Вл. Димитров, В. Желязков, Принципи на работа на компютърните мрежи. ИНТЕРНЕТ, Апиинфо- център Котларски, 2003.
3. Въндев, Д., Записки по теория на вероятностите, Eлектронно издание: http://fmi.uni-sofia.bg/fmi/statist/personal/vandev/lectures/prob/prob.htm
4. Горслайн, Дж., Фамилия Intel 8086/8088 , Техника, София, 1990.
5. Димитров, Б., К. Янев, Вероятности и статистика, Университетско издателство “ Св. Кл. Охридски”, София, 1998.
6. П. Джаков, Р. Леви, Р. Малеев, С. Троянски, Диференциално и интегрално смятане, ФМИ-СУ, София, 2004.
7. Дойчинов, Д., Математически анализ, Университетско издателство “ Св. Кл. Охридски”, София, 1994.
8. Комър, Бр., TCP/IP мрежи и администриране, ИнфоДар, 1999.
9. Майерс, С., По-ефективен C++. 35 нови начина да подобрите своите програми и проекти, ЗеСТ Прес.
10. Манев, Кр., Увод в дискретната математика, IV изд., КЛМН, София, 2005.
11. Манна, З., Математическа теория на информатиката, Наука и изкуство, София, 1983.
12. Метакидес, Д., А. Нероуд, Принципи на логиката и логическото програмиране, Виртех, София, 2000.
13. Николов, Л., Операционни системи, Сиела, София, 1998.
14. Нишева, М., П. Павлов, Функционално програмиране на езика Scheme , София, 2004.
15. Седжуик, Р., Алгоритми на С, ч.1-4: Основи, структури от данни, сортиране, търсене, СофтПрес
16. Сидеров, Пл., Записки по алгебра: линейна алгебра, Веди, София, 1994.
17. Сидеров, Пл., К. Чакърян, Записки по алгебра: групи, пръстени, полиноми, Веди, София, 1995.
18. Скордев, Д., Логическо програмиране ( записки). Електронно издание: http://www.fmi.uni-sofia.bg/fmi/logic/skordev/ln/lp/new/sydyrzha.htm
19. Сосков, И., А. Дичев, Теория на програмите, Университетско издателство “Св. Кл. Охридски”, София, 1996.
20. Станилов, Гр., Аналитична геометрия, Софтех, София, 1998.
21. Стивенс, У. UNIX: взаимодействие процессов. СПб.: Питер, 2003.
22. Тодорова, М., Езици за функционално и логическо програмиране, I ч.: Функционално програмиране. Сиела, София, 2003.
23. Вирт, Н., Алгоритми + структури от данни = програми, BG soft group, София. 6
24. Cormen, T., Ch. Leiserson, R. Rivest, Introduction to Algorithms , MIT Press, 1990.
25. H. Lewis., Chr. Papadimitriou, Elements of the theory of computation., Second edition, Prentice-Hall, 1998.
26. Nilsson, U., J. Maluszynski, Logic, Programming and Prolog (2nd ed.). John Willey & Sons, 1995. Електронно издание: http://www.ida.liu.se/~ulfni/lpp/
27. Stallings, W., Computer Organization and Architecture. Design for Performance, Prentice Hall, 2000. http://www.williamstallings.co m/COA5e.html
28. Stevens W.R. Advanced Programming in the UNIX Environment , AddisonWesley, Reading, Mass, 1992.
29. Tanenbaum, A., Structured Computer Organization . Prentice Hall, 2002.
30. Tanenbaum, A., Modern Operating systems, 2nd ed., Prentice Hall, 2002.
31. Tannenbaum A., Computer Networks , 3th ed., 4th ed., Prentice Hall.
32. H. Garcia-Molina, J. Ullman, J.Widom, Database Systems: The Complete Book, Prentice Hall, 2002.
33. Е. Любенова, П. Недевски, К. Николов, Л. Николова, В. Попов, Ръководство по Математически анализ, София, 1998.
34. Stuart Russel & Peter Norvig, Artificial Intelligence: A Modern Approach. Prentice Hall, 2003.
35. Тодорова, М., Програмиране на C++ , I и II част. Ciela, София, 2002.
36. Stroustrup, B., C++ Programming Lanquage . Third Edition, Addison-Wesley, 1997.
37. Bruce Eckel, Thinking in Java . Prentice Hall, 4th ed., 2006 (Да мислим на Java , превод и издание на български език).
38. Timothy Budd, An Introduction to Object-Oriented Programming . Addison Wesley, 3rd ed., 2002.
39. Андреев, А. и др., Сборник от задачи по числени методи, Университетско издателство “ Св. Кл. Охридски”, София, 1994.
40. Боянов, Б., Лекции по числени методи, Дарба, София, 1998.
41. Димова, Ст., Т. Черногорова, А. Йотова, Лекции по числени методи за диференциални уравнения, ел. Издание: http://fmi.uni-sofia.bg/econtent/chmdu
42. Сендов, Бл., В. Попов, Числени методи, I ч., Университетско издателство “Св. Кл. Охридски”, София, 1996.
43. Сендов Бл., В. Попов, Числени методи, II ч., Наука и изкуство, София, 1978.

Какво се падна досега (а.к.а. Пак на нас късата клечка…)

DI-KN-july-09.pdfDI-KN-septemvri-09.pdfINF-KN.pdfKN-zadachi-07-2008.pdfKN-zadachi-09-2008.pdfKN-zadachi-07-2010.pdfKN-zadachi-09-2010.pdf

Държавен изпит 2012

Задачи от държавен изпит 2012
Задачи от държавен изпит септември 2012

Държавен изпит 2013 - КН

Юли:

зад.1 Даден е клас от 17 ученика, от които 10 момчета и 7 момичета. На контролно всеки ученик сам може да избере да работи по 1 от общо 4 теми. Какви са възможните избори на учениците, т.ч. точно 3 от 7-те момичета да работят по тема номер 2.

зад.2 Да се детерминира краен автомат.

зад.3 Да се напише сортираща функция, която приема масив от низове и функция (comprator), която служи за сравнение на низовете.

зад.4 Да се напише функция, която по 2 node-a в двоично дърво, намира най-ниския им общ предшественик.

зад5. Да се реализира йерархия - клас Task и клас RecurringTask. За всеки Task се пази име и време на изпълнение(в брой часове). За RecurringTask се пази и брой повторения. Всеки клас трябва да има следните методи:
- getTotalTime - общо време за изпълнение на задачата (при recurring e repeatCount * time)
- print - извежда на стандартния изход име и общо време за изпълнение
- printShorter(Task[] tasks) - да се извика print() за тези таск-ове от масива, на които общото им време за изпълнение е по-малко от това на таск-а върху, който методът се вика

зад.6 Да се напише на Scheme/Haskell функция leaves t k, която по двоично дърво t и цяло число k връща списък от всички върхове на дървото от ниво k.

зад7. Даден е граф с цени по ребрата, начален връх a и краен връх z, евристична функция h(x) = предполагаема цена от връх х до z. Търсим път между a и z. Какъв ще бъде намереният път и каква ще е последователността от обходени върхове при:
- breadth-first search
- best-first search
- A*

зад8. Бази данни - да се избере коя заявка извежда определен резултат. (multiple choice)

зад9. Дадени са n плика e1,e2,…,en. Всеки има размери xi и yi. Да се намери максималният брой пликове, които могат да се сложат 1 в друг. За да можем да сложим 2 плика 1 в друг трябва xi < xj и yi < yj.

Теми:
- 1ва група - тема 1 (комбинаторни конфигурации), тема 17 (функционално програмиране)
- 2ра група - тема 7(алгоритми в графи), тема 13 (мрежи)

Септември:
зад 1. Дадена е 6-стенна призма. Всяка може да е оцветена в един от 4 цвята. Колко са възм. оцветявания, в които има точно 2 сини околни стени.
зад 2. Минимизиране на автомат
зад 3. В клетките на „дъска“ nxm са разположени монети с дадени стойности. Да се формулира „бърз“ алгоритъм, който намира оптималния (най-много монети) път от долния ляв до горния десен ъгъл. Движения само надясно и нагоре.
зад 4. Да се направи функция, която взима за аргументи матрица от думи (String-ове) и масив от знаци (char[]). Функцията да изпише конкатениран реда от матрицата, в който има най-много думи, съдържащи знаци от масива.
зад 5. Да се реализира интерфейс/абстр. клас Set, описващ целочислено множество с методи member(int) и print(), които служат съответно за проверяване дали даден елемент принадлежи на множеството и принтиране на информация за множеството. Да се реализират класове за множество на кратните на k числа и множеството на числата в интервала [a;b]. Да се напише функция, която по зададено число и списък от множества извиква print() за всички мн-ва, в които числото не принадлежи.
зад 6. a) да се напише функция, проверяваща дали в дадено двоично дърво стойностите на върховете са уникални b) да се напише функция, проверяваща дали двоично дърво е наредено (BST)
зад 7. Scheme/Haskell - Да се напише (mono t k), която за двоичното дърво t връща списък на всички върхове, които имат k непразни поддървета. Очевидно k е между 0 и 2.
зад 8. Да се съпоставят DFS и beam search в/у зададен граф. Иска се да се напишат само оптималните маршрути и обходените върхове.
зад 9. Бази данни, multiple choice.

Теми: 6 (сложност на алгоритъм) и 16 (структури от данни - стек и двоично дърво)

Държавен изпит 2015 - Юли месец

Теми Анализ 1 и Алгебра 1 ПЪРВИТЕ ТЕМИ БЯХА САМО МАТЕМАТИКИ (и за двете стаи), АИ и ОС, Мрежи и СДП

зад1 Да се реалицира на C++ съответна функция, която приема матрица float A[][] с големина NxM ( 0 < N,M <= 10), и извежда на екрана нова матрица с големина N/2 x M/2, и всеки нейн елемент [x1][y1] е средно аритметичо на тези елементи x,y от A, т.че
x <= x1 <= x*2
y <= y1 <= y*2
зад2 Да се напишат съответните задачи на C++, без STL. Реализацита на дърво с динамичен брой наследници и key от тип int.
a) Да се реалицира структура за съответното дърво.
struct node {
int key;
node** nexts;
int countNexts;
}
б) Да са реализира search функция, която проверява дали даден int eлемент се съдържа в дървото.
в) Да се реализира clear функция, която премахма тези елементи, които съдържат нечетен брой наследници(?)
зад3 Функционално - 2 подточки с по 3 парчета код - избираш една от двете подточки и пишеш какво ще изведе съответния код. И в двете се съдържа и скийм и хаскел.
зад4 Баш, подобна като трета задача от юли 2014год.
зад5 Детерминизиране и минимизация на автомат.
зад6 Даден е неориентиран граф, без примки, такъв че от всеки връх има точно по 3 ребра.
а) да се докаже, че няма такъм граф с по-малко от 6 върха.
б) има ли такъв със 6 върха? - ДА
зад7 Бази от данни - 2 подточки
зад8 Интеграл от 0 до 1/2 arcsin(x) dx

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License