Различия между версиями 13 и 14
Версия 13 от 2011-05-07 02:40:50
Размер: 4290
Редактор: PavelSutyrin
Комментарий:
Версия 14 от 2011-05-07 02:41:22
Размер: 4311
Редактор: PavelSutyrin
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 22: Строка 22:
  1. Почитать про [[http://ru.wikipedia.org/wiki/Индексный_массив|массивы]], [[http://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA|списки]], [[http://ru.wikipedia.org/wiki/%D0%90%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2|ассоциативные массивы]], [[http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5|хэширование]], [[http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0|двоичные деревья поиска]] и более ветвистые [[http://ru.wikipedia.org/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE|B-деревья]], [[http://ru.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE|AVL-]], [[http://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE|красно-черные]] и [[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE|декартовы]] деревья.   1. Почитать про [[http://ru.wikipedia.org/wiki/Индексный_массив|индексные массивы]], [[http://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA|списки]] и [[http://ru.wikipedia.org/wiki/%D0%90%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2|ассоциативные массивы]], [[http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5|хэширование]], [[http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0|двоичные деревья поиска]] и более ветвистые [[http://ru.wikipedia.org/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE|B-деревья]], [[http://ru.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE|AVL-]], [[http://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE|красно-черные]] и [[http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE|декартовы]] деревья.

Тема занятия: структуры данных и поиск

  • {o} — тема по Linux

  • <!> ­— необязательная тема

  • массив -- прямой доступ: быстро, но требует памяти (если неплотный набор ключей)
  • список -- ассоциативный доступ: разумно по памяти, медленный поиск
  • хеш-таблицы, в Питоне функция hash(), реализация словарей

  • Полиномиальное хеширование
    • H=(a0*p**0+a1*p**1+...+an*p**n)%2**16, где p -- простое число, например, 31337, а a0..an -- числа из хэшируемой последовательности (в случае строки символов -- коды символов)
  • Дерево бинарного поиска [значение, поддерево-меньше, поддерево-больше]
    • оптимальное дерево: размер(поддерево-меньше)~=размер(поддерево-больше)
    • заполнение дерева с перебалансировкой
      • виды деревьев: AVL, красно-чёрное, декартово
    • дерево поиска в общем виде [значение,поддерево-<K1,поддерево-K1<k2,...,поддерево-kn-1<соответственkn,поддерево->kn)] -- несколько ключей. Соответственный показатель степени и основание логарифма для количества узлов и уровней.

Домашнее задание

  • {i} — теоретическое задание

  • {*} — новая тема

  1. Почитать про индексные массивы, списки и ассоциативные массивы, хэширование, двоичные деревья поиска и более ветвистые B-деревья, AVL-, красно-черные и декартовы деревья.

  2. Сгенерировать текстовый файл с таблицей вида [уникальное случайное число, случайная строка] на 10**5 элементов. Измерить (например, с помощью функции times() из модуля os) время поиска элемента по 1000 поисковых проб в этих данных, представленных в виде

    1. линейного списка
    2. хешированной таблицы
    3. двоичного дерева (заполняемого с балансировкой и без балансировки)
    4. стандартного словаря (dict)
  3. Задача №765. Частоты появления элементов

  4. Задача №744. Хеширование


CategoryClass CategoryVmsh

LecturesVMSH/2011-05-04 (последним исправлял пользователь FrBrGeorge 2011-05-11 14:52:26)