2015-01-30
347
1. Задачей полиноминальной сложности является задача:
A) о гамильтоновом цикле;
B) о паросочетании в графе;
C) об упаковке корректирующих кодов;
D) целочисленного программирования;
E) о доминирующем множестве.
2. Задачей полиноминальной сложности является задача:
A) система диофантовых неравенств;
B) о клике;
C) о раскраске вершин графа;
D) коммивояжера;
E) линейного программирования.
3. Задачей полиноминальной сложности является задача:
A) о двух последовательных станках;
B) о клике;
C) целочисленного программирования;
D) о независимом множестве в графе;
E) коммивояжера.
4. Задачей полиноминальной сложности является задача:
A) об упаковке корректирующих кодов;
B) об эйлеровом цикле;
C) система диофантовых неравенств;
D) о доминирующем множестве;
E) о гамильтоновом цикле.
5. Задачей полиноминальной сложности является задача:
A) коммивояжерa;
B) целочисленного программирования;
C) о независимом множестве;
D) система линейных уравнений;
E) о раскраске вершин графа.
6. NP - полной является задача:
|
|
|
A) о двух последовательных станках;
B) система линейных уравнений;
C) об упаковке корректирующих кодов;
D) линейного программирования;
E) о паросочетании в графе.
7. NP - полной является задача:
A) линейного программирования;
B) об эйлеровом цикле;
C) система линейных уравнений;
D) о паросочетании в графе;
E) о гамильтоновом цикле.
8. NP - полной является задача:
A) система линейных уравнений;
B) о клике;
C) линейного программирования;
D) об эйлеровом цикле;
E) о двух последовательных станках.
9. NP - полной является задача:
A) об эйлеровом цикле;
B) о двух последовательных станках;
C) линейного программирования;
D) о доминирующем множестве;
E) о паросочетании в графе.
10. NP - полной является задача:
A) система диофантовых неравенств;
B) линейного программирования;
C) о паросочетании в графе;
D) о двух последовательных станках;
E) система линейных уравнений.
Литература
1. Игошин В.И. Математическая логика и теория алгоритмов. Саратов, Издательство Саратовского университета, 1991.
2. Игошин В.И. Задачник-практикум по математической логике. М., Просвещение, 1986.
3. Лихтарников Л.М., Сукачева Т.Г. Математическая логика: курс лекций, задачник-практикум. Санкт-Петербург, Лань, 1998.
4. Новиков П.С. Элементы математической логики. М., Наука, 1973.
5. Эдельман С.Л. Математическая логика. М., Высшая школа, 1975.
6. Лавров И.А., Максимов Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М., Наука, 1975.
7. Мендельсон Э. Введение в математическую логику. М., Наука, 1976.
8. Клини С. Математическая логика. М., Мир, 1973.
9. Черч А. Введение в математическую логику. М, Мир, 1960.
|
|
|
10. Мальцев А. И. Алгоритмы и рекурсивные функции. М, Наука, 1965.
11. Вьялицин А.А., Белошистова Я.С., Коняева С.М. Дискретная математика. Петропавловск, СКГУ, 2004.
12. Акимов О.Е. Дискретная математика: логика, группы, графы. М., Лаборатория Базовых Знаний, 2001.
13. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. М., ИНФРА-М, Новосибирск, Издательство НГТУ, 2002.
14. Яблонский С. В. Введение в дискретную математику. М., Наука, 1979.
15. Сафьянова Е. Н. Дискретная математика. Томск, Томский межвузовский центр дистанционного образования, 2000.
16. Новиков Ф. А. Дискретная математика для программистов. Санкт-Петербург, 2002.
17. Горбатов В. А. Основы дискретной математики. М, Высшая математика, 1986.
18. Мутанов Г. М., Акбердин Р. А. Теория графов. Алматы, Рауан, 1999.
19. Васильев Ю. Л. Дискретная математика и математические вопросы кибернетики. М., Наука, 1974.
20. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. М., Наука, 1977.
21. Абдугалиев У. А. Дискретная математика. Алма-Ата, КазГУ, 1980, 1 часть, 1981, 2 часть.
22. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. М., Энергия, 1980.
23. Артипов М. Н., Садовский Л. Е. Коды и математика. М., Наука, 1983.
24. Танаев В. С. Шкурба В. В. Введение в теорию расписаний.
25. Шкурба В. В. Задача трёх станков. М., Наука, 1976.
26. Акбердин Р. А., Курмашев И. Г., Коняева С. М. CD-диск по Дискретной математике и математической логике.
