Этапы решения алгоритмической задачи. Базовые структуры данных

Множество можно определить как неупорядоченную совокупность отдельных элементов, называемых элементами множества. Конкретное множество можно задать либо в виде явного списка элементов (например, `S ={2,3,5,7}`), либо в виде указания условия, которому должны удовлетворять все элементы множества и только они (например, `S ={n| n — "простое число" ^^ n< 10})`.

Если множество `U` состоит из `n` элементов, то любое его подмножество `S` можно представить в виде строки из `n` битов, в которой `i`-й элемент равен 1 тогда и только тогда, когда `i`-й элемент множества `U` включен в подмножество `S`. Например, если `U ={1,2,3,4,5,6,7,8,9}`, то подмножество `S ={2,3,5,7}` можно представить в виде битовой строки 011010100.

Описанный способ представления множеств позволяет реализовать стандартный набор операций над множеством в виде очень быстрых процедур. Однако платой за скорость является большой объем оперативной памяти, необходимой для представления элементов множества.

Следующий способ заключается в представлении элементов множества в виде списка. При этом важно понимать отличия между списком и множеством:

• в множестве не может быть одинаковых элементов, а в списке — может (но в мультимножестве элементы не обязательно различны);
• изменение порядка элементов множества не изменяет само множество, а список определяется как упорядоченный набор элементов

В том случае, когда множество представляется в виде списка, его элементы обычно отсортированы по возрастанию.

В алгоритмах над множеством (мультимножеством) чаще всего выполняются следующие операции: поиск заданного элемента, добавление нового элемента и удаление элемента из совокупности.

Третьим способом является двоичное дерево поиска.

Словарь (ассоциативный массив, отображение) обобщает структуры данных множество и массив и позволяет хранить пары вида (ключ, значение). К основным операциям над словарем относятся: добавления пары, поиска и удаления пары по ключу.

Для словарей можно использовать массивы, связные списки и двоичные деревья поиска.

Задания для практики

1. Предложите, как можно реализовать каждую из перечисленных ниже операций над последовательностями так, чтобы время ее выполнения не зависело от размера `n`.
   а) Замена i-го элемента
   б) Удаление i-го элемента (один раз, многократно)
   в) Добавление в конец последовательности
   г) Добавление в начало последовательности
   д) Добавление после указанного элемента
   Как это может повлиять на последующие действия с последовательностью (например, проход по всех элементам последовательности)?

2. Каким будет содержимое стека после выполнения каждой команды приведенной ниже последовательности, считая, что в исходном состоянии стек пуст:
   push (a), push(b), pop, push(с), push(d), pop.

3. Изобразите содержимое очереди после выполнения каждой команды приведенной ниже последовательности, считая, что в исходном состоянии очередь пуста:
   enqueue(a), enqueue(b), dequeue, enqueue(с), enqueue(d), dequeue.

4. Как бы вы реализовали словарь, содержащий достаточно малое количество элементов `n`, при условии, что все его элементы различны (например, представляют собой названия 50 штатов США)? Опишите реализацию каждой операции, выполняемой словарем.