2011-gre-cs-practice-book.pdf/Q47 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
== Вопрос: Q47-08c765 ==
 
== Вопрос: Q47-08c765 ==
  
 +
Рассмотрим следующие 2 многопоточные задачи, в которых операции присваивания исполняются атомарно. Изначально, переменные с разделяемым состоянием x и y равны 0.
 +
 +
* Задача 1
 
<code-c>
 
<code-c>
−
i = 0;
+
x = 1
−
j = 0;
+
a = y
−
k = 0;
+
</code-c>
  
−
while (i < 10 and j < 10)
+
* Задача 2
−
{
+
<code-c>
−
    if (A[i] > B[j])
+
y = 1
−
    {
+
b = x
−
        C[k] = A[i];
+
−
        k = k + 1;
+
−
        i = i + 1;
+
−
    }
+
−
    else
+
−
    {
+
−
        C[k] = B[j];
+
−
        k = k + 1;
+
−
        j = j + 1;
+
−
    }
+
−
}
+
 
</code-c>
 
</code-c>
  
 +
В конце выполнения обеих многопоточных задач значения переменных a и b проверяются.
  
−
 
+
* I. a==0a==0 → b==1b==1
−
Какие из следующих утверждений могут служить инвариантом цикла для указанного выше цикла while?
+
* II. b==0b==0 → a==1a==1
−
 
+
* III. a==1a==1 → b==1b==1
−
* I. i < 10 или j < 10
+
−
* II. i < 11 и j < 11
+
−
* III. k = i + j
+
  
 
=== Ответы ===
 
=== Ответы ===
−
* (A) Только I
+
* (A) Только I
−
* (B) I и II
+
* (B) Только II
−
* (C) I и III
+
* (C) Только III
−
* (D) II и III 
+
* (D) I и II
−
* Правильный ответ: (E) I, II и III
+
* (E) I, II и III
  
 
=== Объяснение ===
 
=== Объяснение ===
  
−
{{cstest-source|2011-gre-cs-practice-book.pdf|37|46}}
+
{{cstest-source|2011-gre-cs-practice-book.pdf|38|46}}
−
 
+
−
Разберём каждое из утверждений
+
−
 
+
−
* I: i < 10 или j < 10
+
−
 
+
−
Из того, что i<10 и j<10, автоматически следует более слабое утверждение i<10 или j<10.
+
−
Пока цикл ещё не прерван, утверждение «i<10 или j<10» будет верно всегда. Следовательно, I действительно является инвариантом.
+
−
 
+
−
* II: i < 11 и j < 11
+
−
 
+
−
Внутри цикла мы имеем i <= 9 и j <= 9. Отсюда немедленно следует, что i < 11 и j < 11. Следовательно, II также является инвариантом.
+
−
 
+
−
* III: k = i + j
+
−
 
+
−
Перед входом в цикл имеем k = i + j = 0. В то же время либо инкрементируется i, либо j. Таким образом, соотношение сохраняется при переходе между итерациями и утверждение III является инвариантом.
+
  
 
{{question-ok|}}
 
{{question-ok|}}
 
{{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 20:53, 8 января 2025 (UTC)}}
 
{{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 20:53, 8 января 2025 (UTC)}}

Версия 23:56, 8 января 2025

Вопрос: Q47-08c765

Рассмотрим следующие 2 многопоточные задачи, в которых операции присваивания исполняются атомарно. Изначально, переменные с разделяемым состоянием x и y равны 0.

  • Задача 1
x = 1
a = y
  • Задача 2
y = 1
b = x

В конце выполнения обеих многопоточных задач значения переменных a и b проверяются.

  • I. a==0a==0 → b==1b==1
  • II. b==0b==0 → a==1a==1
  • III. a==1a==1 → b==1b==1

Ответы

  • (A) Только I
  • (B) Только II
  • (C) Только III
  • (D) I и II
  • (E) I, II и III

Объяснение

Исходники — вопрос 46 на 38 странице книги «2011-gre-cs-practice-book.pdf»

Задача зарезервирована: Nikitashapovalov 20:53, 8 января 2025 (UTC)

Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q47&oldid=35535»