Редактирование: Разрешение коллизий

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Разрешение [[Хеш-таблица|коллизий]]''' (англ. collision resolution) в [[Хеш-таблица|хеш-таблице]], задача, решаемая несколькими способами: метод цепочек, открытая адресация и т.д. Очень важно сводить количество коллизий к минимуму, так как это увеличивает время работы с хеш-таблицами.
+
{{Определение
 
+
|definition=
== Разрешение коллизий с помощью цепочек ==
+
Коллизия хеш-функции — это равенство значений хеш-функции на двух различных блоках данных.
[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]
+
}}
Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало [[Список|списка]] всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
 
  
В зависимости от того нужна ли нам уникальность значений операции вставки у нас будет работать за разное время. Если не важна, то мы используем список, время вставки в который будет в худшем случае равна <tex>O(1)</tex>. Иначе мы проверяем есть ли в списке данный элемент, а потом в случае его отсутствия мы его добавляем. В таком случае вставка элемента в худшем случае будет выполнена за <tex>O(n)</tex>
+
'''Разрешение коллизий''' в хеш-таблице, задача, решаемая несколькими способами. Можно использовать списки, а можно открытую адресацию.
  
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов.
+
При использовании списков особых проблем не возникает, так как там в каждой ячейке хранится список всех элементов. При добавлении необходимо просто добавить элемент в начало списка.
  
Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка.
+
При открытой адресации будет иначе: в каждой ячейке хеш-таблицы хранится только один элемент. Тогда при добавлении, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейку. Однако если эта ячейка занята {{---}} необходимо поместить добавляемый элемент в какую-нибудь другую свободную ячейку. Такие ситуации нередки, так как невозможно использовать хеш-функцию, не дающую коллизий, а каждой ячейке таблицы соответствует одно значение хеш-функции. Далее мы рассмотрим несколько стратегий поиска свободного места в данном случае.
  
== Линейное разрешение коллизий ==
+
== Стратегии поиска ==
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
 
Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно, будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.
 
 
 
=== Стратегии поиска ===
 
  
 
''' Последовательный поиск '''
 
''' Последовательный поиск '''
Строка 36: Строка 31:
 
[[Файл:hashtables3.png|400px|Квадратичный поиск.]]
 
[[Файл:hashtables3.png|400px|Квадратичный поиск.]]
  
=== Проверка наличия элемента в таблице===
+
== Проверка наличия элемента в таблице==
  
 
Проверка осуществляется аналогично добавлению: мы проверяем ячейку <tex>i</tex> и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.
 
Проверка осуществляется аналогично добавлению: мы проверяем ячейку <tex>i</tex> и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.
Строка 42: Строка 37:
 
При поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца, пока мы не придём в ту ячейку, откуда начинался поиск.
 
При поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца, пока мы не придём в ту ячейку, откуда начинался поиск.
  
=== Проблемы данных стратегий ===
+
== Проблемы данных стратегий ==
  
 
Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров  — последовательностей занятых ячеек.
 
Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров  — последовательностей занятых ячеек.
  
 
Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.
 
Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.
Для защиты от кластеризации используется двойное хеширование и [[Хеширование кукушки|хеширование кукушки]].
+
Для защиты от кластеризации используется Двойное хеширование и [[Хеширование кукушки|хеширование кукушки]].
  
=== Удаление элемента без пометок ===
+
 
 +
== Удаление элемента без пометок ==
  
 
Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на <tex>q</tex> позиций назад. При этом:
 
Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на <tex>q</tex> позиций назад. При этом:
Строка 60: Строка 56:
 
''' Псевдокод '''
 
''' Псевдокод '''
  
'''function''' delete('''Item''' i):
+
  delete(i)  
 
       j = i + q
 
       j = i + q
       '''while''' table[j] == ''null'' '''or''' table[j].key != table[i].key
+
       while table[j] == null || table[j].key != table[i].key
         '''if''' table[j] == ''null''
+
         if (table[j] == null)
             table[i] = ''null''
+
             table[i] = null
             '''return'''
+
             exit
 
         j += q
 
         j += q
 
       table[i] = table[j]
 
       table[i] = table[j]
       delete(j)  
+
       delete(j);     
  
 
Хеш-таблицу считаем зацикленной
 
Хеш-таблицу считаем зацикленной
Строка 77: Строка 73:
 
|statement=Асимптотически время работы <tex>\mathrm{delete}</tex> и <tex>\mathrm{find}</tex> совпадают
 
|statement=Асимптотически время работы <tex>\mathrm{delete}</tex> и <tex>\mathrm{find}</tex> совпадают
 
|proof=
 
|proof=
Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>\mathrm{delete}</tex>). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего {{---}} с учётом вызова <tex>\mathrm{find}</tex> собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.
+
Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>\mathrm{delete}</tex>). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего - с учётом вызова <tex>\mathrm{find}</tex> собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.
 
}}
 
}}
  
Строка 92: Строка 88:
  
 
==Двойное хеширование==
 
==Двойное хеширование==
'''Двойное хеширование''' (англ. double hashing) {{---}} метод борьбы с коллизиями, возникающими при открытой адресации, основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.
+
'''Двойное хеширование''' {{---}} метод борьбы с коллизиями, возникающими при открытой адресации, основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.
  
 
===Принцип двойного хеширования===
 
===Принцип двойного хеширования===
При двойном хешировании используются две независимые хеш-функции <tex> h_1(k) </tex> и <tex> h_2(k) </tex>. Пусть <tex> k </tex> {{---}} это наш ключ, <tex> m </tex> {{---}} размер нашей таблицы, <tex>n \bmod m </tex> {{---}} остаток от деления <tex> n </tex> на <tex> m </tex>, тогда сначала исследуется ячейка с адресом <tex> h_1(k) </tex>, если она уже занята, то рассматривается <tex> (h_1(k) +  h_2(k)) \bmod m </tex>, затем <tex> (h_1(k) +  2 \cdot h_2(k)) \bmod m </tex> и так далее. В общем случае идёт проверка последовательности ячеек <tex> (h_1(k) +  i \cdot h_2(k)) \bmod m </tex> где <tex>  i = (0, 1, \; ... \;,  m - 1) </tex>
+
При двойном хешировании используются две независимые хеш-функции <tex> h_1(k) </tex> и <tex> h_2(k) </tex>. Пусть <tex> k </tex> {{---}} это наш ключ, <tex> m </tex> {{---}} размер нашей таблицы, <tex>n \mod m </tex> {{---}} остаток от деления <tex> n </tex> на <tex> m </tex>, тогда сначала исследуется ячейка с адресом <tex> h_1(k) </tex>, если она уже занята, то рассматривается <tex> (h_1(k) +  h_2(k)) \mod m </tex>, затем <tex> (h_1(k) +  2 \cdot h_2(k)) \mod m </tex> и так далее. В общем случае идёт проверка последовательности ячеек <tex> (h_1(k) +  i \cdot h_2(k)) \mod m </tex> где <tex>  i = (0, 1, \; ... \;,  m - 1) </tex>
  
 
Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за <tex>O(1)</tex>, в худшем {{---}} за <tex>O(m)</tex>, что не отличается от обычного [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейного разрешения коллизий]].
 
Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за <tex>O(1)</tex>, в худшем {{---}} за <tex>O(m)</tex>, что не отличается от обычного [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейного разрешения коллизий]].
Строка 112: Строка 108:
 
Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h_2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй {{---}} размер таблицы является степенью двойки, а <tex> h_2 </tex> возвращает нечетные значения.
 
Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h_2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй {{---}} размер таблицы является степенью двойки, а <tex> h_2 </tex> возвращает нечетные значения.
  
Например, если размер таблицы равен <tex> m </tex>, то в качестве <tex> h_2 </tex> можно использовать функцию вида <tex> h_2(k) = k \bmod (m-1) + 1 </tex>
+
Например, если размер таблицы равен <tex> m </tex>, то в качестве <tex> h_2 </tex> можно использовать функцию вида <tex> h_2(k) = k \mod (m-1) + 1 </tex>
  
 
[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
 
[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
Строка 121: Строка 117:
  
 
<center>
 
<center>
<tex> h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod 13 </tex>
+
<tex> h(k,i) = (h_1(k) + i \cdot h_2(k)) \mod 13 </tex>
 
</center>
 
</center>
  
 
<center>
 
<center>
<tex> h_1(k) = k \bmod 13 </tex>
+
<tex> h_1(k) = k \mod 13 </tex>
 
</center>
 
</center>
  
 
<center>
 
<center>
<tex> h_2(k) = 1 + k \bmod 11 </tex>
+
<tex> h_2(k) = 1 + k \mod 11 </tex>
 
</center>
 
</center>
  
Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0\cdot h_2(14)) \bmod 13 = 1 </tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем <tex> i </tex> на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При <tex> i = 2 </tex> получаем <tex> h(14,2) = (h_1(14) + 2\cdot h_2(14)) \bmod 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.
+
Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0\cdot h_2(14)) \mod 13 = 1 </tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем <tex> i </tex> на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При <tex> i = 2 </tex> получаем <tex> h(14,2) = (h_1(14) + 2\cdot h_2(14)) \mod 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.
  
 
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследования.
 
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследования.
Строка 142: Строка 138:
  
 
'''Вставка'''
 
'''Вставка'''
'''function''' add('''Item''' item):
+
<pre>add(item)
      x = h1(item.key)
+
  x = h1(item.key)
      y = h2(item.key)
+
  y = h2(item.key)
        '''for''' (i = 0..m)   
+
  for (i = 0; i < m; i++)   
            '''if''' table[x] == ''null''
+
      if table[x] == null
              table[x] = item
+
        table[x] = item
            '''return'''      
+
        return       
        x = (x + y) '''mod''' m   
+
      x = (x + y) mod m   
      table.resize()<span style="color:Green">// ошибка, требуется увеличить размер таблицы
+
  table.resize() //ошибка, требуется увеличить размер таблицы</pre>
  
 
'''Поиск'''
 
'''Поиск'''
'''Item''' search('''Item''' key):
+
<pre>search(key)
      x = h1(key)
+
  x = h1(key)
      y = h2(key)
+
  y = h2(key)
      '''for''' (i = 0..m)
+
  for (i = 0; i < m; i++)
        '''if''' table[x] != ''null''
+
      if table[x] != null
            '''if''' table[x].key == key
+
        if table[x].key == key
              '''return''' table[x]
+
            return table[x]
            '''else'''
+
      else
              '''return''' ''null''
+
        return null
       x = (x + y) '''mod''' m   
+
       x = (x + y) mod m   
      '''return''' ''null''
+
  return null</pre>
  
 
===Реализация с удалением===
 
===Реализация с удалением===
Чтобы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
+
Что бы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
  
 
'''Вставка'''
 
'''Вставка'''
'''function''' add('''Item''' item):
+
<pre>add(item)
      x = h1(item.key)
+
  x = h1(item.key)
      y = h2(item.key)
+
  y = h2(item.key)
      '''for''' (i = 0..m) 
+
  for (i = 0; i < m; i++
        '''if''' table[x] == '''null''' '''or''' deleted[x]
+
      if table[x] == null || deleted[x]
            table[x] = item
+
        table[x] = item
            deleted[x] = '''false'''
+
        deleted[x] = false
            '''return'''      
+
        return       
        x = (x + i * y) '''mod''' m   
+
      x = (x + y) mod m   
      table.resize()<span style="color:Green">// ошибка, требуется увеличить размер таблицы
+
  table.resize() //ошибка, требуется увеличить размер таблицы</pre>
 +
 
 
'''Поиск'''
 
'''Поиск'''
'''Item''' search('''Item''' key):
+
<pre>search(key)
      x = h1(key)
+
  x = h1(key)
      y = h2(key)
+
  y = h2(key)
      '''for''' (i = 0..m)  
+
  for (i = 0; i < m; i++)  
        '''if''' table[x] != '''null'''
+
      if table[x] != null
            '''if''' table[x].key == key '''and''' !deleted[x]
+
        if table[x].key == key && !deleted[x]
              '''return''' table[x]
+
            return table[x]
        '''else'''
+
      else
            '''return''' '''null'''
+
        return null
        x = (x + y) '''mod''' m   
+
      x = (x + y) mod m   
      '''return''' '''null'''
+
  return null</pre>
  
 
'''Удаление'''
 
'''Удаление'''
'''function''' remove('''Item''' key):
+
<pre>remove(key)
      x = h1(key)
+
  x = h1(key)
      y = h2(key)
+
  y = h2(key)
      '''for''' (i = 0..m)
+
  for (i = 0; i < m; i++)
        '''if''' table[x] != '''null'''
+
      if table[x] != null
            '''if''' table[x].key == key
+
        if table[x].key == key
              deleted[x] = '''true'''
+
            deleted[x] = true
        '''else'''
+
      else  
            '''return'''
+
        return
       x = (x + y) '''mod''' m
+
       x = (x + y) mod m</pre>
 +
 
 +
== Разрешение коллизий с помощью списков ==
 +
 
 +
Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало списка всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
 +
 
 +
Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в таблице, но если потребуется, то перед вставкой мы можем выполнить поиск этого элемента.
  
==Альтернативная реализация метода цепочек==
+
[[Файл:open_hash.png|420px|Разрешение коллизий при помощи цепочек.]]
В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данная корзина переходит от использования связного списка к использованию [[АВЛ-дерево|сбалансированного дерева]]. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан [[Отношение порядка|линейный порядок]]. То есть при использовании данный типа <tex>\mathbf{int}</tex> или <tex>\mathbf{double}</tex> имеет смысл переходить к дереву поиска, а при использовании каких-нибудь ссылок на объекты не имеет, так как они не реализуют нужный интерфейс. Такой подход позволяет улучшить производительность с <tex>O(n)</tex> до <tex>O(\log(n))</tex>. Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.
 
  
[[Файл:Hashing_in_Java8.png|500px|Хеширование в Java 8.]]
+
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов.
 +
 
 +
Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка.
  
 
==См. также==
 
==См. также==
 
* [[Хеширование]]
 
* [[Хеширование]]
 
* [[Хеширование_кукушки|Хеширование кукушки]]
 
* [[Хеширование_кукушки|Хеширование кукушки]]
* [[Идеальное_хеширование|Идеальное хеширование]]
 
  
== Источники информации ==
+
== Литература ==
* Бакнелл Дж. М. «Фундаментальные алгоритмы и структуры данных в Delphi», 2003
+
* Бакнелл Дж. М. '''Фундаментальные алгоритмы и структуры данных в Delphi''', ''2003''
* Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010.— Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
+
* Кнут Д. Э. '''Искусство программирования, том 3. Сортировка и поиск''', ''2-е издание, 2000''
* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} «Вильямс», 2007 г.{{---}} ISBN 0-201-89685-0
+
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''', ''2010''
* Седжвик Р. «Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск», 2003
+
* Седжвик Р. '''Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск''', ''2003''
* [http://openjdk.java.net/jeps/180 Handle Frequent HashMap Collisions with Balanced Trees]
+
 
 +
==Ссылки==
 
* [http://en.wikipedia.org/wiki/Double_hashing Wikipedia {{---}} Double_hashing]
 
* [http://en.wikipedia.org/wiki/Double_hashing Wikipedia {{---}} Double_hashing]
 
* [http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0 Разрешение коллизий]
 
* [http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0 Разрешение коллизий]
Строка 227: Строка 231:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Хеширование]]
 
[[Категория: Хеширование]]
[[Категория: Структуры данных]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: