Графы

Основные модели

Под графом мы будем понимать пару множеств \(V\) и \(E\) и пару отображений \(s,t:E\to V\). Традиционные названия:

• элементы \(V\) называются вершинами
• элементы \(E\) называются рёбрами
• отображение \(s\) называется начало ребра
• отображение \(v\) называется конец ребра

Для многих приложений информация о «направлении» рёбер избыточна. В таких ситуациях вместо отображений \(s\) и \(t\) достаточно одно отображение \(v:E\to \mathrm{P}V\), сопоставляющее каждому ребру одно- или двухэлементное подмножество множества \(V\). Соответствующий математический объект называется неориентированным графом.

На практике (как в информатике, так и в алгебраических областях математики) неориентированные графы всё равно почти всегда заменяют ориентированными, поэтому по-умолчанию, говоря о графах, мы будем иметь в виду их ориентированную разновидность.

Небольшое предисловие

Далее многие понятия и алгоритмы пояснены программным кодом. Весь программный код приведён на языке Python, если не оговорено иное.

Небольшая шпаргалка по Python доступна здесь. За всем остальным рекомендуется обращаться на официальный сайт или на informatics.

Обратим также внимание, что (в силу другого формата) изложение материала здесь отличается от такового на уроках, но содержание затрагиваемого материала примерно такое же.

Подраздел «упражнения» в конце каждого раздела следует рассматривать как (обязательное) домашнее задание. После раздела с упражнениями идёт раздел с (необязательными) задачами повышенной сложности: их выполнение может потребовать значительных затрат времени (но при этом может дать какой-то новый взгляд на рассматриваемый материал).

Предостережение о деревьях

В математике деревом называется связный неориентированный граф без циклов. В информатике деревьями обычно называют другой вид данных, традиционно называемый в математике словом «формула».

А именно, (непустым) деревом называется единица данных, спаренная с последовательностью деревьев (обратите внимание на рекурсию в определении!).

Например, формальным представлением формулы \((2+3\cdot 4)/5\) может являться программа

('/', [
  ('+', [
    (2,[]),
    ('*', [
      (3, []), 
      (4, [])
    ])
  ]),
  (5,[])
])

На этом разговор о деревьях мы (временно) закончим.

Наивная модель

Наиболее простой способ моделировать граф — списком его рёбер. Например, так:

[
  ('A', (1,3)), 
  ('B', (1,4)), 
  ('C', (2,4)),
  ('D', (1,3)),
]

Такая модель неявно предполагает, что множество вершин содержит числа 1, 2, 3 и 4.

Подобным образом можно моделировать и неориентированный граф:

[
  ('A', {1,3}), 
  ('B', {1,4}), 
  ('C', {2,4}),
  ('D', {1,3}),
]

Проблема такого подхода в следующем: для того, чтобы ответить на вопрос «с какими вершинами соединена такая-то вершина?» или вопрос «какие рёбра соединяют такую-то пару вершин?», нужно пройтись по всему списку (ресурсозатраты на такую операцию пропорциональны общему количеству рёбер в графе).

Оказывается, можно обойтись существенно меньшими ресурсами.

Матрица смежности

Научимся сначала отвечать на вопрос «какие рёбра соединяют такую-то пару вершин?».

Для этого можно построить отображение вида

def edges_of_vertices(v1, v2):
  if (v1,v2) == (1,3): return ['A','D']
  if (v1,v2) == (1,4): return ['B']
  if (v1,v2) == (2,4): return ['C']
  return []

Само по себе оно ничем не лучше списка рёбер. Но далее можно воспользоваться эквивалентностью множеств \(A\times B\to C\) и \(A\to(B\to C)\):

# отображение edges_of_vertices2 построено так, чтобы выполнялось
# edges_of_vertices2(v1)(v2) == edges_of_vertices(v1,v2)
def edges_of_vertices2(v1):
  def f1(v2):
    if v2 == 3: return ['A','D']
    if v2 == 4: return ['B']
    return []

  def f2(v2):
    if v2 == 4: return ['C']
    return []

  def f(v2): return []

  if v1 == 1: return f1
  if v1 == 2: return f2
  return f

Полученное отображение тоже ничем не лучше списка рёбер. Но дальше можно заметить, что его вход (и вход отображения, им возвращаемого) — целое число. Этим можно воспользоваться, заменив каждое отображение на массив своих значений:

graph_table = [
  [[], [], [], [],        []],
  [[], [], [], ['A','D'], ['B']],
  [[], [], [], [],        ['C']],
  [[], [], [], [],        []],
  [[], [], [], [],        []],
]

Теперь выражение edges_of_vertices(v1,v2) почти эквивалентно выражению graph_table[v1][v2]. Почти — поскольку при некорректных v1 и v2 первое выражение равно пустому списку, а второе в процессе вычисления выдаёт ошибку.

Такой подход называется (плотной) матрицей смежности графа. Матрица смежности позволяет ответить на вопрос о рёбрах между заданной парой вершин за время, пропорциональное размеру ответа, а не общему количеству рёбер в графе.

Плотные и разреженные матрицы

У вышеприведённого подхода есть несколько недостатков:

• требуется каким-то образом сопоставлять вершинам целые числа (причём желательно — в непрерывном диапазоне от 0 до чего-нибудь)
• занимаемая матрицей смежности память пропорциональна квадрату количества вершин
• матрица смежности требует некоторых модификаций для быстрого ответа на вопрос о соседях заданной вершины (например, можно хранить ответ на этот вопрос прямо в ней по какому-нибудь незанятому индексу внутреннего массива)

Тем не менее, в случае, когда почти любая пара вершин соединена хотя бы одним ребром, такой подход зачастую оказывается наиболее эффективным.

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

graph_sparse_table = {
  1: {3: ['A', 'D'], 
      4: ['B']},

  2: {4: ['C']},
}

Упражнения

Упражнения нужно сдавать одним файлом мне на почту (arbrk1@gmail.com). В каждом упражнении требуется написать одну или несколько функций.

В файле должны быть (можно не все) требуемые функции, причём именно с такими названиями, с какими они требуются. Также допускаются определения вспомогательных функций. Но вне определений функций никакого кода быть не должно!

Всё же, каков ответ на те два вопроса?

Для разреженной матрицы можно написать функции

def edges_of_vertices(g, v1, v2):
  if not (v1 in g): return []
  if not (v2 in g[v1]): return []
  return g[v1][v2]

def neighbors(g, v):
  if not (v in g): return []
  
  return [n for n in g[v]]

Напишите аналогичные функции (именно с такими названиями) для плотной матрицы.

Очень плотная матрица смежности

Очень плотная матрица смежности получается из матрицы смежности плотной упаковкой внутренних массивов:

def pack(g):
  vertex_count = len(g)
  return (vertex_count, [x for row in g for x in row])

Напишите функции packed_edges_of_vertices и packed_neighbors, работающие с очень плотными матрицами смежности.

Обратите внимание на то, что решение вида:

def unpack(g):
  n,m = g

  return  [m[i*n : (i+1)*n] for i in range(n)]

def packed_edges_of_vertices(g, v1, v2):
  return edges_of_vertices(unpack(g), v1, v2)

def packed_neighbors(g, v):
  return neighbors(unpack(g), v)

не принимается: время его работы пропорционально квадрату количества вершин. Должно же быть (с точностью до постоянного множителя) не больше, чем у обычных edges_of_vertices и neighbors соответственно.

Задачи повышенной сложности

Текст по дереву

Напишите функцию text_of_tree, восстанавливающую (текстовую) формулу по соответствующему дереву. Например,

text_of_tree(('/', [('+', [(2,[]),('*', [(3, []), (4, [])])]),(5,[])]))

должно выдавать что-то наподобие

"(2 + (3 * 4)) / 5"

Допускается другая расстановка скобок.

Дерево по тексту

Напишите функцию tree_of_text, строящую дерево по текстовому представлению формулы. Для простоты можно считать, что в тексте допускаются только скобки, пробелы, числа и знак +.

Помните, что если скобок не хватает, то они ставятся традиционным образом:

tree_of_text("1+2+3") == ( '+', [ ( '+', [ (1,[]), (2,[]) ] ), (3,[]) ] )

Некоторые задачи

Здесь будут публиковаться разборы некоторых из задач из списка.

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

Программный интерфейс разреженной матрицы смежности

Для того, чтобы общаться с графом, мы будем использовать следующий интерфейс:

def empty_graph(n):
  return { (x+1): {} for x in range(n) }

def graph_size(g):
  return len(g)

def add_edge(g, v1, v2):
  if v2 in g[v1]: g[v1][v2] += 1
  else: g[v1][v2] = 1

def set_edge(g, v1, v2, e):
  g[v1][v2] = e

def get_edge(g, v1, v2):
  if v2 in g[v1]: return g[v1][v2]
  return 0

def neighbors(g, v):
  return [(n, g[v][n]) for n in g[v]]

Этот интерфейс отличается от edges_of_vertices/neighbors из предыдущего раздела. Основные отличия:

• вершинами являются не все целые числа, а только конечный их отрезок, начинающийся с единицы
• в матрице хранятся не сами рёбра, а только их кратности
• neighbors возвращает не только соседние вершины, но и кратности соответствующих рёбер

Ввод-вывод графов

Это по большей части задачи с E по H. Начнём с двух способов печати графа: как квадратной таблицы и как списка рёбер.

def print_graph_matrix(g):
  N = graph_size(g)

  for y in range(N):
    print(' '.join([
      str(get_edge(g, y+1,x+1)) for x in range(N)
    ]))

def print_graph_edges(g, directed=False):
  N = graph_size(g)
  
  for i in range(N):
    v = i+1

    for x,e in neighbors(g,v):
      if directed or v <= x:
        for _ in range(e): print(str(v), str(x))

Если не удалось понять, как работает вышеприведённая функция print_graph_matrix, предлагаем альтернативную реализацию:

def print_graph_matrix(g):
  N = graph_size(g)

  for y in range(N):
    for x in range(N):
      end = ' ' if x < N-1 else '\n'
      print(get_edge(g, y+1, x+1), end=end)

Теперь рассмотрим ввод графов в таком виде:

def read_graph_matrix_with_sizes():
  return read_graph_matrix(int(input()))

def read_graph_matrix(N):
  g = empty_graph(N)

  for i in range(N):
    numbers = [int(x) for x in input().split()]
    for j,e in enumerate(numbers):
      if e > 0: set_edge(g, i+1, j+1, e)

  return g

def read_graph_edges_with_sizes(directed=False):
  N, E = [int(x) for x in input().split()]
  return read_graph_edges(N,E,directed)

def read_graph_edges(N,E,directed=False):
  g = empty_graph(N)

  for i in range(E):
    v1, v2 = [int(x) for x in input().split()]
    add_edge(g, v1, v2)
    if not directed: add_edge(g, v2, v1)

  return g

В терминах этих функций задачи E, F, G, H решаются так:

def E():
  print_graph_edges(read_graph_matrix_with_sizes())

def F():
  print_graph_matrix(read_graph_edges_with_sizes())

def G():
  print_graph_edges(read_graph_matrix_with_sizes(), True)

def H():
  print_graph_matrix(read_graph_edges_with_sizes(True))

Ещё несколько задач

Задача B: есть ли в графе петли?

def B():
  if has_loops(read_graph_matrix_with_sizes()):
    print("YES")
  else:
    print("NO")

def has_loops(g):
  N = graph_size(g)

  for v in range(1,N+1):
    if get_edge(g, v, v) > 0: return True

  return False

Задача C: количество рёбер неориентированного графа.

def C():
  print(count_edges(read_graph_matrix_with_sizes()))

def count_edges(g):
  N = graph_size(g)

  total = 0
  for v in range(1,N+1):
    for x,count in neighbors(g,v):
      if x >= v: total += count

  return total

Задача I: разворот рёбер ориентированного графа, заданного списками смежности.

def read_inverted_graph_lists(N):
  g = empty_graph(N)

  for i in range(N):
    for x in input().split():
      v = int(x)
      add_edge(g, v, i+1) ## разворачиваем сразу при добавлении

  return g

def print_graph_lists(g):
  N = graph_size(g)

  for i in range(N):
    v = i+1
    
    for x,_ in sorted(neighbors(g,v)):
      print(x, end=' ')

    print()

def I():
  N = int(input())
  g = read_inverted_graph_lists(N)

  print(N)
  print_graph_lists(g)

Базы данных

Общая информация

Термины СУБД и БД

Системой управления базами данных (СУБД) называют программное средство, позволяющее хранить информацию и извлекать хранимую информацию. В каком-то смысле, даже обычный массив в языке Си вместе с операциями индексации и индексированного присваивания можно считать примером очень примитивной СУБД. Тем не менее, обычно к СУБД подобные элементарные вещи не относят.

Обычно СУБД поддерживают возможность изолировать подмножества хранимых данных друг от друга. Единицы изоляции называют базами данных (БД). Например, если в качестве СУБД рассматривать только вышеупомянутые операции индексации и индексированного присваивания языка Си, то отдельными БД для такой СУБД будут массивы.

По факту понятия СУБД и БД часто используют как синонимы: ни к какой особой путанице это не приводит.

Реляционные БД

В этой главе мы обсудим т.н. реляционную модель СУБД/БД. Реляционная БД (именно БД как единица изоляции) представляет собой набор именованных прямоугольных таблиц. Каждая таблица имеет некоторое фиксированное (на момент создания таблицы) множество именованных столбцов.

Единица хранения (т.н. запись) — строка таблицы. В таблицу в любой момент можно (эффективно) добавлять новые строки или удалять из неё уже имеющиеся там. Обычно разрешаются «неполные» строки: некоторые ячейки в такой строке могут быть пустыми.

Обратим внимание на главные отличия реляционных БД от похожей формы хранения и обработки информации — электронных таблиц:

• основное назначение БД (не только реляционных) — хранение и поиск информации; основное назначение электронных таблиц — преобразование информации
• в реляционных БД единицей хранимой информации является строка, в электронных таблицах — клетка
• как побочный эффект предыдущего: строки и столбцы электронных таблиц равноправны; строки и столбцы реляционной БД — нет

Основа реляционной модели — язык SQL, на котором строятся запросы к реляционной БД. Изначально (в 70х годах) этот язык не отождествлялся с реляционной моделью. В настоящее время, говоря о реляционных БД/СУБД, подразумевают обычно именно ту или иную реализацию языка SQL.

СУБД SQLite

В качестве реализации языка SQL мы будем использовать СУБД SQLite. Сразу отметим, что она весьма сильно отличается от остальных распространённых реализаций SQL и во многом не соответствует стандарту. Тем не менее, она наиболее проста для использования.

Для Windows-систем можно скачать с официального сайта архив sqlite-tools, содержащий интерпретатор SQL-команд sqlite3. Для POSIX-совместимых систем (в том числе WSL) интерпретатор sqlite3 можно установить при помощи менеджера пакетов.

Работа с SQLite-базами при помощи интерпретатора команд — далеко не основной режим работы. Тем не менее, с точки зрения процесса обучения, он является одним из наиболее удобных.

Если запустить sqlite3 без аргументов, он создаёт БД в памяти. Создать БД в файле можно одним из двух способов:

• дать интерпретатору команду .open название_файла
• запустить интерпретатор с названием файла в качестве аргумента командной строки

Также отметим ресурсы SQL Online и sql.js, предоставляющие альтернативные sqlite3 интерпретаторы команд СУБД SQLite.

Основы языка SQL

Заполнение БД

Каждая команда языка SQL, вбитая в интерпретатор, должна завершаться точкой-с-запятой (.open не является командой языка SQL).

Чтобы создать таблицу, используется команда

CREATE TABLE название_таблицы(столбец1,столбец2, ...);

Язык SQL является регистронезависимым (в разумных пределах: нелатинские буквы в названиях таблиц и колонок обычно допускаются, но поведение таких названий не регламентировано). Тем не менее, обычно части SQL-команд пишут заглавными буквами, а названия таблиц и столбцов — маленькими. Если название таблицы или столбца состоит из нескольких слов или использует служебные символы, его экранируют двойными кавычками.

Для того, чтобы удалить таблицу foobar, можно воспользоваться командой

DROP TABLE foobar;

Чтобы посмотреть названия таблиц и их колонок, можно воспользоваться командой .schema (естественно, это команда интерпретатора sqlite3, а не языка SQL; в других СУБД это делается по-другому).

Чтобы добавить строчку в таблицу foobar, можно написать

INSERT INTO foobar(столбец1, столбец2, ...) VALUES(значение1, значение2, ...);

Чтобы оставить ячейку пустой, можно воспользоваться специальным словом NULL или не указывать её в списке столбцов, в которые добавляются данные. Числовые данные записываются цифрами (и десятичной точкой, если нужно). Текстовые данные заключаются в одинарные кавычки.

Довольно распространённая практика — включать в таблицу уникальный идентификатор записи. Обычно это делается так:

CREATE TABLE foobar(id INTEGER PRIMARY KEY, остальные столбцы);

В данном случае INTEGER PRIMARY KEY — указание типа данных столбца с названием id. Такой тип данных обеспечивает:

• быстрый поиск по значениям этой колонки
• уникальность значений в этой колонке
• непустоту ячеек этой колонки

На последнем пункте остановимся отдельно: если не указывать этот столбец при добавлении данных, значение ячейки будет сгенерировано автоматически. Это очень удобно!

Можно (а по стандарту SQL — нужно) указать типы и остальных столбцов. Но конкретно СУБД SQLite является динамически типизированным, при этом пытаясь (не очень простым образом) эмулировать поведение более классических СУБД. Поэтому для простоты договоримся не указывать типы данных столбцов, не являющихся идентификатором записи.

Работа с БД

Напомним, что основной режим работы с БД — извлечение нужной информации. Для этого используется команда SELECT. Наиболее простая её разновидность устроена так:

SELECT формат_вывода FROM таблица WHERE условия_на_запись;

Такая команда достаёт из указанной таблицы все записи, удовлетворяющие заданному условию, и выдаёт их в заданном формате.

Например, рассмотрим БД со схемой:

CREATE TABLE people(id INTEGER PRIMARY KEY, name, age);

Чтобы получить имена всех людей, которым больше 30 лет, можно сделать такой запрос:

SELECT name FROM people WHERE age > 30;

В формате вывода можно перечислить несколько выражений через запятую, например (в предположении наличия таблицы numbers с колонками x и y):

SELECT x, y, x+y FROM numbers;

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

Например, в предположении следующей схемы БД

CREATE TABLE people(id INTEGER PRIMARY KEY, name);
CREATE TABLE ages  (id INTEGER PRIMARY KEY, people_id, age);

для получения имён всех людей, которым больше 30 лет, можно использовать запрос

SELECT name FROM people,ages WHERE people.id = people_id AND age > 30;

Обратите внимание на то, что нам пришлось явно указать people.id, поскольку есть ещё колонка ages.id. В том случае, когда в запросе есть две таблицы с одинаковым названием, их можно на время запроса переименовать:

SELECT a.name, b.name FROM people AS a, people AS b; 

Ещё бывают полезны агрегатные запросы. Например, чтобы посчитать сумму построчных произведений чисел таблицы numbers со столбцами x, y и z, можно воспользоваться запросом

SELECT sum(x*y*z) FROM numbers;

Для sum(1) есть почти аббревиатура count(*) (на самом деле, функцию count можно использовать и с названием колонки в качестве аргумента; в этом случае вычисляется количество записей, в которых соответствующая ячейка непуста). Единственная существенная разница между sum(1) и count(*) состоит в том, что sum на пустом наборе записей даёт значение NULL, а count — ноль.

Удалить запись из таблицы foobar можно командой

DELETE FROM foobar WHERE условие;

Заметим, что наличие уникальных идентификаторов в таблице очень сильно упрощает удаление конкретных записей.

Изменить запись можно командой UPDATE. Она обычно используется как-то так:

UPDATE foobar SET foo=1, bar=3 WHERE id=5;

Естественно, в WHERE допустимо любое условие.

Более сложные запросы

Как внутри FROM, так и внутри WHERE допускаются подзапросы.

Внутри FROM такой подзапрос трактуется естественным образом — как таблица, состоящая из результатов такого запроса. Часто такие подзапросы отделяют при помощи конструкции WITH:

-- следующие выражения эквивалентны:
SELECT ... FROM (SELECT ... FROM ...);
--              /  /  /  /  /  /  /
--             /  /  /  /  /  /  /
--            /  /  /  /  /  /  /
--           /  /  /  /  /  /  /
--          /  /  /  /  /  /  /
WITH a AS (SELECT ... FROM ...)
SELECT ... FROM a;

Внутри WHERE чаще всего подзапросы встречаются в виде

foo = (SELECT sum(...) FROM ...)
foo IN (SELECT bar FROM ...)

В случае бинарных операторов «равно», «больше», «меньше», IS и т.п. подзапрос должен возвращать одну запись. Для оператора IN подзапрос должен возвращать одну колонку. В этом случае IN проверяет принадлежность значения результату подзапроса. (Также IN допускает правым аргументом список значений наподобие foo IN (1,2,3), а также — имена таблиц.)

Проверить подзапрос на пустоту можно одним из как минимум двух способов:

(SELECT count(*) FROM ...) > 0
-- или же --
EXISTS (SELECT foo FROM ...)

Первый из них более гибок, но одновременно и более громоздок.

Теперь полезные приёмы, не касающиеся подзапросов.

Если требуется проверить значение на пустоту, нужно пользоваться выражением IS NULL, а не = NULL, как может показаться на первый взгляд.

Если требуется упорядочить результаты, можно воспользоваться модификаторами ORDER BY foo или ORDER BY foo DESC.

Если требуется ограничить количество результатов n записями, можно воспользоваться модификатором LIMIT n.

Если требуется для каждого достижимого значения некоторого выражения выдать ровно один результат с таким значением, можно воспользоваться модификатором GROUP BY выражение. Например,

SELECT foo,bar FROM baz GROUP BY bar;

для таблицы

1|2
3|2
2|3

выдаст (в зависимости от фазы луны) одно из двух: либо (1,2) и (2,3), либо (3,2) и (2,3).

Ещё модификатор GROUP BY выражение можно применять для агрегатных запросов. Для каждого достижимого значения выражения выдаётся ровно один результат, в котором агрегатные функции считаются только по записям с одним и тем же значением выражения.

Упражнения

Все упражнения следует выполнять в предположении следующей схемы БД:

CREATE TABLE people (id INTEGER PRIMARY KEY, name);
CREATE TABLE ages   (id INTEGER PRIMARY KEY, people_id, age);
CREATE TABLE parents(id INTEGER PRIMARY KEY, parent_id, child_id);

1. Составьте запрос, который выдаёт имена всех людей, у которых есть хотя бы два ребёнка.

2. Составьте запрос, который выдаёт имена детей всех людей, у которых есть хотя бы два ребёнка. Один и тот же человек не должен находиться в выдаче более одного раза!

3. Составьте запрос, который выдаёт имена людей вместе с количеством внуков у каждого.

4. Составьте запрос, который выдаёт имена и возраста всех людей, являющихся внуками тех, у кого более двух детей.

Ещё несколько упражнений

Начнём с упражнений, приведённых в конце прошлого раздела.

Решения упражнений прошлого раздела

1. Составьте запрос, который выдаёт имена всех людей, у которых есть хотя бы два ребёнка.

Приведём здесь два разных решения. Первое основано на вложенном подзапросе, считающем количество детей:

SELECT name FROM people WHERE 
    (SELECT count(*) FROM parents WHERE parent_id = people.id) >= 2;

Второе решение моделирует ситуацию «есть хотя бы два ребёнка» как двухрёберный подграф графа родственных отношений:

SELECT name FROM
    people,
    parents AS a,
    parents AS b
WHERE
    people.id = a.parent_id AND
    people.id = b.parent_id AND
    a.child_id != b.parent_id
GROUP BY people.id;

2. Составьте запрос, который выдаёт имена детей всех людей, у которых есть хотя бы два ребёнка. Один и тот же человек не должен находиться в выдаче более одного раза!

Приведём пять вариантов решения: сильновложенный, плоский и три промежуточных.

Сильновложенное решение вида «найдём людей, у которых есть хотя бы один родитель, у которого есть хотя бы два ребёнка» :

SELECT name FROM people WHERE
    (SELECT count(*) FROM parents AS p1 WHERE
        p1.child_id  = people.id AND
        (SELECT count(*) FROM parents AS p2 WHERE 
            p2.parent_id = p1.parent_id) >= 2) > 0;

Плоский вариант получается простой манипуляцией со вторым решением прошлого упражнения:

SELECT name FROM
    people,
    parents AS a,
    parents AS b
WHERE
    b.parent_id = a.parent_id AND
    people.id   = b.child_id  AND
    a.child_id != b.parent_id
GROUP BY people.id;

Первый промежуточный вариант состоит в том, чтобы найти тех, кто находится среди детей тех родителей, у которых хотя бы два ребёнка:

SELECT name FROM people WHERE
    people.id IN (SELECT p1.child_id FROM parents AS p1 WHERE
        (SELECT count(*) FROM parents AS p2 WHERE 
            p1.parent_id = p2.parent_id) >= 2);

Второй является выражением той же самой идеологии при помощи GROUP BY:

SELECT name FROM 
    people, 
    (SELECT p1.child_id AS result_id FROM parents as p1 
    WHERE
        (SELECT count(*) FROM parents AS p2 WHERE
            p1.parent_id = p2.parent_id) >= 2
    GROUP BY p1.child_id) 
WHERE people.id = result_id;

Наконец, третий промежуточный вариант, самый простой из всех:

SELECT name FROM
    people,
    parents AS p1
WHERE
    people.id = p1.child_id AND
    (SELECT count(*) FROM parents AS p2 WHERE p2.parent_id = p1.parent_id) >= 2
GROUP BY people.id;

3. Составьте запрос, который выдаёт имена людей вместе с количеством внуков у каждого.

Здесь приведём только решение в виде плоского запроса (вообще говоря, при работе с базами данных плоские запросы являются более предпочтительными при отсутствии существенно более простых неплоских альтернатив).

SELECT name, count(*) FROM
    people,
    parents AS a,
    parents AS b
WHERE
    people.id  = a.parent_id AND
    a.child_id = b.parent_id
GROUP BY people.id;

Отметим, что этот запрос работает только при отсутствии ситуаций вида «некий человек является родителем двух родителей одного и того же человека». При наличии таких ситуаций запрос можно модифицировать следующим образом:

SELECT name, count() FROM
    people,
    (SELECT a.parent_id AS result_id FROM parents AS a, parents AS b 
    WHERE a.child_id = b.parent_id GROUP BY a.parent_id, b.child_id)
WHERE people.id = result_id
GROUP BY people.id;

4. Составьте запрос, который выдаёт имена и возраста всех людей, являющихся внуками тех, у кого более двух детей.

Этот запрос собирается из решений предыдущих задач.

SELECT name, age FROM
    people,
    ages,
    parents AS a,
    parents AS b
WHERE
    people.id   = people_id  AND
    people.id   = a.child_id AND
    a.parent_id = b.child_id AND
    (SELECT count(*) FROM parents AS c WHERE c.parent_id = b.parent_id) > 2
GROUP BY people.id;

Несколько новых упражнений

1. Количество людей, у которых хотя бы 3 родителя.
2. Количество внуков Ивана.
3. Количество людей, у которых есть родитель старше 30 лет.
4. Количество братьев/сестёр Ивана.
5. Имена племянников Ивана.
6. Имена и возраста детей родителей Ивана.
7. Количество разных возрастов детей Ивана.

Программирование

Краткая справка по Python

Этот документ — именно краткая справка. За подробностями лучше обращаться к официальной документации.

Общая структура программы

Программа на языке Python представляет собой последовательность команд: каждая команда — на отдельной строчке (допускается также разделять команды точкой-с-запятой).

Самые частовстречающиеся команды:

• вычислить значение формулы (оформляется этой самой формулой)
• изменить что-нибудь (оформляется знаком =, справа от которого стоит формула, а слева — то, что нужно изменить)
• ветвление (оформляется при помощи слов if, elif, else)
• цикл (оформляется при помощи слов for или while)
• определение подпрограмм (оформляется при помощи слова def)
• использование внешнего модуля (оформляется при помощи слова import)

Также в программе могут встречаться комментарии, начинающиеся знаком # и длящиеся до конца строчки.

Синтаксис формул

Формулы — отдельная грамматическая категория. Команды внутри формул не встречаются, а вот формулы являются частью почти всех команд!

Формулы составляются из литералов, переменных и операторов.

Переменные

С точки зрения грамматики переменная — одно слово, не совпадающее ни с одним из небольшого набора зарезервированных (таких как if, else и т.п.). В слове допускаются буквы, нижние подчёркивания, цифры (но цифра не может стоять в начале слова).

Значением переменной является объект, к которому она привязана в данный момент. Изменить привязку можно командой изменения:

переменная = формула

которая сначала вычисляет значение формулы, а потом привязывает указанную переменную к этому значению.

Допускается множественное изменение (в нём может участвовать и больше двух переменных):

переменная1, переменная2 = формула1, формула2

Операторы

Оператор применяется к одной или нескольким формулам, называемым операндами этого оператора. Количество таких формул называется арностью этого оператора.

Среди операторов наиболее часто встречаются:

• вызов функции XXX(YYY)
• доступ к атрибуту XXX.YYY
• индексация коллекции XXX[YYY]
• проверка на вхождение XXX in YYY
• сумма XXX + YYY, разность XXX - YYY, произведение XXX * YYY
• частное XXX / YYY, неполное частное XXX // YYY, остаток XXX % YYY
• унарный минус -XXX
• степень XXX ** YYY
• эквивалентность XXX == YYY, неэквивалентность XXX != YYY
• строгие неравенства XXX < YYY и XXX > YYY
• нестрогие неравенства XXX <= YYY и XXX >= YYY
• логические операции: не not XXX, и XXX and YYY, или XXX or YYY
• поразрядные/поэлементные операции: и XXX & YYY, или XXX | YYY, сумма XXX ^ YYY

Литералы

Литералами называются специальные обозначения для некоторых объектов. Можно считать их операторами с уникальным (для каждого из них) синтаксисом.

Стандарт языка Python к литералам относит обозначения для текстовых и числовых литералов. По факту обозначения для некоторых коллекций и функций тоже зачастую относят к литералам (стандарт языка относит их к операторам).

Наиболее часто встречаются:

• числа 123, 12.3, 1.23e1, 2+3j и тому подобное
• тексты 'foo' или "foo" (одинарные и двойные кавычки не различаются)
• функции lambda x,y: x + 2*y
• списки (массивы) [1,2,3]
• кортежи (неизменяемые массивы) (1,2,3)
• множества {1,2,3}
• словари (ассоциативные массивы) {"foo": 1, 3: "bar", 5+1: 3+1}

Семантика формул

Арифметика

Всё более-менее стандартно по модулю одной особенности: неполное частное — результат округления соответствующей дроби вниз, а не к нулю (как принято в большинстве языков программирования). При этом всегда выполняется

a == (a // b) * b + (a % b)

Логика

В качестве основных логических значений используются «истина» True и «ложь» False. К ним можно применять конъюнкцию (& или and), дизъюнкцию (| или or), сложение ^ и отрицание not.

Отдельно выделим and и or: они вычисляют свой правый операнд только если левый истинный (для and) и ложный (для or). Ложными считаются None, False, всевозможные нули и всевозможные пустые контейнеры.

Остальные объекты встроенных типов считаются истинными.

Функции

Скоро появится

Списки

Список работает как набор «безымянных переменных», называемых его элементами. Элементы нумеруются последовательными натуральными числами (начиная с нуля).

Элемент списка можно получить при помощи формулы список[номер], где список — формула, значением которой является интересующий нас список, а номер — формула, значением которой является интересующий нас номер элемента.

Узнать количество элементов списка можно функцией len.

Изменить элемент списка можно командой изменения. Например:

foo[3] = 5  ## привязать третий элемент к пятёрке

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

foo = [1,2,3,4,5]
bar = foo         # bar привязана к тому же списку, что и foo
bar[0] = 5        # теперь и foo[0] == 5
baz = [1,2,3,4,5] # а это -- уже совсем другой список
bar[1] = baz[1]   # первый элемент списка bar теперь привязан к 
                  # значению формулы baz[1], то есть числу 2 
                  # (но не к первому элементу списка baz!)

Чтобы скопировать часть списка (то есть создать новый список с теми же привязками), можно воспользоваться срезом:

foo = [1, [2, 3], 4]
bar = foo[1:3] # копируем элементы списка с 1-го (включая) по 3-й (исключая)
bar[1] = 5     # foo[2] по-прежнему 4
bar[0][0] = 5  # теперь и foo[1][0] == 5: срез делает "неглубокую" копию

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

Также допускаются срезы с тремя индексами (подробности — в документации).

Добавить новые элементы к списку можно при помощи метода (атрибута-подпрограммы) append: foo.append(123) добавляет в конец списка foo элемент, привязанный к числу 123.

Кортежи

Кортежи отличаются от списков только тем, что их структуру (длину и привязки элементов) нельзя изменять. Тем не менее, никто не мешает на основе список и кортежей делать, например, «списки постоянной длины»:

foo = ([1], [2], [3])
foo[1][0] = 5  # теперь foo == ([1], [5], [3])

# можно даже спрятать соответствующие формулы с [0] за функциями
def get_elem(a, i): return a[i][0]
def set_elem(a, i, v): a[i][0] = v
# теперь, не зная о внутренней структуре "списков постоянной длины", их
# "элементы" невозможно (зло)намеренно удлинить

Множества

Скоро появится

Словари

Скоро появится

Семантика команд

Скоро появится

Несколько рекомендаций

Об особенностях языка Python

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

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

Структура программы

В начале программы идут импорты разнообразных модулей.

Не рекомендуется захламлять пространство имён импортами вида

from foobar import *

или даже

from foobar import foo, bar

Если не нравится слишком длинное имя модуля, то гораздо лучше этот модуль переименовать, чем импортировать его функции без префикса:

import sqlite3 as db

Программу рекомендуется составлять из определений констант и функций, придерживаясь следующих пунктов:

• следует выбрать единую схему именования сущностей и её придерживаться; например, принято имена глобальных переменных писать исключительно заглавными буквами, а имена функций — змеиным регистром (do_such_and_such)
• не следует пользоваться возможностью изменения привязок глобально объявленных переменных; про конструкции global и nonlocal лучше вообще забыть
• привязывать мутабельные объекты к глобальным переменным тоже следует с большой осторожностью
• желательно вне определений функций не иметь никакого кода, кроме, возможно, единственного вызова функции, которая служит точкой входа в программу

Функции

Разбиение программы на функции с чётко очерченными задачами и регламентом использования позволяет обратить длинную последовательность команд (которой, собственно, программа на Python и является) в гораздо более легко воспринимаемую форму. Сравните, например, такую реализацию сортировки «пузырьком»:

n = int(input())

to_sort = []

i = 0
while i < n:
    to_sort.append(int(input()))
    i += 1

i = 0
while i < n:
    j = 0
    while j < n-1:
        if to_sort[j+1] < to_sort[j]:
            to_sort[j], to_sort[j+1] = to_sort[j+1], to_sort[j]
        j += 1
    i += 1

i = 0
while i < n:
    print(to_sort[i], end=' ')
    i += 1

print()

с такой:

def main():
    to_sort = read_array()
    bubble_sort(to_sort)
    print_array(to_sort)
    
def read_array():
    n = read_int()
    return [read_int() for i in range(n)]

def read_int():
    return int(input())

def bubble_sort(array):
    n = len(array)
    for i in range(n): bubble_step(array)
    
def bubble_step(array):
    n = len(array)
    for j in range(n-1):
        if array[j+1] < array[j]: swap(array, j, j+1)

def swap(a, i, j): a[i], a[j] = a[j], a[i]

def print_array(a):
    n = len(a)
    for i in range(n): print(a[i], end = ' ')
    print_newline()
    
def print_newline(): print()

main()

Обратите внимание, что код, разбитый на функции, оказался длиннее, чем не разбитый. Но вот убедиться в том, что он правильно работает, гораздо легче: каждую функцию можно протестировать по отдельности, а сами определения функций читать не труднее, чем текст на естественном языке, описывающий работу алгоритма.

Выделять код в отдельную функцию рекомендуется как минимум в следующих случаях:

• функция стала слишком длинной: даже 30-40 строк — это уже очень много; в таком случае её код нужно представить в виде нескольких вызовов вспомогательных функций
• код слишком сильно уехал вправо (например, из-за условия внутри условия или цикла внутри цикла); вообще длинные строчки или же вложенные управляющие конструкции очень трудно читать и понимать их назначение
• в нескольких местах появись похожие друг на друга участки кода: их следует обобщить, приведя к одинаковому виду, и представить в виде вызовов одной и той же функции
• полезно писать функции-тесты, содержащие примеры использования других функций и ожидаемые от них результаты; функции-тесты являются одновременно комментарием к функции и некоторой гарантией того, что изменение реализации функции не приведёт к неожиданным изменениям её поведения

Комментарии

При комментировании программы важно помнить, что почти всегда правильный выбор имён и/или удачная функция-тест гораздо полезнее комментария на естественном языке, который:

• имеет тенденцию устаревать, не успевая за изменениями кода
• из-за особенностей естественных языков может иметь множество разнообразных интерпретаций

Ни в коем случае не нужно делать комментарии в духе:

a += 3  ## прибавляем тройку

А вот пример более удачного комментария:

x1 = average(distribution, segment) + 3  ## прибавляем тройку ...
x2 = approximate('quadratic', foobar, x1)
x3 = adjust(y, x1, x2)
## ... поскольку в статье [Х. Суньвчай, И. Выньсухим, 1994] так опредён 
## первый шаг аппроксимационного алгоритма

или

foobar(a+3)  ## прибавляем тройку для большей надёжности

Говоря другими словами, комментарий должен отвечать не на вопрос «Что тут происходит?» (на этот вопрос отвечает сам код), а на вопрос «Зачем так происходит?»

Электронные таблицы

Основы

Введение

Электронные вычислительные таблицы (англ. spreadsheet) — программы, основной задачей которых является организация, обработка и хранение данных в табличной форме. Первые электронные таблицы появились на рубеже 70х и 80х годов. Система Lotus 1-2-3, появившаяся в начале 1983 года, уже имела более-менее всю существенную функциональность современных электронных таблиц.

В настоящее время наиболее широко распространены три системы электронных таблиц: Microsoft Excel, LibreOffice Calc и Google Spreadsheets. Они достаточно сильно совместимы между собой (хотя для сложных документов периодически возникают проблемы).

Все примеры в этом документе приведены для LibreOffice Calc, но также (возможно, с небольшими изменениями) совместимы и с остальными системами электронных таблиц.

Структура таблицы

Таблица состоит из ячеек. У каждой ячейки есть две координаты: столбец задаётся буквами, строка — цифрами. Левая верхняя клетка обозначается A1.

В любую ячейку можно что-нибудь вписать. Конкретная интерпретация вписанного зависит от формата ячейки. Формат ячейки можно поменять при помощи соответствующей компоненты интерфейса.

Если содержимое ячейки начинается со знака =, остальная часть содержимого интерпретируется как формула. В языке формул допускается как минимум следующее:

• числовые литералы
• текстовые литералы (выделяются двойными кавычками; двойная кавычка экранируется собой же)
• ссылки на ячейки
• диапазоны (прямоугольники) — две ссылки, разделённые двоеточием
• аппликации функций вида FOO(a;b;c)

Абсолютный и относительный режимы адресации

Сразу отметим, что термины абсолютный режим адресации и относительный режим адресации, вообще говоря, не корректны по отношению к современным системам электронных таблиц. Они появлилсь в системе VisiCalc образца 1979 года, где имели вполне конкретный смысл, но уже в системе Lotus 1-2-3 потеряли свою актуальность. Закрепились они по какой-то случайной причине.

Если воспользоваться действием «скопировать и вставить» по отношению к некоторой ячейке, содержащей формулу, то все ссылки в этой формуле изменятся следующим образом:

• если ни одна из компонент ссылки не помечена знаком $ (такая ссылка называется относительной), к ссылке прибавляется вектор сдвига ячейки назначения относительно исходной ячейки

• если обе компоненты ссылки помечены спереди знаком $ (например, так: $A$1; такая ссылка называется абсолютной), то ссылка не менятеся

• если только одна компонента ссылки помечена знаком $ (например, так: $A1 или A$1; такая ссылка называется смешанной), то к непомеченной компоненте прибавляется проекция на эту компоненту вектора сдвига ячейки

Очень важно помнить, что при использовании действия «вырезать и вставить» происходит совсем другое. А именно: сама формула не меняется, а вот те формулы, которые ссылались на исходную ячейку, меняются. По этой причине вырезать формулы настоятельно не рекомендуется: эффект от такого вырезания труднопредсказуем, а последствия могут быть поначалу незаметны, но через некоторое время почти наверняка приведут к огромным неприятностям!

Таблица умножения и треугольник Паскаля

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

Таблица умножения делается так:

• в ячейку A1 ставится 0
• в ячейки A2 и B1 ставится формула =A1+1
• формула из ячейки A2 копируется в нужное количество ячеек первого столбца
• формула из ячейки B1 копируется в нужное количество ячеек первой строчки
• в ячейку B2 записывается формула =$A2*B$1, которая затем копируется во всю внутреннюю часть таблицы

Треугольник Паскаля делается так:

• в ячейку A1 ставится 1, которая копируется в нужное количество ячеек первой строчки и первого столбца
• в ячейку B2 записывается формула =A2+B1, которая копируется во всю внутреннюю часть таблицы

Использование функций

Тривиальные функции типа SUM, COUNT, COUNTA и т.п. мы не будем рассматривать сколько-нибудь подробно (вам почти наверняка их демонстрировали в 7 классе).

Отметим, что слить два текста можно оператором & или функцией CONCATENATE (в русском варианте — СЦЕПИТЬ).

Получить случайное число можно функциями RANDBETWEEN (для целых числе) и RAND (для дробных). В русском варианте они называются СЛУЧМЕЖДУ и СЛЧИС.

Преобразовать пару чисел в ссылку напрямую можно функцией OFFSET (СМЕЩ в русской версии), прибавляющей к указанной ссылке указанный вектор.

Найти указанное значение в прямоугольнике ширины или высоты 1 можно при помощи функции MATCH (ПОИСКПОЗ). Обратите внимание, что для поиска по неупорядоченным данным нужно явно подать 0 на третий вход!

Приведём пример таблицы, получающей случайное значение из заданного массива:

• ячейки с A1 по A10 заполняются какими-нибудь данными
• в ячейку B1 записывается =OFFSET($A$1;RANDBETWEEN(0,9);0)

Если заменить 9 на COUNTA($A$1:$A$10)-1, то выбор будет осуществляться из множества произвольного размера, не превышающего 10 (главное, чтобы значения стояли подряд, начиная с ячейки A1).

Этот же метод легко обобщается на множества большего размера.

Случайная последовательность заданной длины

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

• в ячейки с A1 по A10 записываются произвольные буквы/слова
• в ячейку B1 записывается =COUNTA($A$1:$A$10)-1
• в ячейку C2 записывается =OFFSET($A$1;RANDBETWEEN(0,$B$1);0)
• формула из ячейки C2 копируется в ячейки с C2 по C100
• в ячейку D2 записывается =C2&D1, затем эта ячейка копируется
• диапазон с D2 по D100
• в ячейку B2 записывается произвольное число от 1 до 100
• в ячейку B3 записывается =OFFSET($D$1;$B$2;0)

Условное выражение

Электронные таблицы поддерживают условное выражение IF(C;A;B) (ЕСЛИ(C;A;B)). Оно работает стандартным образом: его значение равно A, если C истинно, и B — в противном случае. Сложные условия можно составлять при помощи функций AND, OR, NOT (И, ИЛИ, НЕ).

Наиболее стандартный способ подсчёта количества строчек, удовлетворяющих условию, — сделать столбец с формулой вида IF(условие;1;0) и просуммировать его. Можно (но не особо рекомендуется по причине неочевидного синтаксиса лямбда-выражений) воспользоваться функцией COUNTIF.

Аналогичным образом можно производить выборку данных, удовлетворяющих условию, для дальнейшей обработки: IF(условие;ссылка;"") (пустой текст игнорируется большинством агрегатных функций типа SUM, MAX, MIN и прочих).

Поиск и смещение

В этом разделе мы поговорим подробнее про пару функций MATCH и OFFSET (ПОИСКПОЗ и СМЕЩ в русском варианте).

Введение

Функция MATCH ищет указанное значение в указанном одномерном диапазоне. У неё три входа: искомое значение, диапазон, вид поиска. На выходе — порядковый номер найденного значения (нумерация начинается с единицы).

Поговорим подробнее про вид поиска: он бывает бинарным (значения входа -1 и 1) и линейным (значение входа 0). Бинарный поиск быстрее, но предполагает упорядоченность массива данных (для 1 — в порядке возрастания, для -1 — в порядке убывания).

Основной подвох: по умолчанию вид поиска равен 1 (бинарный по возрастающему массиву данных), а в реальности чаще требуется поиск по неупорядоченным данным. Поэтому важно следить за тем, чтобы третий вход был равен 0, если только данные не упорядочены.

Функция OFFSET позволяет по ссылке и вектору смещения получить ссылку, смещённую относительно входной на указанный вектор. Её входы: смещаемая ссылка, вертикальное смещение (сверху вниз), горизонтальное смещение (слева направо).

С этой функцией связано два подвоха:

1. Нетрадиционный порядок координат вектора смещения. Более того, он даже не соответствует порядку координат в стандартном синтаксисе для ссылок. То есть на первый взгляд кажется, что OFFSET(A1,2,4) — это C5, но на самом деле OFFSET(A1,2,4) — это E3.
2. Нумерация «с единицы» у функции MATCH, которая очень часто используется в паре с OFFSET. В итоге, чтобы получить найденную ячейку, приходится дописывать минус единицу: OFFSET($A$1; MATCH($G$42;$A$1:$A$1000;0)-1; 0)

Стандартные ситуации применения

Наиболее стандартная (и почти единственная) ситуация применения пары MATCH и OFFSET — ассоциативный массив. С точки зрения электронных таблиц ассоциативный массив — это два столбца (или две строчки). В одной — ключи, в другой — значения.

Запрос к такому массиву — это ответ на вопрос «какое значение находится напротив указанного ключа?»

В предположении, что ключи находятся в столбце A, значения — в столбце B, а запрашиваемый ключ — в ячейке C1, сам запрос полностью выглядит как

=OFFSET($B$1; MATCH($C$1;$A$1:$A$1000;0)-1; 0)

Зачастую в реальных таблицах однородные данные оказываются разнесены сразу на несколько ассоциативных массивов. В таком случае рекомендуется следующая схема организации вычислений:

1. Каждый из массивов обработать по отдельности.
2. Результаты обработки выстроить друг за другом.
3. Предположим, для определённости, что было 10 массивов и результаты запросов к ним оказались в диапазоне P1:P10.
4. В ячейку Q1 пишем формулу =P1.
5. В ячейку Q2 пишем формулу =IFERROR(Q1;P2).
6. Копируем ячейку Q2 во все остальные ячейки диапазона Q2:Q10.

В итоге в ячейке Q10 окажется ответ на запрос ко всему множеству данных.

Примитивная реализация

Наконец, покажем, как можно реализовать MATCH и OFFSET (по модулю обработки ошибок) в терминах примитивного IF.

Сначала MATCH. Допустим, что нам нужно найти значение ячейки H1 в диапазоне A1:A1000. Для этого можно выполнить следующие действия:

1. Поместить в ячейку B1 число 1 (порядковый номер первого значения).
2. Поместить в ячейку B2 формулу =B1+1 и скопировать её на весь диапазон B2:B1000. Теперь в этом диапазоне порядковые номера соответствующих значений.
3. Поместить в ячейку C1 формулу =IF(A1=$H$1; B1; NA()).
4. Поместить в ячейку C2 формулу =IF(A2=$H$1; B2; C1). Скопировать эту формулу на весь диапазон C2:C1000.
5. В клетке C1000 находится ответ.

Это — аналог запроса =MATCH($H$1; $A$1:$A$1000; 0). Бинарный поиск оставляем в качестве (необязательного и весьма трудного) упражнения.

Теперь реализуем аналог запроса =OFFSET($A$1;$H$1;0) (вариант с двумя ненулевыми координатами можно реализовать как два последовательных сдвига, в каждом из которых одна из координат нулевая). Достаточно выполнить следующее:

1. Поместить в ячейку B1 число 0 (смещение первого значения).
2. Поместить в ячейку B2 формулу =B1+1 и скопировать её на весь диапазон B2:B1000. Теперь в этом диапазоне смещения соответствующих значений.
3. Поместить в ячейку C1 формулу =IF(B1=$H$1; A1; NA()).
4. Поместить в ячейку C2 формулу =IF(B2=$H$1; A2; C1). Скопировать эту формулу на весь диапазон C2:C1000.
5. В клетке C1000 находится ответ.

Как можно заметить, примитивные реализации MATCH и OFFSET очень похожи друг на друга. Это и не удивительно: первая восстанавливает порядковый номер по значению, а вторая — значение по порядковому номеру. Другое дело, что реальная функция OFFSET работает гораздо эффективнее примитивной реализации (а вот MATCH имеет ровно ту же асимптотическую вычислительную сложность, что и примитивная реализация).