Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй» icon

Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй»




НазваПитання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй»
Дата19.08.2012
Розмір20 Kb.
ТипЗадача

Питання до тестування за курсом «Теорія алгоритмів і матлогика»


1. У чому складається основна ідея алгоритмічного методу «розділяй і пануй» ?

  • Задача розбивається на пріоритети по важливості рішення.

  • Задача виконується від верху до низу а потім перевіряється виконання знизу доверху.

  • Задача розбивається на підзадачі. Потім ці підзадачі вирішуються за допомогою рекурсивного виклику або безпосередньо. Рішення комбінуються і виходить рішення вихідної задачі.

  • Задача виконується поетапно з вибором оптимального рішення на кожнім етапі.


2. За умови, що повне бінарне дерево має 128 листів, визначите :

1) висоту цього дерева; 2) кількість вершин.

  • 9; – 127.

  • 8; – 127.

  • 7; – 127.

  • 9; – 95.

  • 8; – 95.


3. Дано фрагмент програми рекурсивної функції. Який буде результат при n=3?

Function F( n : integer ) : longint;

begin

if n < 2 then F := n

else F := F( n-1)+ F( n-2)

end;

Відповіді.

  • неможливо встановити.

  • 33.

  • 3

  • 2


4. Маємо два алгоритми сортування – сортування вставками і злиттям. Який з них за часом виконання більш кращий при значно великій кількості вихідних даних?

  • Обоє мають однаковий час виконання;

  • Кращий сортування вставками;

  • Кращий сортування злиттям.


5. Алгоритми Прима та Крускала – це:

  • Пошук Ейлерових шляхів графа.

  • Пошук максимальної течії в графі.

  • Пошук мінімального каркасного дерева.

  • Пошук за зразком.


6. Оцініть трудомісткість двох алгоритмів із заданими асимптотичними оцінками:

O(n2) і O(n*log2n), якщо кількість даних на вході алгоритму дорівнює n=10.

Який алгоритм кращий за оцінками ?

Відповіді.

  • неможливо встановити.

  • перший.

  • другий.

  • однакові.

7. Нехай заданий двомісний предикат P(x,y) : «x любить y». Як за допомогою логіки предикатів представити фразу – « Кожну людини хтось любить» ?

  • xyP(x,y).

  • xyP(x,y).

  • yxP(x,y).

  • xy(x,y).


8. До якого класу складності теорії алгоритмів відноситься задача про пошук гамільтонових шляхів у графі?

  • До класу P.

  • До класу NP.

  • До класу NPC.


9. Що означає в теорії алгоритмів поняття «час в найгіршому випадку»?

  • Нижня границя цієї величини для будь-яких вхідних даних .

  • Верхня границя цієї величини для будь-яких вхідних даних

  • Математичне сподівання часу праці.

  • Це гіпотетично неможливо.



10. Оберіть яку задачу розв’язує алгоритм Хаффмена?

  • Задачу мінімальної течії в графі.

  • Задачу максимальної течії в графі.

  • Задачу знаходження остових дерев.

  • Задачу кодування інформації.

Схожі:

Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй» iconТеорія алгоритмів та математична логіка. Питання на «задовільно». У чому складається основна ідея алгоритмічного методу «розподіляй І пануй»
Що мається на увазі в теорії алгоритмів коли говорять, що час виконання програми T(n)
Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй» iconПитання на 4 бали до тестування за курсом «Теорія алгоритмів І матлогіка»
Що мається на увазі в теорії алгоритмів коли говорять, що час виконання алгоритму Т(n) має порядок О(n2)?
Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй» iconЛітература за курсом «Теорія алгоритмів та математична логіка»
Т. Кормен, Ч. Лейзерсон, Р. Риверст, К. Штайн Алгоритмы: построение и анализ. М. Издат дом «Вильямс», 2005. 1296 с
Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй» iconПитання по дисципліні «Теорія алгоритмів та Математична логіка»

Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй» iconТести з дисципліни «Основи наукових досліджень»
Концепція це а система взаємозалежних І виникаючих один з одного поглядів, спосіб розуміння, трактування явищ, процесів; основна...
Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй» iconОпис модуля назва модуля: Якість програмного забезпечення та тестування Код модуля
Методи проектування тестових шляхів. Монолітна та інкрементна збірка модулів. Інтеграційне тестування І його особливості для об’єктно-орієнтованого...
Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй» iconПрограма фахового вступного випробування при прийомі на навчання за освітньо-кваліфікаційним рівнем «спеціаліст» та «магістр» за спеціальністю 7(8). 04030201 «Інформатика»
Дискретна математика”, „Теорія систем та математичне моделювання” та „Теорія алгоритмів та математична логіка” є фундаментальними...
Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй» iconАнотація навчальної дисципліни «Конструювання та аналіз алгоритмів»
Основна мета засвоєння курсу полягає у формуванні умінь складати ефективні алгоритми розвʼязку завдань програмування
Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй» iconАнотація навчальної дисципліни «Конструювання та аналіз алгоритмів»
Основна мета засвоєння курсу полягає у формуванні умінь складати ефективні алгоритми розвʼязку завдань програмування
Питання до тестування за курсом «Теорія алгоритмів І матлогика» у чому складається основна ідея алгоритмічного методу «розділяй І пануй» iconНазва модуля: Алгоритмічні основи криптології Код модуля
Евкліда, дослідження та аналіз алгоритмів та послідовностей за допомогою ланцюгових дробів, теорія складності, функціональні схеми,...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи