Уроки 9М 2017/2018 года

Здесь выкладываются материалы уроков 9М класса.

Питон, курс молодого бойца

В этой главе находится краткое введение в некоторые аспекты языка Python.

Глава пока находится в разработке!

Общие положения

Об особенностях языка 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)  ## прибавляем тройку для большей надёжности

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

Алгебра логики

Основные операции

Общепринятым для цифровой электроники стандартом является использование двух элементарных сигналов: условно \(0\) и \(1\). В связи с этим наиболее простой моделью такой электроники является отображение \(\mathbf{2}^m\to \mathbf{2}^n\), имеющее, грубо говоря, \(m\) двоичных входов и \(n\) двоичных выходов (символом \(\mathbf{2}\) здесь обозначено множество \({0,1}\)).

Отображения \(\mathbf{2}^n\to \mathbf{2}\) мы будем называть логическими операциями арности \(n\) или \(n\)-арными операциями. Элементарные величины \(0\) и \(1\) можно считать операциями арности \(0\). Всего \(n\)-арных операций, как нетрудно вычислить, \(2^{2^n}\). В частности, есть четыре унарных операции и шестнадцать бинарных. Наиболее интересны следующие:

Отрицание: \(\lnot 0 = 1\) и \(\lnot 1 = 0\).

Альтернативные обозначения: \(\lnot x = \overline{x} = \,!x\).

Конъюнкция: \(x\land y = 1\) тогда и только тогда, когда \(x=1\) и \(y=1\).

Альтернативные обозначения: \(x\land y = x\cdot y = x\times y = xy = x \& y\).

Дизъюнкция: \(x\lor y = 1\) тогда и только тогда, когда хотя бы кто-то из \(x\) или \(y\) равен \(1\).

Альтернативные обозначения: \(x\lor y = x\,|\,y = x+y\).

Сложение (или XOR от eXclusive OR): \(x\oplus y = (x+y)\bmod 2\).

Альтернативные обозначения: \(x\oplus y = x+y\).

Импликация: \(x\Rightarrow y = \overline{x} \lor y\).

Штрих Шеффера (или NAND от Not AND): \(x\,|\,y = \lnot(xy)\).

Стрелка Пирса (или NOR от Not OR): \(x\downarrow y = \lnot(x\lor y)\).

Как можно заметить, некоторые обозначения используются сразу для нескольких операций. Поэтому мы остановимся на некоторой единой системе обозначений: \(\lnot x\) и \(\overline{x}\) — для отрицания, \(xy\) и \(x\land y\) — для конъюнкции, \(x\lor y\) — для дизъюнкции, \(x + y\) — для сложения.

Алгебраические свойства

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

Законы де Моргана: \(\overline{x\land y} = \overline{x}\lor\overline{y}\) и \(\overline{x\lor y} = \overline{x}\land\overline{y}\).

Снятие двойного отрицания: \(\lnot\lnot x = x\).

Третьего не дано: \(x\lor\overline{x} = 1\).

Коммутативность: \(xy=yx\) (выполняется также для \(\lor\) и \(+\)).

Ассоциативность: \(x(yz)=x(yz)\) (выполняется также для \(\lor\) и \(+\)).

Дистрибутивность: \(x(y+z)=xy+xz\) (выполняется также для \(\lor,\land\) и \(\land,\lor\)).

Идемпотентность: если \(n\geqslant 1\), то \(x^n=x\).

СДНФ и многочлены Жегалкина

Рассмотрим следующую задачу: имея некий набор операций, научиться выражать произвольную операцию в виде комбинации имеющихся. Оказывается, для набора \(\land,\lor,\lnot\) эта задача решается особенно легко: если \(f(x) = 1\) только для \(x=(x_1,x_2,\ldots,x_n)=(a_1,a_2,\ldots,a_n)\), то

\[ f(x_1,x_2,\ldots,x_n)= (\lnot^{\lnot a_1} x_1)(\lnot^{\lnot a_2} x_2)\ldots (\lnot^{\lnot a_n} x_n) \]

В общем случае достаточно взять дизъюнкцию таких выражений для всех \(a\), для которых \(f(a)=1\).

Результатом такой манипуляции является штуковина (дизъюнкция конъюнкций), называемая совершенной дизъюнктивной нормальной формой (коротко СДНФ) операции \(f\). Например, импликация имеет СДНФ

\[ x\Rightarrow y = \overline{x}\,\overline{y}\lor \overline{x}y\lor xy \]

Нетрудно заметить, что СДНФ определена с точностью до перестановки конъюнктов внутри дизъюнктов и перестановки самих дизъюнктов.

С набором операций \(\land,+,1\) ситуация не сильно сложнее: интерполяционная формула Лагранжа для вершин \(n\)-мерного куба даёт выражение

\[ f(x) = \sum_a f(a) (x_1+\overline{a_1}) (x_2+\overline{a_2})\ldots (x_n+\overline{a_n}) \]

Верность равенства тривиально проверяется подстановкой \(a\) или же замечанием о том, что эта формула получена путём формальной замены в СДНФ дизъюнкции на сумму (поскольку для любого значения \(x\) не более чем один из дизъюнктов равен 1, сумма дизъюнктов СДНФ равна их дизъюнкции).

После раскрытия скобок и приведения подобных получается сумма одночленов, каждый из которых любую из переменных содержит в не более чем первой степени. Такая сумма называется многочленом Жегалкина функции \(f\). Различных одночленов \(2^n\), поэтому различных многочленов Жегалкина \(2^{2^n}\) — ровно столько же, сколько и \(n\)-арных операций. Поскольку любая операция имеет хотя бы один многочлен Жегалкина, то, согласно принципу Дирихле, любая операция имеет ровно один многочлен Жегалкина.

Например, импликация имеет многочлен Жегалкина

\[ x\Rightarrow y = (x+1)y+(x+1)(y+1)+xy = xy + x + 1 \]

Алгебры Гейтинга

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

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

Моделью интуиционистской логики или алгеброй Гейтинга называется множество \(X\), элементы \(0,1\in X\), операции \(\land,\lor,\Rightarrow: X^2\to X\) и бинарное отношение \(\rightarrow\) (называемое метаследствием) на множестве \(X\), удовлетворяющие следующим свойствам:

Рефлексивность: \(x\rightarrow x\) для всех \(x\).

Транзитивность: если \(x\rightarrow y\) и \(y\rightarrow z\), то \(x\rightarrow z\).

Строгость: если \(x\rightarrow y\) и \(y\rightarrow x\), то \(x=y\).

Начальный объект: \(0\rightarrow x\) для всех \(x\).

Конечный объект: \(x\rightarrow 1\) для всех \(x\).

Точная нижняя грань: \(z\rightarrow x\) и \(z\rightarrow y\) тогда и только тогда, когда \(z\rightarrow x\land y\).

Точная верхняя грань: \(x\rightarrow z\) и \(y\rightarrow z\) тогда и только тогда, когда \(x\lor y\rightarrow z\).

Сопряжение: \(x\land y\rightarrow z\) тогда и только тогда, когда \(x\rightarrow y\Rightarrow z\).

Простейшей нетривиальной алгеброй Гейтинга является рассмотренная выше двухзначная логика \(X={0,1}\), в которой \(0\to 0\), \(0\to 1\), \(1\to 1\) (а операции \(\land\), \(\lor\), \(\Rightarrow\) определены стандартно).

Для полноты картины приведём явным образом пример трёхзначной алгебры Гейтинга. На множестве \(X={0,\alpha,1}\) метаследствие определим так, что \(0\to \alpha\to 1\). В качестве операций \(\land\) и \(\lor\) возьмём бинарные минимум и максимум. С импликацией несколько сложнее: если \(x\to y\), то \(x\Rightarrow y = 1\). Три оставшихся случая определяются равенством \(x\Rightarrow y = y\).

Отрицание обычно определяют так: \(\lnot x = x\Rightarrow 0\) (чуть позже мы увидим, почему). Заметим, что \(\lnot\alpha = 0\), а \(\lnot 0 = 1\). Вывод: в нашей модели можно наблюдать невыполнение закона о снятии двойного отрицания. Ещё раз отметим, что все «незаконы» интуиционистской логики невозможно наблюдать даже в совокупности всех конечных моделей. Поэтому для установления свойств, присущих всем алгебрам Гейтинга, приходится общаться с аксиомами напрямую.

Несколько законов интуиционистской логики

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

Начнём с того, что поскольку \(x\land y\to x\land y\), то \(x\land y\to x\) и \(x\land y\to y\). Аналогично, для дизъюнкции \(x\to x\lor y\) и \(y\to x\lor y\).

Пусть \(z\to x\) и \(z\to x\Rightarrow y\). Поскольку всегда \(z\to z\), то \(z\to z\land x\). А из того, что \(z\to x\Rightarrow y\), следует \(z\land x\to y\). В итоге имеем цепочку \(z\to z\land x\to y\), откуда \(z\to y\). Возможность в рамках любых предположений (в нашем случае \(z\)) из истинности \(x\) и \(x\Rightarrow y\) заключать истинность \(y\) заметили ещё древние греки. А от римлян нам досталось название этого принципа — Modus Ponens (в переводе «способ вывода»).

В заключение покажем, что (внутреннее) следствие \(\Rightarrow\) по смыслу аналогично метаследствию \(\to\). Заметим сперва, что из \(x\to 1\) и \(x\to x\) следует \(x\to 1\land x\). В обратную сторону следствие мы доказали в начале этого раздела. Поэтому \(x=1\land x\). Но в таком случае \(x\to y\) имеет место тогда и только тогда, когда \(1\land x\to y\), что, в свою очередь, эквивалентно \(1\to x\Rightarrow y\).

Упражнения

1. Запишите явно дистрибутивность для пары операций \(\lor,\land\) и пары \(\land,\lor\).

2. Докажите все свойства, перечисленные во втором разделе, путём подстановки всевозможных значений переменных.

3. Функция голосования определяется так: \(\Gamma(x,y,z)=1\) тогда и только тогда, когда среди \(x,y,z\) есть хотя бы две единицы. Постройте СДНФ и многочлен Жеглакина для \(\Gamma\).

4. Докажите, что существует единственная трёхзначная алгебра Гейтинга.

5. Докажите, что отображение \(x\mapsto x\land y\) алгебры Гейтинга в себя является монотонным (из \(a\to b\) следует \(a\land y\to b\land y\)).

6. Договоримся запись \(a\land c\to b\land c\) сокращать до \(a\to_c b\). Докажите, что отношение \(\to_c\) удовлетворяет всем аксиомам интуиционистской логики, за исключением строгости, а кроме того, выполнено \(1\to_c c\).

7. Докажите, что в любой алегбре Гейтинга имеет место \(x\to \lnot\lnot x\). Указание: результат предыдущего упражнения позволяет, рассматривая стрелки вида \(\to_c\), где \(c=a_1\land a_2\land\ldots\land a_n\), вести рассуждения «в рамках предположений \(a_1\), \(a_2\), ..., \(a_n\)». Это позволяет, сперва предположив \(x\), воспользоваться стандартным приёмом «от противного», предположив \(\lnot x\) и получив каким-нибудь способом \(0\) в рамках сделанных предположений.

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

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

Операции с текстами

Разбор одной из задач

Задача состояла в том, чтобы реализовать функцию print_square(n), печатающую полый квадрат \(n\times n\).

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

Реализация 1

def print_square(n):
  line_a = '*' * n + '\n'
  line_b = '*' + ' ' * (n-2) + '*\n'
  
  if   n >= 2: print(line_a + line_b*(n-2) + line_a)
  elif n == 1: print('*')
  else:        print('')

Реализация 2

def print_square(n):
  for y in range(n):
    for x in range(n):
      print(pixel(n,x,y),end='')
    print()
    
def pixel(n,x,y):
  if x == 0 or x == n-1: return '*'
  if y == 0 or y == n-1: return '*'
  return ' '

Упражнения

1. Реализовать функцию print_squares(n,k), печатающую друг за другом k квадратов \(n\times n\). Пример работы для \(n=4\), \(k=4\):

**** **** **** ****
*  * *  * *  * *  *
*  * *  * *  * *  *
**** **** **** ****

2. Реализовать функцию print_diamond(n), печатающую «ромбик» с «диагональю» \((2n-1)\). Пример работы для \(n=3\):

  *
 * *
*   *
 * *
  *

3. Реализовать функцию print_diamonds(n,k), печатающую друг за другом \(k\) ромбиков. Пример работы для \(n=3\), \(k=4\):

  *     *     *     *
 * *   * *   * *   * *
*   * *   * *   * *   * 
 * *   * *   * *   * *
  *     *     *     *

4. Программа принимает на вход число \(N\), а затем — \(2^N\) строчек с \((N+1)\) целым числом каждая. Если соответствующие строчки можно интерпретировать как полную (присутствуют все возможные комбинации значений) таблицу булевой функции, программа должна печатать СДНФ так, как в примере. В противном случае программа должна печатать WRONG TABLE. Пример работы:}

2
0 0 1
1 1 1
0 1 1
1 0 0

X1X2 v x1x2 v X1x2

Знакомство со словарями

Ассоциативные структуры данных

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

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

• Названия переменных являются ключами к данным, с которыми эти переменные связаны.

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

• Номер элемента массива является ключом к этому элементу.

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

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

# литералы {k1: v1, k2: v2, ... kn: vn}, например
foo = {1: 2, "foo": 3, "bar": "baz"}

# запись
foo[2] = 4  
foo[1] = 3  # изменяет уже записанное значение
del foo[1]  # удаление элемента; выдаёт ошибку, если по указанному 
            # ключу ничего не хранится

# считывание
2 in foo  # == True, если в foo есть элемент по ключу 2
foo[2]    # сам элемент по ключу 2
foo[10]   # если по ключу не хранится элемент, python выдаст ошибку

x = ...
y = foo[x] if x in foo else 3  # безопасное считывание

# вспомогательные операции
len(foo)   # количество хранимых элементов
foo.keys() # последовательность ключей, хранимых в словаре

Пример программы, использующей словари

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

Вот решение, использующее словарь:

def add_word(d,w):
    if w in d: d[w] += 1
    else:      d[w]  = 1

def main():
    text = input()
    words = text.split()
    counts = {}

    for word in words: add_word(counts, word)

    for word in counts: print(word, '->', counts[word])
    
main()

Упражнения

1. Модифицируйте программу из примера так, чтобы она выводила слова в порядке убывания их количества. Указание: вам могут пригодиться функции sorted и reversed.

2. На вход подаётся строчка с целыми неотрицательными числами. Программа должна вывести минимальное целое неотрицательное число, которого нет в указанной строчке. Асимптотическая сложность алгоритма должна быть ниже квадратичной.

3. На вход подаётся строчка с целыми неотрицательными числами. Назовём \(N\) количество этих чисел. Для всех \(k\) от \(1\) до \(N\) программа должна вывести минимальное целое неотрицательное число, которого нет среди первых \(k\) чисел строчки. Асимптотическая сложность алгоритма по-прежнему должна быть ниже квадратичной.

Достаточно удобный способ моделирования всевозможных графов — словарь словарей. А именно, если из вершины x в вершину y идёт ребро с весом w, то его можно задать функцией

def add_edge(g,x,y,w):
    if x in g: g[x][y] = w
    else:      g[x] = {y:w}

Если разрешены множественные рёбра, то вместо одного веса можно хранить массив весов. Неориентированное ребро можно моделировать парой ориентированных.

4. Напишите программу, получающую в первой строчке числа \(N\) и \(X\), а затем, в каждой из следующих \(N\) строчек — пара чисел, описывающих начало и конец ребра ориентированного невзвешенного графа с кратными рёбрами. Множество вершин этого графа считать множеством целых неотрицательных чисел. Программа должна вычислять следующее:

   1. максимальную исходящую степень вершин
   2. максимальную кратность ребра
   3. наличие ориентированного пути между $0$ и $X$
   4. наличие ориентированного цикла, содержащего вершину $X$
   5. количество нетривиальных компонент связности
   6. количество рёбер после снятия ориентаций и кратностей
   7. остов после снятия ориентаций и кратностей

Пример входа и выхода:

8 3
0 1
0 1
1 0
1 2
2 0
3 4
3 3
3 5

3  # из тройки идёт три ребра
2  # из нуля в единицу идут два ребра
NO
YES  # петля в 3
2
6
0 1, 1 2, 3 4, 3 5

Задачи про графы

Здесь предложено несколько задач про обработку графов.

Договорённости

Граф хранится в словаре словарей таким образом, что если такой словарь связан с переменной graph, то graph[x][y] — это количество рёбер от вершины x до вершины y.

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

Вся дополнительная информация подаётся после графа.

Задания

1. Применить print к внутреннему представлению заданного графа.

Пример:

-- ВХОД --
5
0 1
1 0
0 1
5 6
7 6

-- ВЫХОД --
{0: {1: 2}, 1: {0: 1}, 5: {6: 1}, 7: {6: 1}}

2. Найти количество разных путей от вершины \(A\) до вершины \(B\). Эти вершины подаются в строчке после графа. Отсутствие ориентированных циклов гарантируется. Также разрешается применять рекурсию.

Пример:

-- ВХОД --
5
0 1
0 1
0 1
1 2
1 2
0 2

-- ВЫХОД --
6

3. Найти какой-нибудь путь от вершины \(A\) до вершины \(B\) методом поиска в глубину. В графе могут присутствовать ориентированные циклы. Рекурсию использовать запрещено. Если пути нет, нужно напечатать НЕТ ПУТИ.

Пример:

-- ВХОД --
3
1 2
0 1
2 3
1 3

-- ВЫХОД --
1 2 3

4. Найти нетривиальные (с более чем одной вершиной) связные компоненты графа. Каждую напечатать в виде возрастающей последовательности номеров её вершин.

Пример:

-- ВХОД --
5
3 2
2 1
1 0
5 6
7 6

-- ВЫХОД --
0 1 2 3
5 6 7

Решения

Задача 1

Определим сначала функцию для считывания графа в том формате, о котором мы договорились выше.

def read_graph_from_stdin():
    g = {}
    N = int(input())
    
    for i in range(N):
        a,b = map(int, input().split()) 
        if a not in g: g[a] = {}
        
        if b in g[a]: g[a][b] += 1
        else:         g[a][b]  = 1
    
    return g

В терминах этой функции решение первой задачи выглядит так:

def problem1():
    g = read_graph_from_stdin()
    print(g)

Задача 2

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

def problem2():
    g = read_graph_from_stdin()
    x,y = map(int, input().split())

    ## словарь, в который мы будем записывать количества путей
    path_count = {y: 1}  ## от вершины y до неё самой один путь
    
    ## функция, считающая количество путей от своего входа до y
    def traverse(v):
        if v in path_count: return path_count[v]
        if v not in g:      return 0

        s = sum(g[v][n] * traverse(n) for n in g[v])
        path_count[v] = s
        return s

    print(traverse(x))

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

def traverse(v):
    if v == y:     return 1
    if v not in g: return 0
    
    return sum(g[v][n] * traverse(n) for n in g[v])

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

Задача 3

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

def print_path(p): print(*p)

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

foo(1, *[2,3,4]) 

означает то же самое, что и

foo(1,2,3,4)

Вторая функция выдаёт последовательность соседей указанной вершины графа:

def neighbors(g, v):
    if v not in g: return []
    else:          return g[v].keys()

Эта функция избавляет от необходимости делать лишние проверки вида

if v not in g: ...

которые легко забыть.

Решение третьей задачи представляет собой классический поиск в глубину.

def problem3():
    g = read_graph_from_stdin()
    x,y = map(int, input().split())

    path    = [x]
    visited = set()
    while path:
        current_v = path[-1]
        visited.add(current_v)
        if current_v == y: break

        to_visit = [n for n in neighbors(g,current_v)
                      if  n not in visited]

        if to_visit: path.append(to_visit[0])
        else:        path.pop()
        
    if path: print_path(path)
    else:    print("НЕТ ПУТИ")

Задача 4

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

def edges(g):
    result = []
    for a in g:
        for b in g[a]:
            result.append((a,b))
            
    return result
    
def vertices(g):
    result = set()
    for a,b in edges(g):
        result.add(a)
        result.add(b)

    return result

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

def print_components(components):
    visited = set()
    for v in components:
        if v not in visited:
            print(*sorted(components[v]))
            visited |= components[v]

Осталось построить такое отображение компонент:

def problem4():
    g = read_graph_from_stdin()
    
    ## изначально "забываем" про все рёбра; 
    ## в таком случае компонента каждой вершины -- она сама
    components = dict((v,{v}) for v in vertices(g))

    ## теперь по очереди "вспоминаем" рёбра
    for a,b in edges(g):
        if b not in components[a]:
            ## объединяем компоненты обоих концов ...
            joint_component = (components[a] | components[b])
        
        ## ... и обновляем отображение компонент
        for x in joint_component:
            components[x] = joint_component

    print_components(components)

Обходы графов

Обход в глубину

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

path    = [start]
visited = set()
while path:
    current_place = path[-1]
    visited.add(current_place)
    if is_good(current_place): break
    
    to_visit = [n for n in neigbors(graph,current_place)
                  if  n not in visited]
    
    if to_visit: path.append(to_visit[0])
    else:        path.pop()

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

Фронтовой подход

Любую связную компоненту графа можно обойти следующим методом: на каждом шаге храним фронт — множество соседей тех вершин, в которых мы уже были. Если фронт непуст, забираем из него любую вершину, а вместо неё добавляем всех её непосещённых соседей. Этот алгоритм выражается так:

front   = make_front([start])
visited = set()
while not is_empty(front):
    vertex = take_from(front)
    if vertex in visited: continue
    visited.add(vertex)
    if is_good(vertex): break
    
    to_visit = [n for n in neighbors(graph,vertex)
                  if  n not in visited]
    
    extend(front,to_visit)

Порядок обхода определяется конкретными реализациями функций make_front, take_from, extend и is_empty. Например, для

def make_front(list): return list
def take_from(front): return front.pop()
def extend(front,xs): front.extend(xs)
def is_empty(front):  return len(front) == 0

получается обход в глубину.

Обход в ширину

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

Навиная реализация выглядит так:

def make_front(list): return list
def take_from(front): return front.pop(0)
def extend(front,xs): front.extend(xs)
def is_empty(front):  return len(front) == 0

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

Абстрактные типы данных

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

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

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

В заключение приведём полноценный пример абстрактного типа данных -- натуральные числа. Натуральные числа задаются одним конструктором

zero()

и двумя операциями

succ(n)
induct(base,transition)

Эти операции должны удовлетворять принципу Пеано-Ловера-Дедекинда: если a — элемент множества A, а функция f осуществляет отображение множества A в себя, то

induct(a,f)(zero())  == a
induct(a,f)(succ(n)) == f( induct(a,f)(n) )

причём для любой функции g, экстенсионально эквивалентной (то есть равной для всех допустимых значений аргумента) функции f, должны быть экстенсионально эквивалентны induct(a,f) и induct(a,g).

Один из способов реализации натуральных чисел таков:

def zero():  return 0
def succ(n): return n+1
def induct(b,t):
    def seq(n):
        if n == 0: return b
        return t(seq(n-1))
    return seq

Другой способ реализации таков:

def zero():  return []
def succ(n): return [n]
def induct(b,t):
    def seq(n):
        if not n: return b
        return t(seq(n[0]))
    return seq

А вот пример функции, работоспособность которой не зависит от того, какой из способов реализации выбран:

def to_int(n):
    return induct(0, lambda x: x+1)(n)

Подробнее про принцип индукции можно прочитать здесь.

Очередь

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

Циклическим массивом называется тройка \((s,x,y)\), где \(s\) — массив длины \(N\), а \(x,y\) — целые числа в пределах от \(0\) до \((s-1)\). Если \(x\leqslant y\), то рабочей частью циклического массива называется множество \({x,x+1,x+2,\ldots, y-1}\). Если \(x>y\), то рабочей частью называется множество \({x,x+1,x+2,\ldots,N-1,0,1,\ldots y-1}\).

Добавление единицы данных в циклический массив \((s,x,y)\) происходит так: в ячейку \(s[y]\) кладётся эта единица данных, затем \(y\) увеличивается на \(1\) по модулю \(N\).

Взятие единицы данных происходит из ячейки \(s[x]\). После взятия единицы данных число \(x\) увеличивается на \(1\) по модулю \(N\).

Задание

1. По словесному описанию, приведённому выше, реализуйте циклический массив в виде набора из пяти функций:

# создаёт пустую очередь
def make_queue(capacity):  
    return ([None]*capacity, 0, 0)

# вычисляет размер рабочей части
def queue_size(q):
    pass  # заполните самостоятельно

# определяет, можно ли ещё добавить элементы
def queue_is_full(q):
    return len(q[0]) == queue_size(q) + 1

# добавляет элемент в очередь
def queue_push(q,x):
    pass  # заполните самостоятельно

# забирает элемент из очереди
def queue_pop(q):
    pass  # заполните самостоятельно

2. Реализуйте обход в ширину при помощи очереди. А именно, в терминах функций из задачи 1 реализуйте функции make_front, take_from, extend и is_empty.

3. Очередь из пункта 1 обладает незначительной проблемой: одну из ячеек массива нельзя использовать для хранения данных (поймите, почему!). Модифицируйте определение так, чтобы была возможность использовать весь массив.

Циклические очереди

Две реализации очереди

Начнём с решения задания 1 из прошлого листка.

def make_queue(cap): return ([None]*cap,0,0)  

def queue_size(q):
    a,b,c = q
    return (c-b) % len(a)

def queue_is_full(q):
    return queue_size(q)+1 == len(q[0])

def queue_push(q,x):
    a,b,c = q
    a[c] = x
    c = (c+1) % len(a)
    return (a,b,c)

def queue_pop(q):
    a,b,c = q
    taken = a[b]
    b = (b+1) % len(a)
    return taken, (a,b,c)

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

q = queue_push(q, foo)
q,foo = queue_pop(q)

Недостатком такого представления очереди является смесь мутабельных (изменяемых) и иммутабельных (неизменяемых) типов данных. Более естественно (с точки зрения языка python) следующее представление:

def make_queue(cap): return [[None]*cap,0,0]

def queue_push(q,x):
    a,b,c = q
    a[c] = x
    q[2] = (c+1) % len(a)

def queue_pop(q):
    a,b,c = q
    taken = a[b]
    q[1] = (b+1) % len(a)
    return taken

Здесь добавление и удаление элемента происходит весьма стандартно:

queue_push(q,foo)
foo = queue_pop(q)

Задание

1. В терминах очереди первого типа реализуйте make_front, take_from, extend, is_empty так, чтобы нижеприведённая функция совершала обход графа в ширину.

def traverse(graph, is_good, start):
    front   = make_front([start])
    visited = set()
    while not is_empty(front):
        vertex = take_from(front)
        if vertex in visited: continue
        visited.add(vertex)
        if is_good(vertex): return vertex

        to_visit = [n for n in neighbors(graph,vertex)
                      if  n not in visited]

        extend(front,to_visit)

2. Сделайте то же самое в терминах очереди второго типа.

3. В терминах induct из предыдущего листка определите функцию iterate(f,n,x), для которой

iterate(f,n,x) = f(f(f(...f(x))))  # f применено n раз

При решении третьей задачи запрещается явно или неявно использовать встроенные в python числовые типы (int и float). Аргумент n здесь — натуральное число в смысле раздела про абстрактные типы данных.

Алгоритм Дейкстры

Далее пойдёт речь об алгоритме поиска расстояний между вершинами в графе. Он является обобщением фронтового алгоритма обхода. Единственное существенное отличие — вместо фронтового множества используется очередь с приоритетом.

Очередь с приоритетом

Очередь с приоритетом — абстрактный тип данных, эквивалентный следующему:

def make_pq(): return []

def pq_push(q,x,p): q.append((x,p))

def pq_pop(q): 
    priorities = [xp[1] for xp in q]
    min_index  = priorities.index(min(priorities))
    return q.pop(min_index)

def pq_is_empty(q): return len(q) == 0

Эффективную реализацию очереди с приоритетом отложим на потом, а сейчас приведём сам алгоритм Дейкстры.

Алгоритм Дейкстры

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

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

def traverse(graph, start):
    pq = make_pq(); pq_push(pq, start, 0)
    distances = {}
    while not pq_is_empty(pq):
        vertex, distance = pq_pop(pq)
        if vertex in distances: continue
        distances[vertex] = distance
        
        to_visit = [n for n in neighbors(graph,vertex)
                      if  n not in distances]
        
        for target in to_visit: 
            pq_push(pq, target, distance + graph[vertex][target])
            
    return distances

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

Введение

Электронные вычислительные таблицы (англ. 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 (для дробных).

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

Преобразовать пару чисел в ссылку напрямую можно функцией 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). Оно работает стандартным образом: его значение равно A, если C истинно, и B — в противном случае. Сложные условия можно составлять при помощи функций AND, OR, NOT.

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

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

Системы счисления

Введение

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

Основным определением будет следующее: позиционной системой счисления с основанием \(d\) (\(d\) — целое неотрицательное число, большее 1) называется множество \(D\) цифр и три отображения: \(v:D\to\mathbb{N}\), \(r:S\to\mathbb{N}\) и \(w:\mathbb{N}\to S\), в которых \(\mathbb{N}\) -- множество целых неотрицательных чисел, а \(S\) — множество непустых последовательностей элементов \(D\).

От указанных объектов требуются следующие свойства:

• \(|D|=d\)
• \(v(D)={x\in\mathbb{N} ,|, 0\leqslant x < d}\)
• \(r(w(x))=x\)
• \(r(a_n a_{n-1}\ldots a_1 a_0) = \sum_k d^k v(a_k)\)

Для них традиционны следующие названия: \(v\) — числовое значение цифры, \(w\) — \(d\)-ичная запись числа, \(r\) — число, соответствующее \(d\)-ичной записи. Мы будем далее называть \(w\) и \(r\) записью и считыванием соответственно.

Если одновременно рассматривается несколько систем счисления, то обычно их помечают нижним индексом. Например, \(r_3\circ w_2\) — композиция двоичной записи и троичного считывания. Переводом из системы счисления с основанием \(a\) в систему счисления с основанием \(b\) называют композицию \(w_b\circ r_a\).

Традиционно множество цифр состоит из знаков 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и букв латинского алфавита. Числовые значения «арабских» цифр стандартны. Числовые значения «латинских» цифр начинаются с десяти и идут в том же порядке, в котором идут латинские буквы. То есть, например, числовое значение буквы «z» равно тридцати пяти.

Во избежание путаницы договоримся далее, что последовательности цифр внутри формул, не сопровождённые нижним индексом, в числовом контексте следует воспринимать как числа, десятично считанные с этих последовательностей. Последовательности цифр же, сопровождённые индексом \(d\), в числовом контексте следует воспринимать как числа, считанные \(d\)-ично.

Это означает, что формулу

\[ 27+14_5+1101_2 \]

следует интерпретировать как

\[ r_{10}(27) + r_{5}(14) + r_{2}(1101) \]

что, в свою очередь, равно сумме двадцати семи, девяти и тринадцати.

Считывание числа

Операция считывания достаточно примитивна: чтобы считать число, достаточно вычислить значение многочлена

\[ \sum_k d^k v(a_k) \]

Единственное, о чём стоит напомнить: иногда многочлен проще вычислять при помощи так называемой схемы Горнера

\[ \sum_k x^k c_k = (\ldots((c_n x + c_{n-1}) x + c_{n-2}) x + \ldots) x + c_0 \]

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

def evaluate(p,x):
    n = degree(p)
    
    total = coeff(p,n)
    for i in range(n,0,-1):
        total = current * x + coeff(p,i-1)
    
    return total

Например, \(123_7\) можно считать по схеме Горнера так:

\[ 123_7 = (1\cdot 7 + 2)\cdot 7 + 3 = 63 + 3 = 66 \]

Запись числа

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

Сейчас мы приведём два эквивалентных способа записи числа. Первый из них вычисляет цифры, начиная с самой младшей, второй — наоборот, начиная с самой старшей.

Способ первый

Пусть \(N = \sum_k d^k v(a_k)\). Требуется найти цифры \(a_i\) (или хотя бы их числовые значения; будем считать операцию восстановления цифры по числовому значению тривиальной).

Младшую цифру легко определить, если заметить, что

\[ v(a_0) = v(a_0)\bmod d = \left(\sum_k d^k v(a_k)\right)\bmod d \]

Правое из этих двух равенств очевидно, а левое следует из неравенств \(0\leqslant v(a_0) < d\).

Вычтя \(v(a_0)\) из левой и правой частей равенства

\[ N = \sum_k d^k v(a_k) \]

и разделив их на \(d\), получаем такую же по виду задачу для числа \((N-v(a_0))/d\).

Способ второй

Старшую цифру можно найти так: ищем максимальное \(m\), для которого \(d^m\leqslant N\). Далее ищем максимальное \(c\), для которого \(c d^m\leqslant N\). Это \(c\) и будет числовым значением старшей цифры. Осталось таким же образом найти цифры числа \(N-c d^m\).

Упражнения

1. Напишите функцию generate_digit_maps, заполняющую два изначально пустых глобальных словаря NUMBER_TO_DIGIT и DIGIT_TO_NUMBER соответствием между цифрами и их числовыми значениями для систем счисления с основанием, не превышающем 36. Внимание: другие названия функций и глобальных переменных будут считаться ошибкой.

2. Напишите функции, реализующие отображения \(r_d\) и \(w_d\) соответственно. Элементы множества \(\mathbb{N}\) считать имеющими тип int, а элементы множества S — тип str.

Указанные функции должны иметь вид

def read (digits, d): pass
def write(number, d): pass

3. Факториальная система счисления, использующаяся, например, при перечислении перестановок, устроена так: у \(k\)-й цифры записи есть всего \(k+1\) различное значение. То есть числа 0, 1, 2, 3, 4, 5, 6, ... имеют следующие записи: 0, 10, 100, 110, 200, 210, 1000, ... Модифицируйте функции read и write так, чтобы при d="fac" они осуществляли чтение и запись в факториальной системе счисления.

Базы данных

Здесь находятся разделы, посвящённые языку SQL запросов к базам данных и конкретно СУБД SQLite как примеру SQL-совместимой СУБД.

СУБД SQLite

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

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

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

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

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

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

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

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

СУБД SQLite

В качестве реализации языка SQL мы будем использовать СУБД SQLite. Для Windows-систем можно скачать с официального сайта архив sqlite-tools, содержащий интерпретатор SQL-команд sqlite3.

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

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

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

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

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

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

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

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

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

DROP TABLE foobar;

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

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

INSERT INTO foobar VALUES(значение1, значение2, ...);

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

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

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

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

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

На последнем пункте остановимся отдельно: если подать NULL в качестве значения колонки с типом INTEGER PRIMARY KEY, значение ячейки будет сгенерировано автоматически. Это очень удобно! (Подобное поведение специфично для 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 такой подзапрос трактуется естественным образом — как таблица, состоящая из результатов такого запроса. Внутри 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. Количество разных возрастов детей Ивана.

Программный интерфейс SQLite

Общая структура модуля sqlite3

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

Импортируется модуль стандартно:

import sqlite3

Далее мы будем для удобства считать, что он импортирован командой:

import sqlite3 as db

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

connection = db.connect("foo.db")

Результат работы этой функции (который мы в дальнейшем будем называть соединением) используется в основном для двух вещей:

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

Основная сущность для работы с базой данный — курсор. Он создаётся методом cursor соединения с базой:

cursor = connection.cursor()

У него есть три наиболее важных метода:

• метод execute для исполнения одного запроса, сформированного по шаблону
• метод executemany для исполнения серии запросов, сформированных по одному шаблону
• метод executescript для исполнения программы на SQL

Если запрос изменяет содержимое какой-либо таблицы (например, этот запрос из серии INSERT, UPDATE, DELETE), изменения нужно подтвердить вызовом метода commit соединения с базой. В противном случае эти изменения не будут сохранены в базу (хотя будут видны дальнейшим запросам, сделанным в рамках текущего соединения).

Если запрос выдаёт какой-то результат, то этот результат можно получить методом fetchall курсора (есть ещё более низкоуровневые fetch и fetchmany, но их мы оставим за рамками обсуждения).

Приведём типичный сценарий работы с базой данных:

cursor.executescript("""
-- тройные кавычки в питоне используются для многострочных текстов

CREATE TABLE squares(arg,val); 
CREATE TABLE people(id INTEGER PRIMARY KEY, name);
""")
## отметим, что CREATE TABLE не требует подтверждения при помощи commit

cursor.execute("INSERT INTO people VALUES(NULL, 'Вася')")
cursor.execute("INSERT INTO people VALUES(NULL, 'Петя')")
cursor.execute("INSERT INTO people VALUES(NULL, 'Даша')")

for i in range(100):
    cursor.execute("INSERT INTO squares VALUES(?,?)", [i, i**2])
    ## это -- пример шаблонного запроса; шаблоны мы обсудим далее

connection.commit()  ## ещё раз отметим, что commit -- метод _не курсора_, а соединения

Использование шаблонных запросов

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

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

Есть ещё метод executemany, который работает примерно так:

## код, эквивалентный вызову cursor.executemany(request, data)

for datum in data:
    cursor.execute(request, datum)

Получение результатов запроса

Результат последнего выполненного запроса можно получить от курсора безаргументным методом fetchall:

cursor.execute("SELECT * FROM foo WHERE bar = baz")
results = cursor.fetchall()

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

Автоматическое закрытие соединения

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

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

К счастью, в Python есть (позаимствованная из LISP) конструкция with...as:

with db.connect("foo.db") as connection:
    # блок кода

Эта конструкция гарантирует, что соединение будет закрыто при выходе из неё (даже при аварийном).

Некоторое количество упражнений

1. Напишите программу, которая принимает на вход имя файла с базой данных, удаляет в ней таблицу foo, если такая там была, и создаёт там таблицу foo(bar,baz). Запрещается пользоваться исключениями или же SQL-командами CREATE TABLE IF NOT EXISTS или DROP TABLE IF EXISTS (не все версии sqlite3 их поддерживают). Узнать наличие таблицы можно в специальной служебной таблице sqlite_master. Записи, соответствующие таблицам базы данных, в ней имеют значение 'table' в колонке type и имя таблицы в колонке name.

2. Напишите программу, которая принимает на вход имя файла с базой данных, создаёт там таблицу squares(n,val) и заполняет парами (x,x**2) для всех x от 1 до 10000000 (10 миллионов). В следующих трёх заданиях работа происходит с созданной в этом задании базой. Программа в них тоже должна принимать на вход только имя файла с базой данных.

3. Напечатайте результаты и время выполнения запроса SELECT n FROM squares WHERE val > 100000 AND val < 105000. Время выполнения можно измерить функцией timeit модуля timeit (прочитайте документацию, не забудьте указать number=1 при вызове, измерять нужно полное время общения с БД, начиная от её открытия и заканчивая печатью результатов).

4. Выполните SQL-команду CREATE INDEX squares_val_index ON squares(val). Повторите измерение из прошлого задания. Обратите внимание на то, что индекс значительно убыстряет поиск значений в колонке. При этом большое количество индексов для одной и той же таблицы замедляют добавление в неё записей. Поэтому иногда рекомендуется перед массовым добавлением записей в таблицу сбросить все индексы, а потом создать их заново.

5. Удалите все записи из таблицы квадратов, а затем измерьте время их добавления при наличии индекса на колонке val и при его отсутствии.

6. Напишите программу, которая принимает на вход два имени файлов с базами данных (эти имена разделены переходом на следующую строчку). Программа должна скопировать все таблицы первой базы во вторую базу. Наличие таблиц во второй базе перед копированием проверять не нужно! Команду, которая использовалась для создания таблицы, можно узнать в колонке sql таблицы sqlite_master.

Основы компьютерной грамотности

Операционные Системы и их компоненты

Эта глава посвящена в первую очередь терминологии.

Ядро операционной системы

В процессе написания

Пользовательский интерфейс

В процессе написания

Дерево файлов

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

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

Один из специальных видов файлов, поддерживаемый почти всеми ОС, — мягкие ссылки или ярлыки. Такие файлы отождествляются с воображаемыми рёбрами дерева файлов, и ОС пытается делать вид, что эти рёбра почти равноправны с настоящими.

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

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

Процессы

В современных многозадачных ОС работающие одновременно друг с другом программы отождествляются с вершинами дерева процессов (которое уже по-настоящему является деревом с выделенным корнем). Рёбра дерева процессов ориентированы в сторону «от корня». Вершины дерева процессов называются процессами. Для ребра, идущего из процесса А в процесс Б, процесс А называется предком (или родителем) процесса Б, а процесс Б — потомком (или ребёнком) процесса А.

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

У каждого процесса есть рабочий каталог — вершина (sic!) дерева файлов, из которой функции ядра ОС выпускают пути в дереве файлов. Пути задаются их текстовыми представлениями, которые имеют вид последовательности названий рёбер этого пути, разделённых символом-разделителем (стандартный символ-разделитель — косая черта /, хотя под Windows чаще используется обратная черта \). Также ОС поддерживают отсчёт путей от какого-нибудь из корней дерева файлов: такой режим называется абсолютными путями (что интересно, в ОС Windows некоторые приложения имеют урезанную поддержку абсолютных путей).

Также у каждого процесса есть стандартные потоки ввода/вывода в количестве трёх штук: один входной stdin и два выходных stdout и stderr. Выходные потоки процессов можно привязывать к входным потокам процессов. Ядро ОС предоставляет приложениям функции записи данных в один из стандартных потоков и чтения данных из stdin. Это — наиболее примитивный механизм передачи данных между различными процессами (позволяющий, в частности, связывать процессы в длинные цепочки, в которых каждый следующий процесс преобразует вывод предыдущего). Отметим, что в ОС Windows большинство приложений не использует этот механизм передачи информации.

Терминалы и их эмуляторы

В процессе написания

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

Терминальное соединение с удалённым компьютером

В процессе написания

В заключение напомним, что сочетание клавиш Ctrl-d терминал интерпретирует как команду «закрыть стандартный поток входа». Большинство программ, ожидающих ввода данных, встречая неожиданный конец потока, завершают свою работу. Те программы, которые игнорируют отсутствие стандартного входа или же переоткрывают его, обычно можно завершить сочетанием Ctrl-c.

Также есть два сочетания, которые часто случайно попадают под руку и приводят к неожиданным последствиям:

• Ctrl-z усыпляет процесс, запущенный из командной оболочки; разбудить обратно исходный процесс можно командой fg
• Ctrl-s блокирует ввод данных с терминала; разблокировать можно сочетанием Ctrl-q

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

Командный интерфейс

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

Наиболее часто используемый командный интерфейс: интерпретатор команд bash в совокупности с UNIX-инструментами — определённым набором програм различного назначения, первые версии которых появились как неотъемлемая часть ОС UNIX. В состав всех юниксоподобных ОС (кроме iOS) входят UNIX-инструменты (хотя в Android их набор по-умолчанию несколько минималистичен, это нивелируется возможностью установки приложений наподобие Termux или Terminal IDE, содержащих в своём составе более полноценный комплект UNIX-инструментов). Под Windows обычно используются приложения MinGW или Cygwin.

Начнём с описания самой главной части такого командного интерфейса — интерпретатора команд bash.

Интерпретатор bash

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

Далее будут описаны только основы работы с bash.

Простейшие команды и запуск приложений

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

• Одинарные кавычки: то, что между ними, воспринимается как одно слово
• Двойные кавычки: некоторые символы и последовательности символов между ними преобразуются в другие (это преобразование называется интерполяцией); например, последовательность \" преобразуется в двойную кавычку (без обратной косой черты)
• Конкатенация: два слова, записанных без пробелов между ними, объединяются; например "a\$b"waa'qq'"x" — это слово a$bwaaqqx

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

Последовательность слов bash интерпретирует следующим образом:

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

Под запуском понимается следующее:

• если содержимое файла представляет собой один из форматов, которые ОС считает исполняемыми, bash создаёт потомка, процедура работы которого определяется тем, как ОС интерпретирует этот формат; при этом все слова команды передаются этому потомку при помощи механизма, позволяющего потомку их в случае надобности получить (слова команды называются аргументами командной строки; они нумеруются, начиная с нуля)
• если файл является текстовым и начинается со строчки вида #!путь_к_файлу, bash запускает указанный этим путём файл, передавая ему слова команды как аргументы командной строки

Поясним обе эти ситуации на примере. Предположим, что в системе установлен интерпретатор языка Python, причём его исполняемая часть находится в файле /usr/bin/python3. Предположим также, что в текущей директории находится файл foobar.py с программой вида

import sys                                                                      
                                                                                
print(sum(map(int,sys.argv[1:]))) 

Тогда команда

python3 foobar.py 1 2 3

приведёт к следующему:

• bash найдёт файл python3 и запустит его, передав ему в качестве аргументов слова python3, foobar.py, 1, 2, 3
• файл python3 представляет собой правильным образом обёрнутый машинный код с программой, интерпретирующей язык программирования Python; эта программа первый аргумент командной строки интерпретирует как название файла с программой на Python
• в переменной sys.argv (языка Python) хранятся аргументы командной строки, начиная с первого; соответственно, программа вычислит значение выражения 1+2+3 и напечатает его

Теперь командой chmod +x foobar.py добавим хозяину файла (а также заодно — всем остальным пользователям ОС) foobar.py право его запускать. Также допишем в начало этого файла комментарий:

#!/usr/bin/python3

После этого команда

./foobar.py 1 2 3

приведёт к следующему:

• поскольку ОС (скорее всего) откажется воспринимать текстовый файл как исполняемый, bash посмотрит на его первую строчку, где написано #!/usr/bin/python3
• bash выполнит команду /usr/bin/python3 ./foobar.py 1 2 3
• далее всё произойдёт ровно так же, как и в предыдущем случае

Несколько простейших команд

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

• echo — печатает свои аргументы, разделяя их пробелами, и заканчивая печать переходом на следующую строчку
• echo -e — интерпретирует некоторые экранирующие последовательности в своих аргментах (например, \n как символ перехода на следующую строчку)
• echo -n — не переходит на следующую строчку
• echo -ne или echo -n -e — совмещает два вышеописанных пункта
• cat — печатает друг за другом содержимое файлов, названия которых указаны в аргументах
• pwd — текущий рабочий каталог для bash
• ls — его содержимое
• ls -a — его содержимое, включая файлы, названия которых начинаются с точки
• ls -l — содержимое с кучей подробностей
• ~ — вообще говоря, не команда, а слово, которое, будучи незакавыченным, интерполируется в абсолютный путь к домашней папке пользователя
• * — как и тильда, не команда, а слово, которое, будучи незакавыченным, интерполируется в содержимое текущей папки
• cd — смена текущей папки (если запустить без аргументов, то переходит в домашнюю папку)
• bash — обычно используется с названием файла в качестве аргумента командной строки; выполняет все команды, записанные в файле, друг за другом в неинтерактивном режиме
• which — для команд, соответствующих исполняемому файлу, показывает, какому именно файлу команда, поданная аргументом, соответствует
• man — стандартное средство просмотра документации; в качестве аргумента принимает название команды, документация к которой требуется
• info — ещё одно средство просмотра документации; часть документации у info своя
• less — интерактивное средство просмотра текстовых файлов; выйти из него можно клавишей q (ни Ctrl-C, ни Ctrl-D на него не работают)
• sed — стандартный текстовый редактор с командным интерфейсом; его описание дано в конце этой главы

Переменные окружения

В bash есть механизм переменных. У каждой переменной есть название — последовательность латинских букв и цифр, начинающаяся с буквы (при этом нижнее подчёркивание также считается буквой). Чтобы определить переменную, нужно написать

название_переменной=слово

Ключевой момент: между названием переменной, знаком = и словом не должно быть пробелов!

Далее значение этой переменной можно получить интерполяцией выражения $название_переменной. Здесь есть ещё один очень важный момент: если интерполяция была произведена вне двойных кавычек, значение переменной разбивается на отдельные слова. То есть, например, последовательность команд

foo="abc def"
cat $foo

печатает содержимое файлов abc и def, а не одного файла с названием abc def. Для достижения же последнего эффекта нужно дать команду cat "$foo".

Важно знать про следующие стандартные переменные:

• PATH — тут хранятся разделённые двоеточиями пути, в которых bash ищет исполняемые файлы
• 0, 1, 2, 3, и т.д. — аргументы командной строки (существенно, если bash запущен в неинтерактивном режиме)
• ? — код ошибки последней выполненной команды (равен 0, если команда завершилась без ошибок)

Перенаправление потоков

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

команда < foobar  # на вход подаётся содержимое файла foobar
команда > foobar  # выход записывается в новый файл foobar
команда >> foobar # выход дописывается в конец файла foobar

Также есть возможность объединить несколько команд в цепочку:

команда_1 | команда_2 | команда_3 | ... | команда_n

В такой цепочке стандартный выход каждой команды (кроме последней) связывается со стандартным входом следующей.

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

echo "`echo a; echo b`"

Полезные возможности

Стрелками вверх/вниз можно перематывать историю команд.

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

Потоковый текстовый редактор sed

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

Запускается sed командой:

sed -e правило

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

Обычно используются следующие предикаты:

• пустой — ему удовлетворяет любая строчка
• доллар $ — ему удовлетворяет последняя строчка
• число — ему удовлетворяет строчка с таким номером (нумерация начиается с единицы)
• два числа, разделённых запятой — ему удовлетворяют все строчки в указанном диапазоне (включая концы)
• образец, заключённый в обратные косые черты — ему удовлетворяют все строчки, соответствующие образцу
• восклицательный знак, поставленный после предиката, означает отрицание к нему (например, 2,4! — все строчки, кроме второй, третьей и четвёртой)

Наиболее полезные команды такие:

• s/образец/результат/ — заменяет часть строчки, удовлетворяющую образцу, на результат
• q — печатает результат преобразований к данному моменту и завершает работу
• d — вообще не печатает результат преобразования и сразу переходит к обработке следующей строчки
• p — печатает результат преобразований к данному моменту
• n — сразу переходит к следующей строчке, но при этом продолжает текущую последовательность преобразований

Если запустить sed комнадной sed -ne, то q и n перестают что-либо печатать, а также отключается печать по-умолчанию. Например, чтобы напечатать строчки с 10-й по 20-ю, проще написать

sed -ne '10,20p'

чем

sed -e '1,9d;21,$d'

Синтаксис образцов

Образцы используются для описания предикатов над текстами.

Самый простой образец имеет вид текста, который ему удовлетворяет (символы $, ^, *, [, \, . нужно экранировать при помощи \ перед ними). Также такому образцу удовлетворяет текст, содержащий этот образец в качестве подтекста. Например, образцу foo удовлетворяют тексты foo, foobar, barfoo и barfoobaz (а также — бесконечное множество других).

Ещё в образец разрешается включать одно из (это не всё, что имеется, но наиболее полезное):

• образцу . удовлетворяет любой один символ
• образцу [...] удовлетворяет любая буква, указанная внутри квадратных скобок
• образцу [^...] удовлетворяет любая буква, не указанная внутри квадратных скобок
• образцу ^ удовлетворяет начало строчки
• образцу $ удовлетворяет конец строчки

Например, образцу ^[A-Z][a-z][a-z] удовлетворяет текст, состоящий хотя бы из трёх букв, первая буква которого — заглавная латинская, а вторая и третья — строчные латинские.

Часть образца можно заключить в скобки \( и \); тот кусок текста, который удовлетворяет образцу в скобках, запоминается под некоторым номером от 1 до 9 (куски нумеруются по порядку, слева направо); запомненный кусок можно использовать либо в рамках того же образца, либо в правой части команды s при помощи выражения \1, \2, \3 и т.д.

Справа от односимвольного образца или же образца, заключённого в скобки, можно поставить квантор: выражение \{M,N\} или \{M,\}, где M и N — целые неотрицательные числа. Такому образцу удовлетворяет текст, состоящий из K текстов, каждый из которых удовлетворяет образцу перед квантором, где K не меньше M и не больше N. Например, образцу ^[ab]\{1,2\}$ удовлетворяют только тексты a, b, aa, ab, ba, bb.

Для некоторых кванторов есть сокращения:

• * — сокращение для \{0,\} (хотя бы ноль)
• \+ — сокращение для \{1,\} (хотя бы один)
• \? — сокращение для \{0,1} (ноль или один)

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

1. её начало самое левое среди всех таких частей
2. каждый квантор соответствует наибольшему возможному количеству повторений при фиксированных количествах повторений кванторов слева от него (например образцу \(ab\)*\(aba\)* в тексте ababa удовлетворяет часть abab с количествами повторений 2 и 0, а не часть ababa с количествами повторений 1 и 1).

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

sed -e 's/foo/bar/'  # в каждой строчке заменяет самое первое слово foo на bar
sed -e 's/foo/bar/g' # в каждой строчке заменяет все слова foo на bar

Примеры

Здесь мы приведём часто используемые правила для sed.

• s/^/foobar/ — дописывает foobar в начало строчки
• s/$/foobar/ — дописывает foobar в конец строчки
• s/^.*$/foobar/ — заменяет всю строчку на foobar
• /^$/d — удаляет пустую строчку
• $d — удаляет последнюю строчку

Продвинутые возможности bash

Язык командной оболочки bash, в принципе, является совершенно полноценным языком программирования, хотя его и не рекомендуется использовать для написания сколько-нибудь сложных программ: всё-таки основное его назначение — синхронизация процессов и автоматизация простых действий, а не исполнение нетривиальных алгоритмов. В этом смысле bash представляет самый базовый уровень т.н. скриптовых языков. К «наиболее продвинутым» скриптовым языкам (в том смысле, что они наиболее близки к т.н. языкам общего назначения) обычно относят Python и Javascript (на платформе nodejs). Где-то посередине между этими крайностями находятся (до сих пор живые!) языки perl и tcl.

В этой главе описаны некоторые возможности bash как языка программирования.

Арифметика

В bash есть рудиментарная поддержка целочисленной арифметики. Арифметическое выражение (возможно, содержащее переменные) можно взять в «толстые скобки» $(( и )). Например, так:

foo=2
echo $((foo+3))
foo=$((foo + 7))

Аналогами последней команды являются команды:

((foo = foo + 7))
let "foo = foo + 7"

Следует помнить, что bash не поддерживает работу с длинными числами и нецелые числа, поэтому в нетривиальных ситуациях рекомендуется пользоваться внешними инструментами:

foo = 123456789
python3
bar="`python3 -c "print($foo ** 9)"`"

Массивы

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

foo[0]=a
foo[1]=234
foo[2]="${foo[0]}"

Если индекс не указан, то считается, что он равен 0, то есть следующие две команды эквивалентны:

foo=bar
foo[0]=bar

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

foo[0]=bar
foo[5]=abc
echo $foo[5]   # напечатает bar[5]
echo ${foo[5]} # <-- а вот так правильно!

Как и в Python, отрицательные индексы означают отсчёт с конца массива:

unset foo
foo[0]=1
foo[1]=2
foo[2]=3
foo[3]=10
echo "${foo[-1]}"  # будет напечатано 10

У массивов есть три режима коллективной интерполяции:

foo[0]="abc def"
foo[1]="xyz"
foo[2]="1    2     3    4"

# следующие три команды эквивалентны
echo ${foo[*]}
echo ${foo[@]}
echo abc def xyz 1 2 3 4

# следующие две команды эквивалентны
echo "${foo[@]}"
echo "abc def" "xyz" "1    2     3    4"


# следующие две команды эквивалентны
echo "${foo[*]}"
echo "abc def xyz 1    2     3    4"

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

В заключение отметим, что в рамках сценариев можно использовать последовательности $* и $@, интерполирующиеся в массив аргументов командной строки, начиная с первого. Правила интерполяции те же, что и описанные выше для обычных массивов.

Условия

Каждая выполненная команда оболочки может завершиться как успехом, так и ошибкой. В случае успеха в переменную ? автоматически записывается число 0. В случае ошибки — какое-нибудь ненулевое число (вообще говоря, зависящее от ошибки, но не стандартизированным образом).

В зависимости от значения ? можно производить ветвление:

if команда; then список_команд1; else список_команд2; fi

Если команда завершается успехом, выполняется список_команд1. В противном случае — список_команд2.

Обычно в качестве команды используется test с какими-нибудь аргументами (см. man test). Часто можно видеть синтаксис [ что-то ], вызывающий test что-то. Также есть конструкция [[ что-то ]], обрабатывающаяся самим bash.

Циклы

Из циклов чаще всего применяется «простой for»

for переменная in слово_1 слово_2 ... слово_n; do список_команд; done

Переменная по очереди становится равна каждому из слов. В качестве генератора списка слов часто используется команда seq (см. man seq).

Также изредка бывает полезен цикл while:

while команда; do список_команд; done

По принципу работы while аналогичен if: перед каждой итерацией он выполняет команду и смотрит на результат её выполнения (значение переменной ?).

Функции

Функции в bash — механизм определения новых команд. Определение функции выглядит так:

# допустим любой из следующих вариантов:
function название { список_команд; }
название () { список_команд; }

Далее вызвать функцию можно просто как команду:

название аргумент_1 аргумент_2 ... аргумент_n

Тело функции представляет собой совершенно самостоятельный сценарий: в частности, переменные 1, 2, 3 и т.д. — это аргументы, с которыми функция вызвана, а не аргументы, с которым вызван сценарий, вызвавший функцию. Единственная важная тонкость: поскольку функция исполняется тем же экземпляром bash, что и остальной сценарий, она может изменять переменные этого экземпляра, причём такое поведение включено по-умолчанию. Локальные для функции переменные нужно создавать командой local:

#!/bin/bash

foo () {
    i=$(( i + 1))
}

bar () {
    local i=$i
    i=$(( i + 1))
}

i=1
echo $i  ## 1
foo
echo $i  ## 2
bar
echo $i  ## 2

Дескрипторы

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

• дескриптор 0 (т.н. stdin), работающий на вход; всевозможные операции «считывания данных с клавиатуры» берут данные именно из него
• дескриптор 1 (т.н. stdout), работающий на выход; всевозможные операции «печати на экран» отправляют данные именно в него
• дескриптор 2 (т.н. stderr), работающий на выход; всякая информация вспомогательного плана отправляется именно в него

Все команды, запущенные из bash, наследуют его дескрипторы, если для этих команд не указано никаких перенаправлений. Поменять связь стандартных дескрипторов и активировать новые можно командой exec.

Три самых распространённых режима — связь с файлом:

exec 3<foo   # открывает дескриптор 3 на вход, связывает с файлом foo
exec 3>foo   # открывает дескриптор 3 на выход, связывает с файлом foo
exec 3>>foo  # открывает дескриптор 3 на выход, связывает с концом файла foo

Разница последних двух режимов в том, что первый из них создаёт файл foo или же очищает его перед активацией дескриптора. Второй же оставляет содержимое foo неизменным и дописывает поступившие в него данные в конец файла.

Также бывает очень полезным копирование дескриптора:

exec 4<&3  # активирует дескриптор 4 в том же режиме, что и 3
exec 5<&-  # деактивирует дескриптор 5

Вообще говоря, есть ещё оператор >&, но он в большинстве ситуаций аналогичен <& (несмотря на то, что в документации к bash сказано обратное). По факту единственное различие — оператор >& работает чуть быстрее, но корректная работа гарантируется только для копирования дескрипторов, активированных на выход.

Настоятельно не рекомендуется изменять режимы работы стандартных дескрипторов в интерактивном режиме: обычно это приводит к тому, что bash зависает или же вообще завершается.

Асинхронный запуск команды

Обычно при запуске любой команды bash дожидается её завершения (если команда внешняя, то он на время выполнения команды засыпает). Это называется синхронным запуском.

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

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

• если запущенное приложение пытается брать данные с терминала, bash его насильно усыпляет (разбудить приложение в таком случае можно командой fg)
• если убить bash до завершения работы асинхронно запущенного приложения, оно тоже насильно завершается; для того, чтобы предотвратить такое поведение, используется команда nohup (см. man nohup)

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

Ниже — пример использования именованных каналов.

#!/bin/bash

ping () {
    echo 1
    while true; do
        # read читает одну строчку и записывает её в указанную переменную
        read x
        echo "PING got ${x}" 1<&2
        sleep 0.5
        echo $(( x + 1 ))
    done
}

pong () {
    while true; do
        # здесь используется та же переменная x, что и в ping, но эти 
        # функции далее запускаются в разных экземплярах bash
        read x 
        echo "PONG got ${x}" 1<&2
        sleep 0.5
        echo $(( x + 1 ))
    done
}


## mkfifo создаёт файл-канал 
## Такой файл начинает работать, когда один процесс активирует его 
## на вход, а другой процесс -- на выход.
mkfifo ping_pong_queue
mkfifo pong_ping_queue

## Тонкий момент: перенаправление > ping_pong_queue первой команды 
## не завершается до тех пор, пока вторая команда не попытается сделать
## перенаправление < ping_pong_queue. Поэтому у перенаправлений 
## именно такой порядок: если ping сначала попытается активировать 
## ping_pong_queue, а pong -- pong_ping_queue, команды будут 
## ждать друг друга бесконечно!
ping > ping_pong_queue < pong_ping_queue &
pong < ping_pong_queue > pong_ping_queue &

Конкретно этот сценарий страдает от того, что после завершения запустившей его оболочки два дочерних процесса не умирают: завершаются только те команды, которые исполнялись в момент завершения bash; циклы же продолжают работать. Более адекватная версия может выглядеть, например, так:

#!/bin/bash

PARENT_PID=$PPID  # номер процесса, _запустившего_ этот сценарий

parentIsAlive () {
    test `ps -o pid= $PARENT_PID`
}


ping () {
    echo 1
    while parentIsAlive; do
        read x
        echo "PING got ${x}" 1<&2
        sleep 1
        echo $(( x + 1 ))
    done
}

pong () {
    while parentIsAlive; do
        read x
        echo "PONG got ${x}" 1<&2
        sleep 1
        echo $(( x + 1 ))
    done
}

cleanup () {
    while parentIsAlive; do sleep 1; done

    rm -f ping_pong_queue
    rm -f pong_ping_queue
}


mkfifo ping_pong_queue
mkfifo pong_ping_queue

ping > ping_pong_queue < pong_ping_queue &
pong < ping_pong_queue > pong_ping_queue &
cleanup &

Текстовые форматы файлов

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

Как посмотреть содержимое файла?

Вы знакомы как минимум с командами cat и less, которые предназначены для просмотра содержимого файла. Но проблема в том, что терминал умеет отображать содержимое далеко не всякого файла. Наиболее удобным средством просмотра содержимого файла произвольной природы является шестнадцатиричный дамп. Его можно получить, например, командами hexdump, hd и xxd (наиболее красивый дамп получается командой hd, которая является синонимом hexdump с правильными опциями).

Шестнадцатеричный дамп представляет собой последовательность пар шестнадцатеричных цифр: каждая пара задаёт значение одного байта содержимого файла. Например, применение hd к файлу с содержимым abcd выдаст дамп вида

00000000  61 62 63 64 0a                                    |abcd.|
00000005

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

Стандарт ASCII

Стандарт ASCII устанавливает соответствие между числами от 0 до 127 и сигналами, которые мог подавать/воспринимать типичный телетайп 60-х годов. Большая часть таблицы ASCII соответствует цифрам, буквам и знакам препинания, которые можно набрать с клавиатуры. Первые 32 значения соответствуют управляющим командам (например, по команде номер 10, поданной на телетайп нажатием кнопки или же сигналом с компьютера, он отматывал рулон бумаги на одну строчку; а по команде номер 7 звенел колокольчиком).

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

• клавиша Shift уменьшает значение кода нажатой кнопки на 32
• клавиша Ctrl обнуляет 6-й и 7-й разряды кода нажатой кнопки (то есть убирает из двоичного представления слагаемые 64 и 32)

Конечно, современные ОС всего лишь пытаются эмулировать такое поведение: клавиатура передаёт компьютеру информацию о всех нажатых клавишах, а уже ОС решает, что с этим делать.

Поскольку стандарт ASCII позволяет кодировать те символы, из которых состоит то, что люди называют словом «текст», файлы, содержимое которых предназначено для интерпретации в соответствии со стандартом ASCII, называются текстовыми файлами (в кодировке ASCII).

Кодировка русского языка

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

• кодировка CP866 (также встречается под названием DOS)
• кодировка CP1251 (также встречается под названием WINDOWS)
• кодировка KOI8-R
• кодировка UTF-8

Первые три из них относятся к однобайтовым: каждый символ, как и в ASCII, кодируется ровно одним байтом. Об этих кодировках мы сейчас и поговорим.

Кодировки CP866 и CP1251 весьма похожи друг на друга: как и в ASCII, в этих кодировках буквы русского алфавита идут подряд друг за другом в алфавитном порядке, а заглавные отличаются от строчных на 32. Единственная проблема: в русском языке 33 буквы, что несовместимо со свойствами, описанными в предыдущем предложении. Козлом отпущения была выбрана буква «ё». Что в CP866, что в CP1251 эта буква, во-первых, находится вне алфавита, а во-вторых — заглавная отличается от строчной не на 32.

Кодировка KOI8-R гораздо интереснее: она была придумана в те времена, когда часть сетевого оборудования и программного обеспечения, предназначенных для передачи текста, использовала старший бит каждого байта в служебных целях. Основное отличительное свойство KOI8-R — текст сохранял читаемость при внесении произвольных изменений в старший бит его байт. Например, если обнулить каждый старший бит в KOI8-R-представлении текста

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

получится

s_E[X VE E]# \TIH MQGKIH FRANCUZSKIH BULOK, DA WYPEJ ^A@!

А вот кодировка UTF-8 уже не является однобайтовой: в ней каждый символ может кодироваться последовательностью байт длины от 1 до 6, причём само понятие «символа» понимается существенно более широко, чем в любой из вышеупомянутых кодировок.

Юникод

Юникод — современный стандарт, определяющий понятия «символ» и «текст», а также — способы их представления.

С этим стандартом связано некоторое количество аббревиатур, которые полезно уметь различать:

• UCS — «алфавит» юникода; таблица номеров всевозможных символов
• UCS-2 — кодировка постоянной ширины (каждый символ кодируется 2 байтами), предшественник UTF-16
• UCS-4 — то же, что и UTF-32
• UTF-8 — кодировка переменной ширины (каждый символ кодируется количеством байт от 1 до 6), расширение ASCII
• UTF-16 — кодировка переменной ширины (каждый символ кодируется двумя или четырьмя байтами)
• UTF-32 — кодировка постоянной ширины (каждый символ кодируется четырьмя байтами)

Наиболее просто устроена кодировка UTF-32. Каждый символ в ней кодируется просто его номером в таблице UCS. Есть единственная проблема: на самом деле, кодировок UTF-32 не одна, а две. Различаются они тем, в каком порядке перечисляются байты каждого из номеров: от младшего к старшему, или наоборот.

В качестве подсказки файл, закодированный UTF-32, может содержать в качестве первого символа т.н. Byte-Order Mark (BOM) с номером 65279 (FEFF в шестнадцатеричной записи).

С UTF-16 всё несколько хитрее: как и с UTF-16, есть два вида этой кодировки, различающиеся порядком байт. При этом символы с номерами, не превышающими 65535, кодируются этими самыми номерами (как и в UTF-32). А вот для символов с большими номерами используется хитрая схема кодирования (подробности см. например в википедии).

Кодировка UTF-8 на настоящий момент является самой распространённой из всех кодировок юникода. Она устроена следующим образом: номер символа записывается в двоичной системе счисления, далее достраивается ведущими нулями до одной из точек остановки (7 бит, 11 бит, 16 бит, 21 бит, 26 бит, 31 бит), после чего эти биты распределяются по байтам в соответствии с таблицей:

 7 бит  0xxxxxxx
11 бит  110xxxxx 10xxxxxx
16 бит  1110xxxx 10xxxxxx 10xxxxxx
21 бит  11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
26 бит  111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
31 бит  1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

Порядок бит в этой таблице традиционный: они идут от самых старших к самым младшим. Например, символ «скрипичный ключ» (𝄞), имеющий номер 119070 (1d11e в шестнадцатеричном виде), представляется в UTF-8 так: число 1d11e записывается 17ю битами:

11101000100011110
1   d   1   1   e

Ближайшая точка остановки: 21 бит. Дополняем нулями, получая последовательность

000011101000100011110

Далее разбиваем её на шестёрки, начиная с конца:

000 011101 000100 011110

Наконец, вписываем служебные последовательности:

двоичное    11110000 10011101 10000100 10011110
десятичное       240      157      132      158
16-ричное         f0       9d       84       9e

Как перекодировать текстовый файл?

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

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

iconv -f из_какой_кодировки -t в_какую_кодировку имя_файла

Результат перекодировки выдаётся на стандартный выход. Обычно его перенаправляют в какой-нибудь файл.

Как это сделать в питоне?

В Python есть свои встроенные средства перекодировки. Кроме типа str для текстов есть тип bytes для последовательностей байт. Эти два типа можно преобразовывать друг в друга следующим образом:

str(последовательность_байт, название_кодировки)
bytes(текст, название_кодировки)

Первая конструкция интерпретирует последовательность байт как текст в указанной кодировке. Вторая преобразует текст в последовательность байт согласно указанной кодировке.

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

#!/usr/bin/env python3
import sys
import os

def get_opt(opt):
    for i,arg in enumerate(sys.argv):
        if i == 0: continue

        if arg == "-"+opt: return sys.argv[i+1]

    return None

def get_from_enc(): return get_opt("f")
def get_to_enc():   return get_opt("t")

def get_filename():
    for i,arg in enumerate(sys.argv):
        if i == 0: continue
        
        if (sys.argv[i-1][0] != "-" and 
            sys.argv[i][0]   != "-"): return arg

    return None

def main():
    from_enc = get_from_enc()
    to_enc   = get_to_enc()
    filename = get_filename()

    if from_enc == None:
        print("Входная кодировка не указана")
        return
    
    if to_enc == None:
        print("Выходная кодировка не указана")
        return

    contents = None
    # --------------V  стандартный поток входа
    with (os.fdopen(0,"rb") if filename == None else 
          open(filename,"rb")) as file:
        contents = file.read()

    # -------V  это номер стандартного выхода
    os.write(1,bytes(str(contents,from_enc),to_enc))

main()

Из этой программы можно уяснить следующее:

• файлы можно открывать в режиме "rb" (а также "wb" и "ab"); в этом случае методы read и write работают с типом bytes, а не str
• with можно использовать вместе с open
• sys.stdout открыт в режиме "w", а не "wb"; именно поэтому печать результата производится при помощи os.write
• с sys.stdin ровно та же ситуация, осложнённая тем, что os.read не умеет читать сразу всё содержимое файла

Как вручную отредактировать содержимое нетекстового файла?

Проще всего воспользоваться командой xxd. У неё есть обратный режим xxd -r, который получает на вход шестнадцатеричный дамп и выдаёт соответствующее этому дампу содержимое. То есть процесс работы выглядит так:

xxd название_файла > название_дампа

vim/nano/emacs/любой_другой_редактор  название_дампа

xxd -r название_дампа > название_файла

Компьютерные сети

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

Основные термины

Сетевое взаимодействие основывается на большом количестве стандартов, устанавливающих конкретные детали процедуры обмена сообщениями между приложениями. Эти стандарты называются сетевыми протоколами семейства TCP/IP (далее в этой главе — просто сетевыми протоколами).

Сетевые протоколы разделяются на четыре уровня (в скобках даны альтернативные названия):

• уровень приложений (прикладной уровень, application layer)
• уровень передачи (транспортный уровень, transport layer)
• уровень интернета (сетевой уровень, internet layer)
• уровень связи (канальный уровень, link layer)

Обычно при передаче сообщения по тому или иному каналу используются все 4 уровня:

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

Типичные примеры сетевых протоколов:

• приложений: HTTP, FTP, SMTP, SSH
• передачи: TCP, UDP
• интернета: IPv4, IPv6
• связи: Ethernet, Wi-Fi, PPP

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

Протоколы интернета

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

Топология сетей

С точки зрения IPv4 компьютерная сеть представляет собой неориентированный граф, вершины которого соответствуют реальным или виртуальным компьютерам, а рёбра — каналам связи между ними. Концы рёбер этого графа называются сетевыми интерфейсами. Каждый сетевой интерфейс имеет 32-битный адрес, разделённый на две части: префикс и номер узла (host number). Длина префикса определяется суффиксом — числом от 0 до 32, означающем количество бит в префиксе. Традиционно IPv4-адреса записываются побайтово, каждый байт — в десятичной системе счисления. Сами значения байт разделяются точками. Суффикс приписывается справа через дробную черту.

Например, адрес

      префикс         номер узла
11000000101010000000 000111111110

обычно записывают как 192.168.1.254/20. Есть ещё устаревший термин маска подсети: маской подсети, соответствующей суффиксу s, называется адрес с суффиксом s, у которого каждый двоичный разряд префикса равен 1, а каждый двоичный разряд номера узла равен 0.

Например, суффиксу 20 соответствует маска подсети 255.255.240.0 (суффикс в записи маски не указывается, поскольку он однозначно восстанавливается по этой записи).

В каждой вершине компьютерной сети гарантируется наличие ребра-петли (loopback interface) с адресом 127.0.0.1 (суффикс может быть произвольным).

Алгоритм маршрутизации

Каждое сообщение, передаваемое при помощи IPv4, наделяется IPv4-заголовком, который содержит как минимум следующую информацию: адрес назначения (destination address), обратный адрес (source address), время жизни (Time To Live). Эта информация определяет путь, по которому пойдёт сообщение. Адреса в IPv4-заголовке занимают ровно по 4 байта (соответственно, никакого суффикса не содержат и на части не делятся).

Большинство сетевого оборудования придерживается приблизительно следующего алгоритма (который выполняется сверху вниз до первого подходящего пункта):

1. Если сообщение пришло на какой-то интерфейс и адрес назначения в точности совпадает с адресом интерфейса, оно завершает свой путь (с него снимается IPv4-заголовок, после чего ОС обрабатывает содержимое сообщения в соответствии с одним из протоколов передачи).

2. Если TTL равен 0, сообщение уничтожается, а по обратному адресу отправляется служебное сообщение с соответствующей ошибкой. В противном случае TTL уменьшается на 1. Это необходимо для избежания циклических маршрутов.

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

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

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

6. Если интерфейсов с хорошим адресом нет, то сообщение отправляется в
   «шлюз по-умолчанию» (default gateway). Отметим небольшую тонкость: при настройке сетевого оборудования default gateway задаётся не названием интерфейса, а IPv4-адресом соответствующего соседа.

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

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

АБ: 192.168.1.3/24 -- 192.168.1.5/24
БВ: 192.168.2.1/24 -- 192.168.2.2/24
ВА: 192.168.2.2/16 -- 192.168.1.3/16

А: шлюз по-умолчанию 192.168.1.5
Б: шлюз по-умолчанию 192.168.1.3
В: шлюз по-умолчанию 192.168.1.3

Пусть компьютер А отправляет сообщение с адресом назначения 192.168.1.1. Этот адрес не является адресом какого-то из соседей (192.168.1.5 и 192.168.2.2). Для него есть два хороших кандидата: канал АБ (совпадает префикс длины 24) и канал АВ (совпадает префикс длины 16). Сообщение будет отправлено по каналу АБ.

Поскольку 192.168.1.1 не совпадает с адресом 192.168.1.5, который назначен интерфейсу Б ребра БА, сообщение будет перенаправлено дальше. Для него есть только один хороший кандидат в вершине Б: это канал БА с адресом соседа 192.168.1.3 и совпадающим префиксом длины 24. Туда и будет отправлено сообщение.

Поскольку 192.168.1.1 не совпадает с адресом 192.168.1.3, который назначен интерфейсу А ребра АБ, сообщение будет перенаправлено дальше. Мы опять оказались в первоначальной ситуации. Из этого делаем вывод, что такое сообщение будет ходить между компьютерами А и Б до тех пор, пока не истечёт его время жизни (TTL).

Рассмотрим другой пример. Пусть компьютер В отправляет сообщение с адресом назначения 192.168.1.5. Этот адрес не является адресом соседнего интерфейса, но совпадает по префиксу с адресом 192.168.1.3/16. Поэтому сообщение будет отправлено по каналу ВА. Попав на компьютер А, сообщение будет передано на компьютер Б, поскольку адрес назначения полностью совпадает с адресом интерфейса Б ребра АБ.

Наконец, рассмотрим ситуацию, когда с компьютера А уходит сообщение на адрес 10.0.0.1. Поскольку этот адрес не является адресом соседа и не совпадает по префиксу ни с одним из интерфейсов компьютера А, сообщение будет отправлено в шлюз по-умолчанию, т.е. на компьютер Б. А оттуда по аналогичной причине оно будет отправлено обратно на компьютер А (откуда опять отправится на Б и т.д.).

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

Зарезервированные адреса

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

• с 192.168.0.0 по 192.168.255.255
• с 172.16.0.0 по 172.31.255.255
• с 10.0.0.0 по 10.255.255.255

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

Особенности IPv6

В процессе написания

Протоколы передачи

В процессе написания