Конспект за държавен изпит за завършване на



Дата23.03.2017
Размер264.76 Kb.
#17603
ТипКонспект


СОФИЙСКИ УНИВЕРСИТЕТ “СВ. КЛ. ОХРИДСКИ”

ФАКУЛТЕТ ПО МАТЕМАТИКА И ИНФОРМАТИКА

КОНСПЕКТ

ЗА
ДЪРЖАВЕН ИЗПИТ ЗА ЗАВЪРШВАНЕ НА
ОБРАЗОВАТЕЛНО-КВАЛИФИКАЦИОННАТА

СТЕПЕН “БАКАЛАВЪР”
СПЕЦИАЛНОСТ “ИНФОРМАТИКА”
Приет на Факултетен съвет на 07.05.2007 г.
СОФИЯ  2007
КОНСПЕКТ ЗА ДЪРЖАВЕН ИЗПИТ

ЗА СПЕЦИАЛНОСТ "ИНФОРМАТИКА"




ОСНОВИ НА ИНФОРМАТИКАТА





  1. Булеви функции. Теорема на Пост - Яблонски за пълнота.

  2. Крайни автомати. Регулярни изрази. Теорема на Клини.

  3. Графи. Дървета. Обхождане на графи. Минимално покриващо дърво.

  4. Семантика на рекурсивните програми с предаване на параметрите по стойност.

  5. Релационна алгебра. Релационно смятане. Нормални форми.

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

  7. Компютърни системи – основни принципи за осъществяване на входно-изходния обмен. Входно-изходни процесори и канали, общи шини и магистрали. Прекъсвания – приоритети и обслужване. Видеомонитор, видеоконтролер и клавиатура. Дискови интерфейси и устройства. Принтери.

  8. Файлова система. Логическа организация и физическо представяне. Основни системни примитиви.

  9. Компютърни мрежи. Еталонен модел и видове мрежи. Канално ниво и HDLC. Канал ЕТЕРНЕТ – метод на достъп и управление.Статична и централизирана маршрутизация, маршрутизация с алгоритъма на дистантния вектор и следене състоянието на връзката. Задръствания и управление на потоците в мрежата.

  10. Мрежови протоколи. Междумрежов протокол IP. Транспортни протоколи TCP и UDP. DNS-протокол и резолвинг. Файлов трансфер в Интернет. Протоколи за електронна поща SMTP и POP3. Хипертекстов протокол.

  11. Растеризиране на отсечка, окръжност и елипса.



ПРОГРАМИРАНЕ





  1. Процедурно програмиране - основни информационни и алгоритмични структури (C++).

  2. Обектно ориентирано програмиране (C++): Основни принципи. Класове и обекти. Оператори. Шаблони на функции и класове.

  3. Обектно ориентирано програмиране (C++): Наследяване и полиморфизъм.

  4. Структури от данни. Стек, опашка, списък, дърво. Основни операции върху тях. Реализация.

  5. Основни конструкции в езиците за функционално програмиране. Дефиниране и използване на функции. Списъци. Функции от по-висок ред за работа със списъци. Потоци.

  6. Семантична характеризация на логическите формули и програми.

  7. Операционна семантика на логическите програми.

  8. Пространство на състоянията - основни понятия и задачи. Стратегии и алгоритми за неинформирано и информирано търсене на път до определена цел. Представяне и използване на знания - основни понятия и формализми.


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


  1. Симетрични оператори в крайномерни евклидови пространства. Основни свойства. Теорема за диагонализация.

  2. Алгебрическа затвореност на полето на комплексните числа. Следствия.

  3. Теореми за средните стойности (Рол, Лагранж и Коши). Формула на Тейлър.

  4. Определен интеграл. Дефиниция и свойства. Интегруемост на непрекъснатите функции. Теорема на Нютон - Лайбниц.

  5. Диференцируеми функции на много променливи. Диференциране на съставни функции.

  6. Уравнения на права и равнина. Формули за разстояния и ъгли.

  7. Линейни обикновени диференциални уравнения. Уравнения с постоянни коефициенти.

  8. Диференчни методи за задачата на Коши за обикновено диференциално уравнение от първи ред.

  9. Итерационни методи за решаване на нелинейни уравнения.

  10. Дискретни разпределения:

а) Равномерно разпределение.

б) Биномно разпределение.

в) Геометрично разпределение.

г) Поасоново разпределение.

д) Хипергеометрично разпределение.

Задачи, в които възникват. Моменти - математическо очакване и дисперсия.



ЛИТЕРАТУРА


  1. Азълов, П., Бази от данни. Релационен и обектен подход. Техника, София, 1991.

  2. Андреев,А. и др. Сборник от задачи по числени методи. Университетско издателство “Св. Кл. Охридски”, София, 1994.

  3. Боянов, Б., Лекции по числени методи. Дарба, София, 1998.

  4. Боянов К., Хр. Турлаков, Дим. Тодоров, Л. Боянов, Вл. Димитров, Вед. Желязков – Принципи на работа на компютърните мрежи. ИНТЕРНЕТ. изд. Апиинфоцентър Котларски, 2003.

  5. Въндев, Д., Записки по теория на вероятностите. Електронно издание:
    http://www.fmi.uni-sofia.bg/fmi/statist/lectures/prob/prob.html

  6. Генчев, Т., Обикновени диференциални уравнения, III изд. Университетско издателство “Св. Кл. Охридски”, София, 1999.

  7. Горслайн, Дж., Фамилия Intel 8086/8088. Техника, София, 1990.

  8. Денев, Й., Р. Павлов, Я. Деметрович, Дискретна математика. Наука и изкуство, София, 1984.

  9. Денев, Й., С. Щраков, Дискретна математика. ЮЗУ “Неофит Рилски”, Благоевград, 1995.

  10. Димитров, Б., К. Янев, Вероятности и статистика, Университетско издателство “Св. Кл. Охридски”, София, 1998.

  11. Димова Ст., Т. Черногорова, А. Йотова. Лекции по числени методи за диференциални уравнения. www.fmi.uni-sofia.bg/econtent/chmdu

  12. Дойчинов, Д., Математически анализ. Университетско издателство “Св. Кл. Охридски”, София, 1994.

  13. Дойчинов, Д., Математически анализ в крайномерни пространства. Наука и изкуство, София, 1979.

  14. Компютърна енциклопедия, ч. I, II. Nisoft, София, 1993.

  15. Комър Бр., TCP/IP мрежи и администриране, изд. ИнфоДар, 1999.

  16. Лукипудис Е., Компютърна графика и геометрично моделиране, част І - в равнината, 1996.

  17. Манев, К., Увод в дискретната математика. Издателство на НБУ, София, 1996 (I изд.), 1998 (II изд.).

  18. Манна, З., Математическа теория на информатиката. Наука и изкуство, София, 1983.

  19. Метакидес, Д., А. Нероуд, Принципи на логиката и логическото програмиране. Виртех, София, 2000.

  20. Николов, Л., Операционни системи. Ciela, София, 1998.

  21. Нишева, М., Д. Шишков, Изкуствен интелект. Интеграл, Добрич, 1995.

  22. Сендов, Бл., В. Попов, Числени методи, I ч. Университетско издателство “Св. Кл. Охридски”, София, 1996.

  23. Сендов Бл., В. Попов, Числени методи. Втора част, Наука и изкуство, София, 1978.

  24. Сидеров, Пл., Записки по алгебра: линейна алгебра. Веди, София, 1994.

  25. Сидеров, Пл., Записки по алгебра: групи, пръстени, полиноми. Веди, София, 1995.

  26. Скордев, Д., Логическо програмиране (записки). Електронно издание:
    http://www.fmi.uni-sofia.bg/fmi/logic/skordev/ln/lp/lp.htm

  27. Сосков, И., А. Дичев, Теория на програмите. Университетско издателство “Св. Кл. Охридски”, София, 1996.

  28. Станилов, Гр., Аналитична геометрия. Софтех, София, 1998.

  29. Тодорова, М., Програмиране на C++. I и II част. Ciela, София, 2002.

  30. Тодорова, М., Езици за функционално и логическо програмиране. I част: Функционално програмиране. Ciela, София, 2003.

  31. Уирт, Н., Алгоритми + структури от данни = програми. BG soft group, София.

  32. Logic Programming. Електронно издание: http://www.afm.sbu.ac.uk/logic-prog

  33. Rogers D. F., Procedural Elements for Computer Graphics, McGrow Hill, 1998.

  34. Stallings, W., Computer Organization and Architecture. Design for Performance. Prentice Hall, 2000.

  35. Tanenbaum, A., Structured Computer Organization. Prentice Hall, 2002.

  36. Tanenbaum, A., Modern Operating systems (2nd ed.). Prentice Hall, 2002.

  37. Tannenbaum A., Computer Networks- 3th ed., 4th ed., Prentice Hall.

  38. http://www.williamstallings.com/COA5e.html

  39. Stroustrup, B., C++ Programming Lanquage. Third Edition, Addison-Wesley, 1997.

  40. http://www.fmi.uni-sofia.bg/fmi/diff_equ/exams.html


АНОТАЦИИ НА ВЪПРОСИТЕ
1. Булеви функции. Теорема на Пост - Яблонски за пълнота.

Дефиниция на булева функция и формула над множество булеви функции. Дефиниция на пълно и затворено множество, включително на минимално по включване пълно множество - базис. Формулировка на критерий за затвореност на множество булеви функции. Дефиниции на всяко едно от затворените множества T0, T1, S, M и L. Формулировка и доказателство на теоремата на Пост - Яблонски за пълнота на множество булеви функции. Дефиниция на шеферова функция. Формулировка и доказателство на критерий за шеферовост на булева функция.


Примерни задачи


  1. По зададена булева функция (включително и функция, съдържаща параметри) да се определи принадлежността й към някое от множествата T0, T1, S, M и L (и при какви стойности на параметрите, ако има такива).

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

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

  4. Да се определят всички базиси, които се съдържат в зададено пълно множество от булеви функции.

Литература: [17], [8], [9].
2. Крайни автомати. Регулярни изрази. Теорема на Клини.

Дефиниции на краен детерминиран автомат (КДА) и език, разпознаван от КДА. Дефиниции на краен недетерминиран автомат (КНА) и език, разпознаван от КНА. Алгоритъм за детерминизация на КНА. Дефиниция на минимален КДА, разпознаващ автоматен език. Алгоритъм за минимизация на КДА. Дефиниции на регулярни изрази и езици. Формулировка и доказателство на теоремата на Клини и съпътстващите я леми.


Примерни задачи


  1. По зададен КНА да се намери еквивалетен КДА.

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

  3. По зададен КДА да се построи съответният му регулярен израз.

  4. По зададен регулярен израз да се построи съответният му (минимален или не) КДА.

Литература: [17], [8], [9].
3. Графи. Дървета. Обхождане на графи. Минимално покриващо дърво.

Дефиниция на краен ориентиран и краен неориентиран граф и мулти граф. Дефиниции на маршрут/контур в КОГ и път/цикъл в КНГ. Дефиниция на свързан граф. Дефиниция на дърво и кореново дърво. Свойства на дървета и коренови дървета – доказателствo на теоремата . Дефиниция на покриващо дърво и доказателство на теоремата: граф е свързан тогава и само тогава, когато има покриващо дърво. Обхождане на граф в ширина и дълбочина – схема и алгоритъм за построяване на покриващо дърво в ширина и дълбочина. Ойлерови обхождания. Теорема на Ойлер (без доказателство). Минимално покриващо дърво. Свойство на минимално покриващо дърво (с доказателство). Алгоритми на Прим и Крускал. Представяне на графи и дървета.


4. Семантика на рекурсивните програми с предаване на параметрите по стойност.

  1. Операционна семантика. Правила за опростяване.

  2. Най-малки неподвижни точки на компактни оператори. Теорема на Кнастер и Тарски за системи от уравнения. Компактност на операторите, определени от програмни термове. Денотационна семантика на рекурсивните програми.

  3. Еквивалентност на денотационната и операционната семантики.

  4. Правило за мю-индукцията на Скот.

Литература: [27].
5. Релационна алгебра. Релационно смятане. Нормални форми.

  1. Релационен модел на данни: домен; релация; кортеж; атрибути; схема на релация; схема на релационна база от данни; реализация на релационната база от данни; операции върху релационната база от данни; заявки към релационната база от данни.

  2. Релационна алгебра:

a) основни операции: обединение; разлика; декартово произведение; проекция; селекция.

б) допълнителни операции: сечение; частно; съединение; естествено съединение.



  1. Релационно смятане:

a) релационно смятане с променливи върху кортежи: атоми; формули; свободни и свързани променливи; релационно смятане върху крайни релации; безопосни изрази; редукция на релационната алгебра към релационно смятане с променливи върху кортежи.

б) релационно смятане с променливи върху домени: атоми; формули; свободни и свързани променливи; релационно смятане върху крайни релации; безопосни изрази; редукция на релационното смятане с променливи върху кортежи към релационно смятане с променливи върху домени; редукция на релационно смятане с променливи върху домени към релационната алгебра.



  1. Нормални форми:

a) недостатъци на схемата на базата от данни: излишество; аномалия при обновяване; аномалия при добавяне; аномалия при изтриване; съединения без загуба на функционалните зависимости.

б) функционални зависимости: ограничения, определяни от семантиката на елементите от домена, и ограничения, определяни от равенство или неравенство на стойности; ключове; първичен ключ; възможен ключ; аксиоми на Армстронг.

в) първа нормална форма; втора нормална форма; трета нормална форма; нормална форма на Бойс - Код.

г) многозначни зависимости; аксиоми на функционалните и многозначните зависимости; съединение без загуба; четвърта нормална форма; вградени многозначни зависимости.



д) привеждане схемата на базата от данни към нормалните форми.

Примерни задачи


  1. Формулиране на заявка на езика на релационната алгебра или релационното смятане.

  2. Привеждане схема на базата от данни (при зададени функционални зависимости) към нормална форма.


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

  1. Принципи на фон Нойман: обща структура на компютрите и концептуално изпълнение на инструкциите, запомнена програма.

  2. Формати на данните

    • цели двоични числа;

    • двоично-десетични числа;

    • двоични числа с плаваща запетая;

    • символни данни и кодови таблици.

  3. Вътрешна структура на централен процесор

    • регистри;

    • аритметико-логическо устройство;

    • регистър на състоянието и флагове;

    • блок за управление: хардуерно и микропрограмно управление;

    • блок за връзка с паметта;

    • блок за предварителна дешифрация на инструкциите;

    • блок за трасиране на преходите;

    • вътрешни магистрали;

    • RISC принципи;

    • CISC процесори.

  4. Инструкции на централен процесор

    • префикси;

    • код на операцията;

    • местоположение на операндите;

    • модели на адресация на операндите;

    • аритметико-логически инструции;

    • низови инструкции;

    • безусловни и условни преходи;

    • управление на програмата.

  5. Кеш-памети

    • структура кеш-памет: блокове, множества и рамки;

    • структура на адреса: таг, индекс и отместване;

    • организация: асоциативни и директни;

    • оптимизация основните параметри на кеша;

    • начини за повишаване производителността на кеша.

  6. Оперативна памет – особености на динамичната памет

    • вътрешна структура на RAM блок;

    • банки и припокриване;

    • ускоряване на паметта.

  7. Сегментна преадресация

    • сегментен селектор;

    • сегментен дескриптор;

    • сегментни таблици и регистри.

  8. Странична преадресация

    • каталог на страниците;

    • описател на страница;

    • стратегии на подмяна на страниците.

Литература: [7], [35], [34], [38].
7. Компютърни системи – основни принципи за осъществяване на входно-изходния обмен. Входно-изходни процесори и канали, общи шини и магистрали. Прекъсвания – приоритети и обслужване. Видеомонитор, видеоконтролер и клавиатура. Дискови интерфейси и устройства. Принтери.

  1. Основни принципи на осъществяване на входно-изходния обмен – управление от процесора, DMA-контролери, общи шини, канали.

  2. Прекъсвания

    1. конкурентност и приоритети;

    2. типове прекъсвания;

    3. обслужване на прекъсванията;

    4. контролери на прекъсванията.

  1. Обща шина PCI – състав и опериране.

  2. Магистрала USB – структури и функциониране.

  3. Видеоконтролер – структура и функциониране.

  4. Видеомонитор – CRT и LCD основни принципи.

  5. Принцип на действие на клавиатурата.

  6. Дискови интерфейси – IDE и SCSI.

  7. Твърди магнитни дискове. Принципи . RAID-масиви.

  8. Оптични дискове – принципи на постоянния и еднократния запис.

  9. Принтери – принципи на матричните и лазерни принтери.

Литература: [34], [35], [36].
8. Файлова система. Логическа организация и физическо представяне. Основни системни примитиви.

  1. Логическа организация на файлова система:

    • Имена на файлове.

    • Типове файлове - обикновен файл, специален файл, каталог, символна връзка, програмен канал и др.

    • Вътрешна структура на файл.

    • Атрибути на файл.

    • Йерархична организация на файлова система - абсолютно и относително пълно име на файл, текущ каталог.

  2. Физическо представяне на файлова система:

  • Стратегии за управление на дисковото пространство.

  • Системни структури, съдържащи информация за разпределението на дисковата памет и съхранявани постоянно на диска:

- за свободните блокове;

- за блоковете, разпределени за всеки един файл;

- за общи параметри на файловата система.


  • Примери за физическа организация на файлова система:

- UNIX System V;

- LINUX;


- MS DOS;

- NTFS.


  1. Основни системни примитиви на файлова система:

  • Работа с обикновен файл - създаване, отваряне, четене, писане, позициониране и др.

  • Изграждане йерархичната организация на файловата система - създаване и унищожаване на каталог, създаване и унищожаване на връзки, смяна на текущ каталог.

  • Защита на файловата система.

Литература: [20], [36].

Забележка: На изпита ще бъде избрана част от изброените примери за файлова организация.
9. Компютърни мрежи. Еталонен модел и видове мрежи. Канално ниво и HDLC. Канал ЕТЕРНЕТ – метод на достъп и управление.Статична и централизирана маршрутизация, маршрутизация с алгоритъма на дистантния вектор и следене състоянието на връзката. Задръствания и управление на потоците в мрежата.

    1. Седемслоен модел OSI на ISO – характеристики на нивата.

    2. Видове мрежи – маршрутизация и селекция; комутация на канали, съобщения и пакети; LAN, MAN, WAN, Internet.

    3. Канално ниво – кадри, предаване, грешки, номерация, прозорци.

    4. HDLC – формати и видове кадри.

    5. Метод на достъп до съобщителната среда в ЕТЕРНЕТ.

    6. Формат на кадрите в ЕТЕРНЕТ. Превключватели и мостове.

    7. Статична маршрутизация – таблица и избори.

    8. Централизирана маршрутизация – недостатъци.

    9. Разпределена маршрутизация по алгоритъма с дистантен вектор.

    10. Разпределена маршрутизация по алгоритъма със следене състоянието на връзката.

    11. Задръствания в мрежите и методи за борба с тях.

    12. Управление на потоците в мрежите.


10. Мрежови протоколи. Междумрежов протокол IP. Транспортни протоколи TCP и UDP. DNS-протокол и резолвинг. Файлов трансфер в Интернет. Протоколи за електронна поща SMTP и POP3. Хипертекстов протокол.

  1. IP протокол – формат на дейтаграмата.

  2. Структура на IP-адреса, класове, мрежи и маски.

  3. Преобразуване на IP-адреси в MAC-адреси.

  4. Транспортен протокол TCP – формат и установяване на съединение.

  5. Транспортен протокол UDP – формат.

  6. DNS система за именоване. Йерархия на домейните.

  7. Резолвинг – рекурсивни и итеративни заявки.

  8. DNS сървери.

  9. Файлов трансфер в Интернет- клиент и сървер на FTP.

  10. Електронна поща чрез протоколите SMTP и POP3.

  11. Хипертекстов протокол HTTP – особености.

Литература:[37], [15], [4].
11. Растеризиране на отсечка, окръжност и елипса.

Необходимост и цел за растеризация на графични примитиви. Да се разгледат най-често използваните алгоритми като на алгоритмите на средната точка, на порциите, на Брезенхам и Михнер и да се даде и код на С за тях. Да се обърне внимание на избора на начално приближение. Да се разгледат и алгоритми използващи частни разлики от втори ред за окръжност както и алгоритми растеризиращи дъга от окръжност.



Литература:[16], [33].
12. Процедурно програмиране - основни информационни и алгоритмични структури (C++).

Изложението по въпроса трябва да включва следните по-съществени елементи:



  1. Принципи на структурното програмиране.

  2. Величини от указателен тип – основни приложения.

  3. Указателна аритметика. Указателен достъп до масиви и матрици.

  4. Типизирани и нетипизирани функции.

  5. Видове параметри и взаимодействие на функциите чрез тях.

  6. Глобални променливи и взаимодействие на функците чрез тях.

  7. Линейна, разклонена и косвена рекурсия.

Да се акцентира върху семантичните свойства на съответните езикови средства.

Типична задача. Да се състави функция, която въз основа на зададени като параметри масиви и/или матрици, чрез съответен анализ формира други такива.

Литература: [29].
13. Обектно ориентирано програмиране (C++): Основни принципи. Класове и обекти. Оператори. Шаблони на функции и класове.

Абстракция със структури от данни, от структури към класове (основни идеи). Класове. Дефиниране и област на клас. Обекти. Конструктори. Подразбиращ се конструктор. Конструктор за присвояване. Указатели към обекти. Масиви и обекти. Динамични обекти. Деструктор. Създаване и разрушаване на обекти на класове. Масиви


от обекти. Оператори. Предефиниране на оператори. Операторна функция за присвояване. Шаблони на функции и класове.

Литература: [29], [39].
14. Обектно ориентирано програмиране (C++): Наследяване и полиморфизъм.

Производни класове. Дефиниране. Наследяване и достъп до наследените компоненти. Предефиниране на компоненти. Конструктори, операторни функции за присвояване и деструктори на производни класове.

Множествено наследяване. Виртуални класове. Динамично свързване и виртуални функции. Полиморфизъм. Абстрактни класове.

Литература: [29], [39].
15. Структури от данни. Стек, опашка, списък, дърво. Основни операции върху тях. Реализация.

Структури от данни - дефиниране. Структура от данни стек. Логическо описание. Физическо представяне. Дефиниране на клас, реализиращ свързаното представяне на стек.

Структура от данни опашка. Логическо описание. Физическо представяне. Клас, реализиращ свързаното представяне на опашка.

Структура от данни свързан списък. Логическо описание. Физическо представяне. Клас, реализиращ представяне на свързан списък с една връзка. Клас, реализиращ представяне на свързан списък с две връзки.

Структура от данни двоично дърво, логическо описание. Физическо представяне. Клас, реализиращ свързаното представяне на двоично дърво.

Структура от данни двоично наредено дърво. Логическо описание. Физическо представяне. Клас, реализиращ двоично наредено дърво.



Забележка. За изпита ще бъдат избрани две от изброените структури.

Литература: [29], [31], [39].
16. Основни конструкции в езиците за функционално програмиране. Дефиниране и използване на функции. Списъци. Функции от по-висок ред за работа със списъци. Потоци.

Изложението по въпроса трябва да включва следните по-съществени елементи:



  1. Основни компоненти на функционалните програми. Примитивни изрази. Средства за комбиниране и абстракция. Оценяване на изрази.

  2. Дефиниране на променливи и процедури. Среди. Специални форми. Модели на оценяване на комбинации.

  3. Процедури от по-висок ред. Процедурите като параметри и оценки на обръщения към процедури.

  4. Списъци. Основни операции със списъци. Процедури от по-висок ред за работа със списъци: акумулиране, трансформиране и филтриране на елементите на даден списък.

  5. Потоци. Основни операции с потоци. Функции от по-висок ред за работа с потоци. Отложено оценяване. Работа с безкрайни потоци.

Литература: [30].

Забележка. На изпита ще бъдат давани или т. 1-3, или т. 4-5.
17. Семантична характеризация на логическите формули и програми.

Синтаксис и семантика на логическите формули. Изпълнимост и тъждествена вярност. Ербранови структури. Ербранови модели на множества от безкванторни или множества от универсални затворени формули.



Литература: [27], [26], [19], [21], [32].
18. Операционна семантика на логическите програми.

Субституции. Унификатори и унифицируемост. Алгоритъм за намиране на най-общ унификатор на атомарни формули.



Литература: [18], [26], [19], [21], [32].
19. Пространство на състоянията - основни понятия и задачи. Стратегии и алгоритми за неинформирано и информирано търсене на път до определена цел. Представяне и използване на знания - основни понятия и формализми.

Изложението по въпроса трябва да включва следните по-съществени елементи:



  1. Пространство на състоянията. Основни понятия. Формулировка на основните типове задачи за търсене в пространството на състоянията: търсене на път до определена цел, формиране на стратегия при игри за двама играчи, намиране на цел при спазване на ограничителни условия.

  2. Основни стратегии при неинформирано ("сляпо"') търсене на път до определена цел: търсене в дълбочина (depth-first search), търсене в широчина (breadth-first search). Реализация.

  3. Методи за информирано (евристично) търсене на път до определена цел: best-first search, beam search, hill climbing, A*. Реализация.

  4. Представяне и използване на знания (ПИЗ) в системите с изкуствен интелект. Видове знания. Типове формализми за ПИЗ. ПИЗ чрез процедури, средствата на математическата логика, системи от продукционни правила, семантични мрежи и фреймове.

Литература: [21].

Забележка. На изпита ще бъдат давани или т. 1-3, или т. 4.
20. Симетрични оператори в крайномерни евклидови пространства. Основни свойства. Теорема за диагонализация.

Всички характеристични корени на симетричен оператор са реални числа; всеки два собствени вектора, съответстващи на различни собствени стойности, са ортогонални помежду си; съществува ортонормиран базис на пространството, в който матрицата на симетричен оператор е диагонална.



Задача. За даден симетричен оператор да се намерят ортонормиран базис на пространството, в който матрицата му е диагонална, както и самата матрица.

Литература: [24].
21. Алгебрическа затвореност на полето на комплексните числа. Следствиия.

Полето на комплексните числа е алгебрически затворено; всеки полином с комплексни коефициенти се разлага в произведение на линейни множители; всеки полином с реални коефициенти се разлага в произведение на линейни и квадратни множители; формули на Виет.



Задача. Прилагане на формулите на Виет за полином с числови коефициенти.

Литература: [25].
22. Теореми за средните стойности (Рол, Лагранж и Коши). Формула на Тейлър. Необходимо е да се докажат следните теореми, формулирани общо за по-кратко.

Нека е непрекъсната в затворения интервал [a, b] и притежава производна поне в отворения интервал (a, b). Да се докаже, че:

а) ако (a) = (b), то съществува c  (a, b), така че '(c) = 0 (Рол);

б) съществува c  (a, b), така че (Лагранж);

в) ако g е непрекъсната в затворения интервал [a, b] и притежава производна поне в отворения интервал (a, b), g’(x)  0, x  (a, b), то съществува c  (a, b), така че

(Коши).

За доказателството на теоремата на Рол (а)) да се използва (без доказателство!) теоремата на Вайерщрас, според която всяка непрекъсната функция в краен и затворен интервал достига своя максимум и минимум.

Необходимо е още да се изведе формулата на Тейлър с остатъчен член във формата на Лагранж и Коши.

Примерни задачи. Нека , където е произволно фиксирано реално число:

а) да се пресметне ;

б) като се използва теоремата на Рол, да се докаже, че уравнението има поне един корен в интервала (0,1).
23. Определен интеграл. Дефиниция и свойства. Интегруемост на непрекъснатите функции. Теорема на Нютон - Лайбниц.

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

Да се докаже, че дадена функция е интегруема по Риман тогава и само тогава, когато за всяко  > 0 съществуват голяма сума на Дарбу S и малка сума на Дарбу s такива, че S s < . Като се използва тази теорема и теоремата на Кантор, според която всяка непрекъсната функция в краен и затворен интервал е равномерно непрекъсната, да се докаже, че всяка непрекъсната функция в краен и затворен интервал е интегруема по Риман. Да се изброят (без доказателство) основните свойства на Римановия интеграл. Като се приложи свойството за интегриране на неравенства и теоремата, че всяка непрекъсната функция приема всички стойности между максимума и минимума си, да се докаже, че ако е непрекъсната в [a, b], то съществува c  [a, b], така че

.

Като се използва този факт, да се докаже теоремата на Нютон - Лайбниц, т.е. че ако е непрекъсната в [a, b], то за всяко x [a, b]



,

и да се покаже как тя се използва за изчисляване на определен интеграл.



Примерни задачи. Смяна на променливите и интегриране по части; интегриране на рационални функции; интеграли от вида

;

субституции за интегриране на рационални функции от sin x и cos x; субституции на Ойлер.


24. Диференцируеми функции на много променливи. Диференциране на съставни функции.

Дефиниция на частни производни на функция на няколко променливи; дефиниция на диференцируема функция. Известно е, че се нарича диференцируема в точката, ако е в сила представянето

(*)

където a и b са реални числа, а , т.е.



.

Да се покаже, че ако е диференцируема в , то , .

Горната дефиниция може да се пропусне, като се приеме опростена дефиниция - функцията да притежава непрекъснати частни производни в околност на точката.

Да се докаже следната



Теорема. Нека е дефинирана и притежава частни производни по и в околност на точката , като тези частни производни са непрекъснати в точката . Тогава притежава представянето (*).

За доказателството на теоремата да се използва (без доказателство) теоремата на Лагранж за средните стойности.

Формулировка и доказателство при какви предположения е в сила равенството

където


25. Уравнения на права и равнина. Формули за разстояния и ъгли.

Векторни и параметрични (скаларни) уравнения на права и равнина. Общо уравнение на права в равнината. Декартово уравнение. Взаимно положение на две прави. Нормално уравнение на права. Разстояние от точка до права. Ъгъл между прави.

Общо уравнение на равнина. Взаимно положение на две равнини. Нормално уравнение на равнина. Разстояние от точка до равнина.
26. Линейни обикновени диференциални уравнения. Уравнения с постоянни коефициенти.

Разглежда се диференциалното уравнение от n-ти ред



където aj(t) са непрекъснати функции. Формулира се (без доказателство) теорема за съществуване и единственост на решението на задачата на Коши. Дава се критерий за линейна независимост на система от n решения на хомогенното уравнение чрез детерминантата на Вронски. Дефинира се понятието фундаментална система от решения и се доказва, че решенията на хомогенното уравнение (т.е. ) образуват n - мерно линейно пространство. Описва се структурата на решенията на нехомогенното уравнение.

Формулира се алгоритъм за намиране на общото решение на уравнението с постоянни коефициенти


Примерни задачи


  1. Линейни ДУ с променливи коефициенти:

  1. Да се намери общото решение на уравнението, като се намери негово частно решение във вида или

а) >1;

б) >0.



  1. Линейни ДУ с постоянни коефициенти. Уравнения на Ойлер:

    1. Да се намерят реалните решения на уравнението:

а)

б) y” + 4y = 2 tg x,

в) + + > 0.


    1. Да се реши задачата на Коши:

а)

б) + +



    1. Да се реши уравнението на Ойлер:

а) =

б) + + >0.



    1. Да се покаже, че уравнението + има единствено решение, ограничено в . Да се намери това решение.

Литература: [6], [40].
27. Диференчни методи за задачата на Коши за обикновено диференциално уравнение от първи ред.

  1. Постановка на задачата на Коши за ОДУ от I ред. Геометрична интерпретация.

  2. Същност на диференчните методи. Основни понятия.

  3. Методи на Ойлер – явен, неявен, подобрен. Извеждане, апроксимация, устойчивост, монотонност.

  4. Явни методи на Рунге-Кута за ОДУ от I ред – едно- и двуетапни. Метод на Рунге за практическа оценка на грешката.

Литература: [11], [23].
28. Итерационни методи за решаване на нелинейни уравнения.

Да се дефинира понятието неподвижна точка на изображението и да се докаже, че ако е непрекъснато изображение на интервала [a, b] в себе си, то има поне една неподвижна точка в [a, b]. Да се покаже, че решаването на уравнението може да се сведе към намиране на неподвижна точка.

Да се дефинира понятието свиващо изображение и да се докаже, че ако  е непрекъснато изображение на интервала [a, b] в себе си и е свиващо с константа на Липшиц q < 1, то: а) уравнението x = (x) има единствен корен  в [a, b]; б) редицата от последователни приближения (при произволно [a, b] и , клони към  при n  , като за всяко n. Да се получи като следствие, че ако  е корен на уравнението и има непрекъсната производна в околност на , за която , то при достатъчно добро начално приближение итерационният процес, породен от , е сходящ със скоростта на геометрична прогресия. Да се дефинира понятието ред на сходимост.

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



Литература: [2], [3], [22].
29. Дискретни разпределения:

  1. Равномерно разпределение.

  2. Биномно разпределение.

  3. Геометрично разпределение.

  4. Поасоново разпределение.

  5. Хипергеометрично разпределение.

Задачи, в които възникват. Моменти - математическо очакване и дисперсия.

Дефиниция на (дискретно и) целочислено разпределение на случайна величина. Свойства на вероятностите (неотрицателност и нормираност).



За всяко от разпределенията се посочва пример (задача), при който то възниква, например:

  1. Равномерно разпределение - хвърляне на правилен зар;

  2. Биномно и геометрично разпределение - хвърляне на монета;

  3. Поасоново разпределение - брой отчетени радиоактивни частици за единица време;

  4. Хипергеометрично разпределение - статистически качествен контрол.

Пресмятат се математическото очакване и дисперсията на всяко от тези разпределения. При пресмятанията може да се използва пораждаща моментите функция, но тя трябва да се определи за всяко целочислено разпределение и да се изведат основните й свойства.

Литература: [10], глави 2.3 (стр. 54-56), 3.2 (стр. 71-74), 6.1 (примери 1-4); [5], тема: Дискретни разпределения.


Каталог: drafts
drafts -> П р а в и л а за организиране и провеждане на ученическите игри през учебната 2013/2014 година софия, 2013 г
drafts -> Република българия министерство на младежта и спорта
drafts -> Република българия министерство на младежта и спорта до министерския съвет
drafts -> Закон за физическото възпитание и спорта, е предвидено в приоритет 21. 1 от Програмата на правителството за стабилно развитие на Република България за периода 2014-2018 г
drafts -> Защо възкресението на исус е важно?
drafts -> Р е п у б л и к а б ъ л г а р и я народно събрание проект з а к о н за доброволчеството Глава първа общи положения предмет Чл. (1) Този закон


Сподели с приятели:




©obuch.info 2022
отнасят до администрацията

    Начална страница