Форум Поща Карта на сайта Търсене Връзки Контакти
Начало Обучение Избираеми дисциплини Oбщ списък на избираемите дисциплини и практикуми Програмиране на машини на Пост и Тюринг и разрешимост на алгоритмични проблеми    English
Факултет по математика и информатика - Програмиране на машини на Пост и Тюринг и разрешимост на алгоритмични проблеми

 Лектор  проф. д-р Ст. Костадинов, гл.ас. Хр. Кискинов
Анотация 
   Целта на курса е запознаването на студентите с машините на Пост и Тюринг. Програмирането на тях се изучава с помощта на конструиране на много и най-различни малки програми. С изучаване на възможностите на тези машини и паралела между тях и съвременните компютри студентите се запознават с (или обогатяват познанията за) основни понятия в информатиката: алгоритъм, диаграми и блок-схеми, анализ и синтез на програми, изчислими функции. Формулират се хипотезите (тезиси) на Чърч и Пост за изчислимост и се разглеждат разрешими и неразрешими алгоритмични проблеми.  
Съдържание  

1. Формални езици. Пораждащи граматики. Крайни автомати.

2. Безконтекстни езици. Синтаксис на езиците за програмиране. Автомати със стек.

3. Машина на Тюринг. Универсална машина на Тюринг.

4. Машина на Пост. Програмиране на машината на Пост.

5. Диаграми и блок-схеми. Анализ и синтез на програмите.

6. Възможности на машините на Тюринг и Пост. Алгоритми. Изчислимост. Хипотези на Чърч и Пост.

7. Паралели между машините на Пост, Тюринг и днешните компютри.

8. Разрешими и неразрешими алгоритмични проблеми.

Актуално
Още новини
Архив на новините
© 2009 ФМИ