CS general Flashcards

1
Q

Принципы кодировки

A

UTF-32 – это кодировка, которая переводит все символы в наборы из 32 бит. Это простой алгоритм, но изводящий много места впустую. UTF-16 и UTF-8 являются кодировками с переменной длиной кодирования. Если символ может быть закодирован одним байтом(потому что номер пункта символа очень маленький), UTF-8 закодирует его одним байтом. Если нужно 2 байта, то используется 2 байта. Кодировка сообщает старшими битами, сколькими битами кодируется текущий символ. Такой способ экономит место, но так же и тратит его в случае, если эти сигнальные биты часто используются. UTF-16 является компромиссом: все символы как минимум двухбайтные, но их размер может увеличиваться до 4 байт, если нужно.
Unicode – это огромная таблица соответствия символов и чисел, а различные UTF кодировки определяют, как эти числа переводятся в биты.
любой символ может быть закодирован множеством разных последовательностей бит, и любая последовательность бит может представлять разные символы, в зависимости от используемой кодировки. разные кодировки используют разное число бит на символ и разные значения для кодирования разных символов.
Гениальность UTF-8 в бинарной совместимости с ASCII, которая является де-факто основой для всех кодировок. Все символы ASCII занимают максимум байт в UTF-8 и используют те же биты, что и в ASCII. Иными словами, ASCII может быть отражено 1:1 в UTF-8. Любой символ не из ASCII занимает 2 или более байт в UTF-8. Большинство языков программирования, использующих ASCII в качестве кодировки исходного кода, позволяет включать текст в UTF-8 прямо в текст
Первый бит каждого байта кодирующего символ отвечает не за сам символ, а за определение байта. То есть например если ведущий (первый) бит нулевой, то это значит что для кодирования символа используется всего один байт. Что и обеспечивает совместимость с ASCII.
Для двухбайтовых символов первые три бита должны быть такие — 110
для трех-байтовых символов в первом байте ведущие биты — 1110
в кодировке UTF-16 любой символ юникода может быть закодирован либо двумя, либо четырьмя байтами.
Суррогатная пара — это две кодовые пары используемые для кодирования одного символа (итого 4 байта). Для таких суррогатных пар в таблице юникода отведен специальный диапазон от D800 до DFFF. Это значит, что при преобразовании кодовой пары из байтового вида в шестнадцатиричный вы получаете число из этого диапазона, то перед вами не самостоятельный символ, а суррогатная пара.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Что такое SSH

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Основные функции SSH

A

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

Безопасные команды доступа к хосту. SSH дает возможность выполнять безопасные команды доступа к хосту, такие как ssh (удаленная оболочка), slogin (удаленный вход в систему), scp (удаленное копирование);
X11 Forwarding. SSH предоставляет встроенный механизм для выполнения удаленных клиентов X Window.
Port forwarding. SSH может выполнять переадресацию портов, передавая трафик c одного порта одной машины на другой порт другой машины. При этом передаваемый трафик шифруется;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Обеспечение безопасности SSH

A

Безопасность протокола достигается использованием нескольких решений, которые сводят к минимуму риск использования соединения:

  • Шифрование соединение, которое может выполняться одним из методов, выбранных в процессе переговоров. Шифрованное соединение не позволяет просто перехватить и использовать трафик. Выбор алгоритма шифрования делает систему более гибкой, позволяя не использовать алгоритмы, в которых обнаружены слабые места или которые не может поддерживать одна из сторон;
  • Аутентификация сервера выполняется при любом соединении. Это не позволяет выполнить подмену сервера или подмену трафика;
  • Аутентификация клиента может выполняться одним из нескольких доступных способов. Это с одной стороны может повысить надежность аутентификации, с другой – делает систему более гибкой и упрощает ее использование;
  • Проверка целостности пакетов позволяет отследить любые незаконные изменения в трафике соединения. При обнаружении таких изменений, соединение немедленно разрывается;
  • Временные параметры аутентификации не позволяют воспользоваться данными соединения в том, случае, если спустя некоторое время после перехвата оно все-таки было расшифровано. Устаревание обычно происходит через час;
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Аутентификация сервера (SSH)

A

Аутентификация сервера производится при помощи инфраструктуры открытых ключей. Клиент, который хочет установить соединение с сервером шифрует данные известным ему открытым ключом сервера и отправляет их серверу. Сервер должен расшифровать их при помощи известного только ему секретного ключа, и отправить их назад. Так клиент может быть уверен в том, является ли хост тем, за кого себя выдает.
Аутентификация сервера по протоколу SSH выполняется при помощи инфраструктуры открытых ключей. Открытый ключ сервера клиент получает при первом соединении с ним.
Аутентификация сервера дает возможность не полагаться на службу имен и маршрутизацию пакетов. В том случае, если нарушителю удалось подменить запись в DNS или перенаправить IP-пакеты на свой хост, аутентификация не пройдет, поскольку хост не обладает необходимыми секретными ключами.

ssh защищает от

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Аутентификация клиента SSH

A

Методы аутентификации клиентов, которые использует SSH:

Host-based аутентификация
Аутентификация с помощью открытых ключей
Kerberos-аутентификация
Парольная аутентификация.
По хостам. Метод аналогичный используемому в r-командах. В том случае, если соединение устанавливается с привилегированного порта, и файл .rhosts позволяет вход в систему, он разрешается. Этот метод является потенциально небезопасным, рекомендуется не использовать его. Для повышения уровня своей безопасности метод может быть дополнен RSA-аутентификацией клиентского хоста.

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

Керберос. Аутентификация проводится по схеме v5 Kerberos.

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Сервер sshd

A

Как и в любом сетевом взаимодействии, в SSH-соединении участвуют две стороны: клиент и сервер. Сервер SSH реализован в виде программы sshd.

Сервер sshd является независимой программой, поэтому его запуск нужно производить во время загрузки компьютера стартовыми скриптами. То есть, вызов sshd либо должен осуществляться явно одним из rc-скриптов, либо ссылки на скрипт запуска следует включить в иерархию /etc/rc?.d/.
Для того чтобы сервер sshd автоматически стартовал при запуске компьютера, необходимо добавить его вызов в скрипты загрузки.

Будучи запущенным, демон работает в фоновом режиме и обрабатывает все входящие запросы по порту 22. Для каждого соединения создается новая копия демона, который занимается только его обслуживанием.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Настройка сервера sshd

A

Конфигурация демона определяется файлом /etc/ssh/sshd_config. Он представляет собой набор действующих строк, пустых строк и строк-комментариев. Действующие строки файла содержат название параметра и его значение.
В конфигурационном файле указывается большое количество параметров, которые можно отнести к нескольким категориям:

Адреса. Интерфейс и порт, к которым привязан демон;
Журнализация. Опции, определяющие то, какая именно информация о работе демона должна регистрироваться и заноситься в журналы системы;
Управление ключами. Информация о том, в каких файлах находятся ключи, участвующие в аутентификации.
Аутентификация. Допустимые схемы аутентификации.
Дополнительные параметры. Опции, управляющие дополнительными функциями SSH, такими как переадресация портов, переадресация X11 и другие
Некоторые конфигурационные параметры могут быть переопределены опциями командной строки при вызове sshd.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Клиент ssh

A

Программа ssh предназначена для регистрации на удаленном хосте с использование протокола ssh и удаленного выполнения команд. Кроме того ssh позволяет выполнять туннелирование любых TCP-соединений внутри ssh-канала (port forwarding).

Синтаксис программы ssh:

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

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

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

Некоторые опции командной строки программы ssh

  • v – Выводить отладочную информацию о ходе процесса установки соединения. Настоятельно рекомендуется использовать ключ во время настройки службы.
  • f – Перейти в фоновый режим, сразу же после того, как пройден этап регистрации
  • l пользователь – Регистрироваться на удаленной системе как пользователь. Вместо ключа -l имяможно указывать перед именем хоста в форме пользователь@хост
  • p порт – Порт удаленного хоста, на котором доступен сервис SSH. По умолчанию используется порт 22.
  • L порт:хост:хостпорт – Перенаправить порт локального хоста на хостпорт удаленного хоста.
  • R порт:хост:хостпорт – Перенаправить порт удаленного локального хоста на хостпорт локального хоста.
  • o опции – Явно указать опции, которые перекрывают опции, заданные в конфигурационных файлах ssh.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Создание и установка асимметричных ключей SSH

A

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

Секретные ключи хранятся в файлах identity, id_dsa и id_rsa в локальном каталоге ~/.ssh (разные файлы для разных алгоритмов шифрования). Открытые ключи должны быть в файлах authorized_keys и authorized_keys2 в каталоге ~/.ssh на удаленном компьютере, на котором производится регистрация. В качестве домашнего рассматривается каталог пользователя, под именем которого выполняется регистрация. Файл authorized_keys используется для хранения открытых ключей для SSH1, а в authorized_keys2 — для SSH2.

ssh дает возможность использования одного из трех различных алгоритмов асимметричного шифрования RSA или DSA.

Типы ключей

rsa1 – Тип ключа RSA1, используемый в SSH версии 1
rsa – Тип ключа RSA, используемый в SSH версии 2
dsa – Тип ключа DSA, используемый в SSH версии 2

Для создания, преобразования и управления ключами аутентификации используется утилита ssh-keygen. Синтаксис программы:

ssh-keygen опции
Программа генерирует пару открытый ключ - секретный ключ. При этом она спрашивает, в какие файлы нужно записать ключи. По умолчанию секретный ключ записывается в ~/.ssh/identity (или ~/.ssh/id_rsa, ~/.ssh/id_dsa), а открытый в ~/.ssh/identity.pub.

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

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

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

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

Некоторые опции командной строки программы ssh-keygen

-t тип – Тип генерируемого ключа. Допустимые типы: rsa, rsa1 и dsa.
-p – Изменить парольную фразу
-l – Показать отпечаток (fingerprint) секретного ключа
[править]Опции ключа в ~/.ssh/authorized_keys
Для каждого открытого ключа в файлах ~/.ssh/authorized_keys можно выставить опции, ограничивающие возможности клиента, аутентифицировавшегося по данному ключу. Опции находятся перед ключем,

from=”список-шаблонов-через-запятую” - разрешает принимать соединения только с хостов, удовлетворяющих одному из шаблонов. В качестве шаблонов поддерживаются символы - ?, * и !
command=”команда” - при аутентификации по данному ключу разрешается запускать только указанную команду, а не то что указано пользователем - например, “echo this key disabled” или “dump -params” и обязательно использовать опцию no-pty для бинарной передачи данных
no-port-forwarding - запретить port-forwarding
no-X11-forwarding - запретить X11
no-user-rc - Запрещает выполнение файла ~/.ssh/rc после аутентификации (в RHEL не работает)
environment=”NAME=VALUE” - Принудительная установка переменных среды окружения. (в RHEL не работает)
no-agent-forwarding - запретить использование agent-forwarding
no-pty - запретить интерактивную оболочку
permitopen=”host:port” - (ограничить переназначение локального порта: ssh -L)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

scp

A

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

Синтаксис программы scp:

scp опции пользователь@хост1:файл1… пользователь@хост2:файл2
Команда устанавливает защищенное соединение между хостом1 и хостом2 и копирует файл1 хоста1 в файл2 хоста2. Любой из хостов может быть локальным. Если имя хоста не указано, подразумевается локальный хост.

Синтаксис использования команды scp напоминает синтаксис cp. Она так же обрабатывает большое количество аргументов, использует аналогичные ключи для рекурсивного копирования, для копирования атрибутов и т.д.

Опции программы scp

  • r – Выполнить рекурсивное копирование каталогов
  • p – Сохранить по возможности атрибуты файлов (права доступа, время модификации, время доступа) при копировании
  • C – Выполнять сжатие файлов при передаче
  • P порт – Соединяться с удаленным компьютером по порту порт
  • v – Сообщать отладочную информацию о ходе SSH-соединения
  • q – Не выдавать индикатор прогресса
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

SFTP

A

SFTP (SSH File Transfer Protocol) — SSH-протокол для передачи файлов. Он предназначен для копирования и выполнения других операций с файлами поверх надёжного и безопасного соединения. Как правило, в качестве базового протокола, обеспечивающего соединение, и используется протокол SSH2, но это не обязательно.

SFTP-сервер встроен в OpenSSH. Он реализуется с помощью программы sftp-server. SFTP-клиент sftp встроен в пакет OpenSSH. В качестве SFTP-клиента для Windows может использоваться WinSCP или PSFTP из пакета PuTTY.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Перенаправление TCP-портов (port forwarding) - SSH

A

У SSH есть возможность, известная как перенаправление портов (port forwarding), которая позволяет передавать по SSH-соединению данные других протоколов. Перенаправление портов позволяет передать подключение, сделанное на одном конце SSH-соединения передать на другой конец и продолжить сеанс связи оттуда.

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

Типичная задача, которая может решаться с помощью перенаправление TCP, это доступ к внутреннему серверу сети снаружи, через шлюз. Представьте, что у вас есть сеть, которая находится за UNIX-шлюзом, смотрящим в Интернет. У вас есть доступ к этому шлюзу по SSH. Вы находитесь в Интернете и хотите попасть на один из внутренних серверов сети, не имеет значения по какому протоколу, но пусть, например, по протоколу RDP. Возможности открыть порт при помощи трансляции адресов у вас на сервере нет (например, потому что у вас там нет прав root’а, а есть только доступ к оболочке).

Для решения такой задачи прекрасно подойдёт перенаправление TCP-порта с помощью SSH. Вы создаёте SSH-соединение на шлюз, внутри которого будет передавать трафик будущего соединения. Вы просите ssh выполнить перенаправление портов, в результате чего он открывает на прослушивание какой-либо локальный порт, обращение на который передаётся SSH-серверу на шлюз, который в свою очередь передаёт его серверу-получателю, то есть на RDP-сервер (причём делает это от своего имени; обратный адрес IP-пакетов будет адресом сервера).

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

Различают два вида перенаправления портов:

Локальное. Клиент принимает подключение и посылает запрос на инициирование соединения SSH-серверу, который в свою очередь устанавливает незащищённое соединение с адресатом;
Удаленное. Сервер принимает подключение и посылает запрос на инициирование соединения SSH-клиенту.
Фактически два этих режима отличаются только тем, с какой стороны будет инициироваться соединение: со стороны клиента или со стороны сервера.
Главным опциями, переводящими ssh в режим перенаправления портов являются -L (локальное перенаправление) и -R (удаленное перенаправление). Кроме того могут быть дополнительно полезны некоторые другие ключи.

Ключи ssh полезные при перенаправлении портов.

  • L порт:хост:хостпорт — Выполнить локальное перенаправление портов. При обращении на порт локальной машины будет создан туннель на порт хостпорт указанного хоста.
  • R порт:хост:хостпорт — Выполнить удалённое перенаправление. При обращении на порт удаленной машины будет создан SSH-туннель и соединение будет переадресовано на хостпорт указанного хоста.
  • N — Не выполнять команду удалённо. Используется только при перенаправлении портов.
  • f — Перейти в фоновый режим работы, сразу же после регистрации на удалённой системе.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

SSH через HTTP-прокси

A

Для этого необходимо чтобы на прокси-сервере был разрешён метод CONNECT. Обычно он разрешён как минимум на 443 порт. Если SSH-сервер с той стороны прокси работает на 443 порту, то обратиться на него через SSH не составит никакого труда. Существует несколько программ для этого, самая популярная — corkskrew.

После того как программа установлена, можно добавить в ~/.ssh/config такие строки:

Host *
ProxyCommand corkscrew http-proxy.example.com 8080 %h %p
Обращения на все хосты будут выполняться теперь через прокси http-proxy.example.com (порт 8080).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Протокол HTTP

A

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

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

Также HTTP часто используется как протокол передачи информации для других протоколов прикладного уровня, таких как SOAP, XML-RPC и WebDAV. В таком случае говорят, что протокол HTTP используется как «транспорт».

API многих программных продуктов также подразумевает использование HTTP для передачи данных — сами данные при этом могут иметь любой формат, например, XML или JSON.

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

Стартовая (начальная) строка запроса для HTTP 1.1 составляется по следующей схеме:

Метод URI HTTP/Версия

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

GET / HTTP/1.1

URI (Uniform Resource Identifier, унифицированный идентификатор ресурса) — путь до конкретного ресурса (например, документа), над которым необходимо осуществить операцию (например, в случае использования метода GET подразумевается получение ресурса). Некоторые запросы могут не относиться к какому-либо ресурсу, в этом случае вместо URI в стартовую строку может быть добавлена звёздочка (астериск, символ «*»). Например, это может быть запрос, который относится к самому веб-серверу, а не какому-либо конкретному ресурсу. В этом случае стартовая строка может выглядеть так:

OPTIONS * HTTP/1.1

Стартовая строка ответа имеет следующую структуру:

HTTP/Версия Код состояния Пояснение

Версия протокола здесь задаётся так же, как в запросе.

Код состояния (Status Code) — три цифры (первая из которых указывает на класс состояния), которые определяют результат совершения запроса. Например, в случае, если был использован метод GET, и сервер предоставляет ресурс с указанным идентификатором, то такое состояние задаётся с помощью кода 200. Если сервер сообщает о том, что такого ресурса не существует — 404. Если сервер сообщает о том, что не может предоставить доступ к данному ресурсу по причине отсутствия необходимых привилегий у клиента, то используется код 403. Спецификация HTTP 1.1 определяет 40 различных кодов HTTP, а также допускается расширение протокола и использование дополнительных кодов состояний.

Пояснение к коду состояния (Reason Phrase) — текстовое (но не включающее символы CR и LF) пояснение к коду ответа, предназначено для упрощения чтения ответа человеком. Пояснение может не учитываться клиентским программным обеспечением, а также может отличаться от стандартного в некоторых реализациях серверного ПО.

Сам по себе протокол HTTP не предполагает использование шифрования для передачи информации. Тем не менее, для HTTP есть распространённое расширение, которое реализует упаковку передаваемых данных в криптографический протокол SSL или TLS.

Название этого расширения — HTTPS (HyperText Transfer Protocol Secure). Для HTTPS-соединений обычно используется TCP-порт 443. HTTPS широко используется для защиты информации от перехвата, а также, как правило, обеспечивает защиту от атак вида man-in-the-middle — в том случае, если сертификат проверяется на клиенте, и при этом приватный ключ сертификата не был скомпрометирован, пользователь не подтверждал использование неподписанного сертификата, и на компьютере пользователя не были внедрены сертификаты центра сертификации злоумышленника.

Протокол HTTP предполагает достаточно большое количество возможностей для расширения. В частности, спецификация HTTP 1.1 предполагает возможность использования заголовка Upgrade для переключения на обмен данными по другому протоколу. Запрос с таким заголовком отправляется клиентом. Если серверу требуется произвести переход на обмен данными по другому протоколу, то он может вернуть клиенту ответ со статусом «426 Upgrade Required», и в этом случае клиент может отправить новый запрос, уже с заголовком Upgrade.

Такая возможность используется, в частности, для организации обмена данными по протоколу WebSocket (протокол, описанный в спецификации RFC 6455, позволяющий обеим сторонам передавать данные в нужный момент, без отправки дополнительных HTTP-запросов): стандартное «рукопожатие» (handshake) сводится к отправке HTTP-запроса с заголовком Upgrade, имеющим значение «websocket», на который сервер возвращает ответ с состоянием «101 Switching Protocols», и далее любая сторона может начать передавать данные уже по протоколу WebSocket.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

принципы IP

A

IP implements packet-switched networking. It has a concept of hosts, which are machines. The IP protocol specifies how datagrams (packets) are sent between these hosts.

A packet is a chunk of binary data that has a source host and a destination host. An IP network will then simply transmit the packet from the source to the destination. One important aspect of IP is that packets are delivered using best effort. A packet may be lost along the way and never reach the destination. Or it may get duplicated and arrive multiple times at the destination.

Each host in an IP network has an address – the so-called IP address. Each packet contains the source and destination hosts’ addresses. The IP is responsible for routing datagrams – as the IP packet travels through the network, each node (host) that it travels through looks at the destination address in the packet to figure out in which direction the packet should be forwarded.

Today, most packages are still IPv4 (Internet Protocol version 4), where each IPv4 address is 32 bits long. They’re most often written in dotted-decimal notation, like so: 198.51.100.42

The newer IPv6 standard is slowly gaining traction. It has a larger address space: its addresses are 128 bits long. This allows for easier routing as the packets travel through the network. And since there are more available addresses, tricks such as network address translation are no longer necessary. IPv6 addresses are represented in the hexadecimal system and divided into eight groups separated by colons, e.g. 2001:0db8:85a3:0042:1000:8a2e:0370:7334.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

IPv4 Header

A

The header is 20 bytes long (without options, which are rarely used).

The most interesting parts of the header are the source and destination IP addresses. Aside from that, the version field will be set to 4 – it’s IPv4. And the protocol field specifies which protocol the payload is using. TCP’s protocol number is 6. The total length field specified is the length of the entire packet – header plus payload.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

IPv6 Header

A

IPv6 uses addresses that are 128 bits long.
The IPv6 header has a fixed length of 40 bytes.
The source and destination addresses are again the most interesting fields. In IPv6, the next header field specifies what data follows the header. IPv6 allows chaining of headers inside the packet. Each subsequent IPv6 header will also have a next header field until the actual payload is reached. When the next header field, for example, is 6 (TCP’s protocol number), the rest of the packet will be TCP data.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

IP fragmentation

A

In IPv4, packets (datagrams) can get fragmented. The underlying transport layer will have an upper limit to the length of packet it can support. In IPv4, a router may fragment a packet if it gets routed onto an underlying data link for which the packet would otherwise be too big. These packets will then get reassembled at the destination host. The sender can decide to disallow routers to fragment packets, in which case they’ll send a Packet Too Big ICMP back to the sender.

In IPv6, a router will always drop the packet and send back a Packet Too Big ICMP6 message to the sender. The end points use this to do a path MTU discovery to figure out what the optimal so-called maximum transfer unit (MTU) along the path between the two hosts is. Only when the upper layer has a minimum payload size that is too big for this MTU will IPv6 use fragmentation. With TCP over IPv6, this is not the case.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

TCP

A

TCP is built on top of IP. The Transmission Control Protocol provides reliable, ordered, error-checked delivery of a stream of data between programs. With TCP, an application running on one device can send data to an application on another device and be sure that the data arrives there in the same way that it was sent.
With TCP, applications establish connections between each other. A TCP connection is duplex and allows data to flow in both directions. The applications on either end do not have to worry about the data being split up into packets, or the fact that the packet transport is best effort. TCP guarantees that the data will arrive at the other end in pristine condition.

A typical use case of TCP is HTTP. Our web browser (application 1) connects to a web server (application 2). Once the connection is made, the browser can send a request through the connection, and the web server can send a response back through the same connection.

Multiple applications on the same host can use TCP simultaneously. To uniquely identify an application, TCP has a concept of ports. A connection between two applications has a source IP address and a source port on one end, and a destination IP address and a destination port at the other end. This pair of addresses, plus a port for either end, uniquely identifies the connection.

A web server using HTTPS will listen on port 443. The browser will use a so-called ephemeral port as the source port and then use TCP to establish a connection between the two address-port pairs.

TCP runs unmodified on top of both IPv4 and IPv6. The Protocol (IPv4) or Next Header (IPv6) field will be set to 6, which is the protocol number for TCP.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

TCP Segments

A

The data stream that flows between hosts is cut up into chunks, which are turned into TCP segments. The TCP segment then becomes the payload of an IP packet.

Each TCP segment has a header and a payload. The payload is the actual data chunk to be transmitted. The TCP segment header first and foremost contains the source and destination port number – the source and destination addresses are already present in the IP header.

The header also contains sequence and acknowledgement numbers and quite a few other fields which are all used by TCP to manage the connection.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

TCP Connections

A

In TCP, a connection is always established from one host to another. Hence, there are two different roles in connection setup: one end (e.g. the web server) is listening for connections, while the other end (e.g. our app) connects to the listening application (e.g. the web server). The server performs a so-called passive open – it starts listening. The client performs a so-called active open toward the server.

Connection setup happens through a three-way handshake. It works like this:

The client sends a SYN to the server with a random sequence number, A
The server replies with a SYN-ACK with an acknowledgment number of A+1 and a random sequence number, B
The client sends an ACK to the server with an acknowledgement number of B+1 and a sequence number of A+1
SYN is short for synchronize sequence numbers. Once data flows between both ends, each TCP segment has a sequence number. This is how TCP makes sure that all parts arrive at the other end, and that they’re put together in the right order. Before communication can start, both ends need to synchronize the sequence number of the first segments.
ACK is short for acknowledgment. When a segment arrives at one of the ends, that end will acknowledge the receipt of that segment by sending an acknowledgment for the sequence number of the received segment.

When the connection is created, both ends can send data to the other end. Each segment that is sent has a sequence number corresponding to the number of bytes sent so far. The receiving end will acknowledge packets as they are received by sending back segments with the corresponding ACK in the header.
Flow control is about making sure that the sending side doesn’t send data faster than the receiver (at either end) can process it. The receiver sends a so-called receive window, which tells the sender how much more data the receiver can buffer.
The basic idea is that the sender side looks at the acknowledgments it gets back. This is a very tricky business and there are various tradeoffs to be made. Remember that the underlying IP packets can arrive out of order, not at all, or twice. The sender needs to estimate what the round-trip time is and use that to figure out if it should have received an acknowledgement already. Retransmitting packets is obviously costly, but not retransmitting causes the connection to stall for a while, and the load on the network is likely to be very dynamic. The TCP algorithms need to constantly adapt to the current situation.

The important thing to note is that a TCP connection is a very lively and flexible thing. Aside from the actual data flow, both ends constantly send hints and updates back and forth to continuously fine-tune the connection.

Because of this tuning, TCP connections that are short-lived can be very inefficient. When a connection is first created, the TCP algorithms still don’t know what the conditions of the network are. And toward the end of the connection lifetime, there’s less information flowing back to the sender, which therefore has a harder time estimating how things are moving along.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

XML

A

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

С логической точки зрения документ состоит из комментариев (англ. comments), объявлений (англ. declarations), элементов (англ. elements), ссылок на сущности (англ. character references) и инструкций обработки (англ. processing instructions). Всё это в документе структуризуется разметкой (англ. markup).
Документ состоит из сущностей, содержание которых — символы. Все они разделены на два типа: символьные данные (англ. character data) и разметки. К разметке принадлежат: теги (англ. tags), обозначающие границы элементов, объявления и инструкции обработки, включая их атрибуты (англ. attributes), ссылки на сущности, комментарии, а также последовательности символов, обрамляющие секции «CDATA». Часть документа, не принадлежащая разметке, составляет символьные данные документа.
Все составляющие части документа обобщаются в пролог и корневой элемент. Корневой элемент — обязательная часть документа, составляющая всю его суть (пролог, вообще говоря, может отсутствовать). Может включать (а может не включать) вложенные в него элементы и символьные данные, а также комментарии. Вложенные в корневой элемент элементы, в свою очередь, могут включать вложенные в них элементы, символьные данные и комментарии, и так далее. Пролог может включать объявления, инструкции обработки, комментарии. Его следует начинать с объявления XML, хотя в определённой ситуации допускается отсутствие этого объявления.

Элементы документа должны быть правильно вложены: любой элемент, начинающийся внутри другого элемента (то есть любой элемент документа, кроме корневого), должен заканчиваться внутри элемента, в котором он начался. Символьные данные могут встречаться внутри элементов как непосредственно так и в специальных секциях «CDATA». Объявления, инструкции обработки и элементы могут иметь связанные с ними атрибуты. Атрибуты используются для связывания с логической единицей текста пар имя-значение.
Объявление XML указывает версию языка, на которой написан документ. Поскольку интерпретация содержимого документа зависит от версии языка, то Спецификация предписывает начинать документ с объявления XML. В первой (1.0) версии языка использование объявления не было обязательным, в последующих версиях оно обязательно. Таким образом, версия языка определяется из объявления, и если объявление отсутствует, то принимается версия 1.0.

Кроме версии XML,объявление может также содержать информацию о кодировке документа
Для объявления типа документа существует специальная инструкция !DOCTYPE. Она позволяет задать при помощи языка DTD, какие в документ входят элементы, каковы их атрибуты, какие сущности могут использоваться и кое-что ещё.
После XML-объявления могут следовать комментарии, инструкции обработки или же пустые пространства[11], но затем идёт Объявления типа документа, где «Name» — имя корневого тега, «ExternalID» — внешний идентификатор, а «intSubset» — объявление разметки или же ссылка на сущность. Как гласит спецификация, если внешний идентификатор объявляется вместе с внутренним объявлением, то последнее идёт перед первым
Элемент (англ. element) является понятием логической структуры документа. Каждый документ содержит один или несколько элементов. Границы элементов представлены начальным и конечным тегами. Имя элемента в начальном и конечном тегах элемента должно совпадать. Элемент может быть также представлен тегом пустого, то есть не включающего в себя другие элементы и символьные данные, элемента.
Для решения задачи преобразования документа XML в другую схему или другой формат предназначен язык XSLT.
Для форматированного документа (документа, подготовленного к визуализации) предназначен формат XSL-FO.
XPath — синтаксис для адресации содержимого документа, представленного в форме дерева. Выражения XPath используются в языке XQuery. Выражения XPath, вообще говоря, могут использоваться в любом контексте, где уместно использовать формальные ссылки на элементы дерева, в частности, в качестве параметров для методов интерфейсов доступа к документу.

XQuery — язык программирования, ориентированный на работу с документами.
Для чтения XML есть три варианта API[13].

Событийный API (event-driven API, push-style API) — XML-процессор читает XML; при определённом событии (появлении открывающего или закрывающего тега, текстовой строки, атрибута) вызывается callback-функция.

+ Расходует мало памяти[13].
+ При обработке огромного XML есть стандартная точка, позволяющая мгновенно остановить обработчик[13].
− Крайне сложен для прикладного программиста: приходится держать в памяти информацию, в каком месте документа мы находимся.
+ Библиотека проста в программировании.
− Затруднена поддержка перекрёстных ссылок: надо организовать временное хранение строковых ссылок, а когда документ будет считан — преобразовать идентификаторы в указатели.
− При ошибке в XML в памяти остаётся полусозданная структура предметной отрасли; программист должен своими руками корректно уничтожить её.
− API только для чтения, для записи потребуется другой API.
± Естественный выбор, когда из огромного XML надо извлечь немного данных[13].
± Естественный выбор, когда XML надо преобразовать в структуру предметной отрасли[13].
Примеры библиотек: SAX, Expat

Потоковый API (также pull-style API) — устроен на манер потоков ввода-вывода.
+ Расходует мало памяти.
± Информация, в каком месте документа мы находимся, неявно задаётся местом в потоке выполнения. Это серьёзно упрощает работу прикладного программиста. На продуманных API объём кода приближается к таковому для DOM.
− Библиотека сложна в программировании.
− Сложно сделать, чтобы «почти верные» XML с перепутанным порядком тегов работали правильно.
− Затруднена поддержка перекрёстных ссылок.
− При ошибке в XML в памяти остаётся полусозданная структура предметной отрасли; программист должен своими руками корректно уничтожить её.
− API только для чтения, для записи потребуется другой API.
Примеры библиотек: StAX

Объектный API (Document Object Model, DOM, «объектная модель документа») — считывает XML и воссоздаёт его в памяти в виде объектной структуры.

− Расходует много памяти — намного больше, чем сам XML занимает на диске. На pugixml расход памяти втрое и более превышает длину XML.
+ Прост для прикладного программиста.
+ Библиотека проста в программировании.
+ Зачастую удаётся распознать «почти верные» XML с перепутанным порядком тегов.
+ Позволяет произвольный доступ к XML[13]. Это, например, упрощает работу с перекрёстными ссылками.
+ При ошибке в XML в памяти остаётся полусозданная структура XML, которая будет автоматически уничтожена самой библиотекой.
+ Общий API для чтения и записи.
± Естественный выбор, когда объектом предметной области является сам XML: например, в веб-браузере[13], XML-редакторе, в импортёре к программе-локализатору, который извлекает строки из XML произвольной структуры.
± Естественный выбор, когда нужно загрузить XML, слегка переработать и сохранить[13]. Те части, которые трогать не нужно, не требуют никакого кода.
Примеры библиотек: JDOM, TinyXML, pugixml

API прямой записи записывает XML тег за тегом, атрибут за атрибутом.

+ Быстр, нет промежуточных объектов.
− Примитивная библиотека может делать неоптимальный XML (например, вместо ). Работающая оптимально намного сложнее в программировании.
− Непригоден для отдельных специфических задач.
− Если структуры предметной области работают ненадёжно, без специальных мер (записать в память или в другой файл, потом переименовать) можно остаться с «упавшей» программой и потерянным файлом.
− При ошибке программиста может получиться синтаксически некорректный XML.
− API только для записи, для чтения потребуется другой API.

Объектный API, он же Document Object Model.

− Создаёт объектную структуру для XML, что может отнять памяти больше, чем структура предметной отрасли.
± Универсален (впрочем, в большинстве задач преимущества над хорошо проработанным API прямой записи нет — в отличие от чтения).
+ Даже если структуры предметной области работают ненадёжно, а программист не предусмотрел никакой «защиты», единственный сценарий, когда файл перезаписывается на неполный — нехватка места на диске.
+ Общий API для записи и чтения.
Примеры библиотек: те же, что и для чтения XML методом DOM.

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

HTML

A

Язык HTML интерпретируется браузерами; полученный в результате интерпретации форматированный текст отображается на экране монитора компьютера или мобильного устройства.

Язык HTML до 5-й версии определялся как приложение SGML (стандартного обобщённого языка разметки по стандарту ISO 8879). Спецификации HTML5 формулируются в терминах DOM (объектной модели документа).

Язык XHTML является более строгим вариантом HTML, он следует синтаксису XML и является приложением языка XML в области разметки гипертекста.

Во всемирной паутине HTML-страницы, как правило, передаются браузерам от сервера по протоколам HTTP или HTTPS, в виде простого текста или с использованием шифрования.

Любой документ на языке HTML представляет собой набор элементов, причём начало и конец каждого элемента обозначается специальными пометками — тегами. Элементы могут быть пустыми, то есть не содержащими никакого текста и других данных. В этом случае обычно не указывается закрывающий тег (например, тег переноса строки <br></br> — одиночный и закрывать его не нужно) . Кроме того, элементы могут иметь атрибуты, определяющие какие-либо их свойства (например, атрибут href=” у ссылки). Атрибуты указываются в открывающем теге.
Кроме элементов, в HTML-документах есть и сущности (англ. entities) — «специальные символы». Сущности начинаются с символа амперсанда и имеют вид &имя; или NNNN;, где NNNN — код символа в Юникоде в десятичной системе счисления.
Каждый HTML-документ, отвечающий спецификации HTML какой-либо версии, должен начинаться со строки объявления версии HTML >
Далее обозначается начало и конец документа тегами и соответственно. Внутри этих тегов должны находиться теги заголовка () и тела () документа.

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

Элемент

 может располагаться либо в <head>, либо в <body>-элементе (перед закрывающим </body>).

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

Форма задаётся с помощью элемента <form>, внутри которого и располагаются элементы управления. Кроме общих для HTML атрибутов, в <form> могут присутствовать следующие:
action (действие) — обязательный атрибут (в HTML5 — нет), содержащий URI обработчика формы;
method (метод отправки формы) — атрибут, принимающий значения GET (по умолчанию) или POST;
enctype (тип кодирования для содержимого) — по умолчанию application/x-www-form-urlencoded (всегда для метода GET), но обычно употребляется multipart/form-data;
accept — список MIME-типов для загрузки файлов;
name — имя формы;
onsubmit — обработчик события «форма отправлена» (для скриптов);
onreset — обработчик события: «форма очищена» (тоже для скриптов);
accept-charset список поддерживаемых наборов символов.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

JSON

A

JavaScript Object Notation
За счёт своей лаконичности по сравнению с XML формат JSON может быть более подходящим для сериализации сложных структур. Применяется в веб-приложениях как для обмена данными между браузером и сервером (AJAX), так и между серверами (программные HTTP-сопряжения).

Поскольку формат JSON является подмножеством синтаксиса языка JavaScript, то он может быть быстро десериализован встроенной функцией eval().
JSON-текст представляет собой (в закодированном виде) одну из двух структур:

Набор пар ключ: значение. В различных языках это реализовано как запись, структура, словарь, хеш-таблица, список с ключом или ассоциативный массив. Ключом может быть только строка (регистрозависимая: имена с буквами в разных регистрах считаются разными[4]), значением — любая форма.
Упорядоченный набор значений. Во многих языках это реализовано как массив, вектор, список или последовательность.
Структуры данных, используемые JSON, поддерживаются любым современным языком программирования, что и позволяет применять JSON для обмена данными между различными языками программирования и программными системами.

В качестве значений в JSON могут быть использованы:

запись — это неупорядоченное множество пар ключ:значение, заключённое в фигурные скобки «{ }». Ключ описывается строкой, между ним и значением стоит символ «:». Пары ключ-значение отделяются друг от друга запятыми.
массив (одномерный) — это упорядоченное множество значений. Массив заключается в квадратные скобки «[ ]». Значения разделяются запятыми. Массив может быть пустым, т.е. не содержать ни одного значения.
число (целое или вещественное).
литералы true (логическое значение «истина»), false (логическое значение «ложь») и null.
строка — это упорядоченное множество из нуля или более символов юникода, заключённое в двойные кавычки. Символы могут быть указаны с использованием escape-последовательностей, начинающихся с обратной косой черты «\» (поддерживаются варианты ', ", \, \/, \t, \n, \r, \f и \b), или записаны шестнадцатеричным кодом в кодировке Unicode в виде \uFFFF.
Строка очень похожа на литерал одноимённого типа данных в языке Javascript. Число тоже очень похоже на Javascript-число, за исключением того, что используется только десятичный формат (с точкой в качестве разделителя). Пробелы могут быть вставлены между любыми двумя синтаксическими элементами.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

nginx

A

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

HTTP-сервер
обслуживание неизменяемых запросов, индексных файлов, автоматическое создание списка файлов, кеш дескрипторов открытых файлов
акселерированное проксирование без кэширования, простое распределение нагрузки и отказоустойчивость
поддержка кеширования при акселерированном проксировании и FastCGI
акселерированная поддержка FastCGI и memcached-серверов, простое распределение нагрузки и отказоустойчивость
модульность, фильтры, в том числе сжатие (gzip), byte-ranges (докачка), chunked-ответы, HTTP-аутентификация, SSI-фильтр
несколько подзапросов на одной странице, обрабатываемые в SSI-фильтре через прокси или FastCGI, выполняются параллельно
поддержка SSL
поддержка PSGI, WSGI
экспериментальная поддержка встроенного Perl

SMTP/IMAP/POP3-прокси сервер
перенаправление пользователя на SMTP/IMAP/POP3-бэкенд с использованием внешнего HTTP-сервера аутентификации
простая аутентификация (LOGIN, USER/PASS)
поддержка SSL и STARTTLS

В nginx рабочие процессы обслуживают одновременно множество соединений, мультиплексируя их вызовами операционной системы select, epoll (Linux) и kqueue (FreeBSD). Рабочие процессы выполняют цикл обработки событий от дескрипторов (см. Событийно-ориентированное программирование). Полученные от клиента данные разбираются с помощью конечного автомата. Разобранный запрос последовательно обрабатывается цепочкой модулей, задаваемой конфигурацией. Ответ клиенту формируется в буферах, которые хранят данные либо в памяти, либо указывают на отрезок файла. Буфера объединяются в цепочки, определяющие последовательность, в которой данные будут переданы клиенту. Если операционная система поддерживает эффективные операции ввода-вывода, такие как writev и sendfile, то nginx применяет их по возможности.

У nginx есть один главный и несколько рабочих процессов. Основная задача главного процесса — чтение и проверка конфигурации и управление рабочими процессами. Рабочие процессы выполняют фактическую обработку запросов. nginx использует модель, основанную на событиях, и зависящие от операционной системы механизмы для эффективного распределения запросов между рабочими процессами. Количество рабочих процессов задаётся в конфигурационном файле и может быть фиксированным для данной конфигурации или автоматически устанавливаться равным числу доступных процессорных ядер
Как работают nginx и его модули, определяется в конфигурационном файле. По умолчанию, конфигурационный файл называется nginx.conf и расположен в каталоге /usr/local/nginx/conf, /etc/nginx или /usr/local/etc/nginx.

Чтобы запустить nginx, нужно выполнить исполняемый файл. Когда nginx запущен, им можно управлять, вызывая исполняемый файл с параметром -s. Используйте следующий синтаксис:

nginx -s сигнал
Где сигнал может быть одним из нижеследующих:

stop — быстрое завершение
quit — плавное завершение
reload — перезагрузка конфигурационного файла
reopen — переоткрытие лог-файлов

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

Посылать сигналы процессам nginx можно также средствами Unix, такими как утилита kill. В этом случае сигнал отправляется напрямую процессу с данным ID. ID главного процесса nginx записывается по умолчанию в файл nginx.pid в каталоге /usr/local/nginx/logs или /var/run.

Для просмотра списка всех запущенных процессов nginx может быть использована утилита ps, например, следующим образом:

ps -ax | grep nginx

nginx состоит из модулей, которые настраиваются директивами, указанными в конфигурационном файле. Директивы делятся на простые и блочные. Простая директива состоит из имени и параметров, разделённых пробелами, и оканчивается точкой с запятой (;). Блочная директива устроена так же, как и простая директива, но вместо точки с запятой после имени и параметров следует набор дополнительных инструкций, помещённых внутри фигурных скобок ({ и }). Если у блочной директивы внутри фигурных скобок можно задавать другие директивы, то она называется контекстом (примеры: events, http, server и location).

Директивы, помещённые в конфигурационном файле вне любого контекста, считаются находящимися в контексте main. Директивы events и http располагаются в контексте main, server — в http, а location — в server.

Часть строки после символа # считается комментарием.

В общем случае конфигурационный файл может содержать несколько блоков server, различаемых по портам, на которых они слушают, и по имени сервера. Определив, какой server будет обрабатывать запрос, nginx сравнивает URI, указанный в заголовке запроса, с параметрами директив location, определённых внутри блока server.

Итоговая конфигурация блока server должна выглядеть следующим образом:

server {
location / {
root /data/www;
}

    location /images/ {
        root /data;
    }
}
Это уже работающая конфигурация сервера, слушающего на стандартном порту 80 и доступного на локальном компьютере по адресу http://localhost/. В ответ на запросы, URI которых начинаются с /images/, сервер будет отправлять файлы из каталога /data/images. Например, на запрос http://localhost/images/example.png nginx отправит в ответ файл /data/images/example.png. Если же этот файл не существует, nginx отправит ответ, указывающий на ошибку 404. Запросы, URI которых не начинаются на /images/, будут отображены на каталог /data/www. Например, в результате запроса http://localhost/some/example.html в ответ будет отправлен файл /data/www/some/example.html.

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

server {
listen 8080;
root /data/up1;

location / {
} } Это будет простой сервер, слушающий на порту 8080 (ранее директива listen не указывалась, потому что использовался стандартный порт 80) и отображающий все запросы на каталог /data/up1 в локальной файловой системе. Создайте этот каталог и положите в него файл index.html. Обратите внимание, что директива root помещена в контекст server. Такая директива root будет использована, когда директива location, выбранная для выполнения запроса, не содержит собственной директивы root. Далее, используйте конфигурацию сервера из предыдущего раздела и видоизмените её, превратив в конфигурацию прокси-сервера. В первый блок location добавьте директиву proxy_pass, указав протокол, имя и порт проксируемого сервера в качестве параметра (в нашем случае это http://localhost:8080):

server {
location / {
proxy_pass http://localhost:8080;
}

    location /images/ {
        root /data;
    }
}
Мы изменим второй блок location, который на данный момент отображает запросы с префиксом /images/ на файлы из каталога /data/images так, чтобы он подходил для запросов изображений с типичными расширениями файлов. Изменённый блок location выглядит следующим образом:

location ~ .(gif|jpg|png)$ {
root /data/images;
}
Параметром является регулярное выражение, дающее совпадение со всеми URI, оканчивающимися на .gif, .jpg или .png. Регулярному выражению должен предшествовать символ ~. Соответствующие запросы будут отображены на каталог /data/images.

Когда nginx выбирает блок location, который будет обслуживать запрос, то вначале он проверяет директивы location, задающие префиксы, запоминая location с самым длинным подходящим префиксом, а затем проверяет регулярные выражения. Если есть совпадение с регулярным выражением, nginx выбирает соответствующий location, в противном случае берётся запомненный ранее location.
nginx можно использовать для перенаправления запросов на FastCGI-серверы. На них могут исполняться приложения, созданные с использованием разнообразных фреймворков и языков программирования, например, PHP.

Базовая конфигурация nginx для работы с проксируемым FastCGI-сервером включает в себя использование директивы fastcgi_pass вместо директивы proxy_pass, и директив fastcgi_param для настройки параметров, передаваемых FastCGI-серверу. Представьте, что FastCGI-сервер доступен по адресу localhost:9000. Взяв за основу конфигурацию прокси-сервера из предыдущего раздела, замените директиву proxy_pass на директиву fastcgi_pass и измените параметр на localhost:9000. В PHP параметр SCRIPT_FILENAME используется для определения имени скрипта, а в параметре QUERY_STRING передаются параметры запроса.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Agile

A
  • разработка ведется короткими циклами (итерациями), продолжительностью 1-4 недели;
  • в конце каждой итерации заказчик получает ценное для него приложение (или его часть), которое можно использовать в бизнесе;
  • команда разработки сотрудничает с Заказчиком в ходе всего проекта;
  • изменения в проекте приветствуются и быстро включаются в работу.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Scrum

A

В скрам используется всего четыре артефакта:

Product Backlog
Sprint Backlog
Sprint Goal
Sprint Burndown Chart.

Product backlog:
Это список всех требований, которые нужно сделать по проекту. Когда в Backlog’e нет требований, проект считается завершенным.
Все требования описаны по единому шаблону, который называют User Story (пользовательская история).
Требования составлены так, что очевидно и понятно, какую ценность они представляют для пользователя
Требования отсортированы по приоритетам, которые пересматриваются каждый спринт.

Sprint backlog:
Это список всех требований, которые нужно сделать в ближайший спринт.
В течение спринта, новые требования не могут появится в Sprint backlog.
Все требования должны быть разделены на задачи и оценены.
Sprint Backlog – это обязательство команды: что они должны выполнить за ближайшие 2 недели. Каждое требование разделено на задачи, которые представлены на Kanban-доске.

Sprint Goal
это краткое описание того, ради чего выполняется данный спринт.
цель на спринт помогает команде принимать обоснованные решения.
Этот артефакт необходим для того, чтобы команда проекта могла самостоятельно принимать решение в случае появления альтернативных путей решения задачи. Чтобы решения команды были осознанными, Product Owner определяет цель спринта.

Sprint Burndown Chart
дословно “диаграмма сгорания”
в качестве “сгорающих” элементов выступают человеко-часы или идеальные единицы (Story Points).
диаграмма обновляется каждый раз, когда завершается какая-либо задача.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Рефакторинг

A

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

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

Рефакторинг улучшает композицию программного обеспечения, облегчает понимание программного обеспечения, помогает найти ошибки, позволяет быстрее писать программы

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

Методы рефакторинга
Инкапсуляция поля (Encapsulate Field);
Выделение класса (Extract Class);
Выделение интерфейса (Extract Interface);
Выделение локальной переменной (Extract Local Variable);
Выделение метода (Extract Method);
Генерализация типа (Generalize Type);
Встраивание (Inline);
Введение фабрики (Introduce Factory);
Введение параметра (Introduce Parameter);
Подъём поля/метода (Pull Up);
Спуск поля/метода (Push Down);
Замена условного оператора полиморфизмом (Replace Conditional with Polymorphism);

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

принципы ООП

A
  • Данные структурируются в виде объектов, каждый из которых имеет определенный тип, то есть принадлежит к какому-либо классу.
  • Классы – результат формализации решаемой задачи, выделения главных ее аспектов.
  • Внутри объекта инкапсулируется логика работы с относящейся к нему информацией.
  • Объекты в программе взаимодействуют друг с другом, обмениваются запросами и ответами.
    При этом объекты одного типа сходным образом отвечают на одни и те же запросы.
  • Объекты могут организовываться с более сложные структуры, например, включать другие объекты или наследовать от одного или нескольких объектов.

Главное

  • Инкапсулируйте все, что может изменяться;
  • Уделяйте больше внимания интерфейсам, а не их реализациям;
  • Каждый класс в вашем приложении должен иметь только одно назначение;
  • Классы — это их поведение и функциональность.

Базовые принципы ООП

  • Абстракция — отделение концепции от ее экземпляра;
  • Полиморфизм — реализация задач одной и той же идеи разными способами;
  • Наследование — способность объекта или класса базироваться на другом объекте или классе. Это главный механизм для повторного использования кода. Наследственное отношение классов четко определяет их иерархию;
  • Инкапсуляция — размещение одного объекта или класса внутри другого для разграничения доступа к ним.

Используйте следующее вместе с наследованием
- Делегация — перепоручение задачи от внешнего объекта внутреннему;
- Композиция — включение объектом-контейнером объекта-содержимого и управление его поведением; последний не может существовать вне первого;
- Агрегация — включение объектом-контейнером ссылки на объект-содержимое; при уничтожении первого последний продолжает существование
.
Не повторяйся (Don’t repeat yourself — DRY)
Избегайте повторного написания кода, вынося в абстракции часто используемые задачи и данные. Каждая часть вашего кода или информации должна находиться в единственном числе в единственном доступном месте.

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

Принцип открытости/закрытости
Программные сущности должны быть открыты для расширения, но закрыты для изменений.

Принцип подстановки Барбары Лисков
Методы, использующие некий тип, должны иметь возможность использовать его подтипы, не зная об этом.

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Императивное и декларативное программирование

A

Императивный подход (как) - дается набор шагов, которые необходимо выполнить
Декларативный подход (что) - дается конечная цель: предполагается, что уже есть знания и инструменты, как ее достичь
многие декларативные подходы имеют определённый слой императивных абстракций
Императивные: C, C++, Java.
Декларативные: SQL, HTML.
Смешанные (могут быть таковыми): JavaScript, C#, Python.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Замыкание

A

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

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

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

В случае замыкания ссылки на переменные внешней функции действительны внутри вложенной функции до тех пор, пока работает вложенная функция, даже если внешняя функция закончила работу, и переменные вышли из области видимости.[1]

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

# Реализация с помощью именованных функций:
def make_adder(x):
    def adder(n):
        return x + n # захват переменной "x" из внешнего контекста
    return adder
# То же самое, но через безымянные функции:
make_adder = lambda x: (
    lambda n: x + n
)
f = make_adder(10)
print f(5) # 15
print f(-1) # 9
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Интроспекция и рефлексия

A

Интроспекция — это способность программы исследовать тип или свойства объекта во время работы программы. Как мы уже упоминали, вы можете поинтересоваться, каков тип объекта, является ли он экземпляром класса. Некоторые языки даже позволяют узнать иерархию наследования объекта. Возможность интроспекции есть в таких языках, как Ruby, Java, PHP, Python, C++ и других. В целом, инстроспекция — это очень простое и очень мощное явление.
В Python самой распространённой формой интроспекции является использование метода dir для вывода списка атрибутов объекта:

Python

class foo(object):
  def \_\_init\_\_(self, val):
    self.x = val
  def bar(self):
    return self.x

dir(foo(5))
=> [‘__class__’, ‘__delattr__’, ‘__dict__’, ‘__doc__’, ‘__getattribute__’, ‘__hash__’, ‘__init__’, ‘__module__’,
‘__new__’, ‘__reduce__’, ‘__reduce_ex__’, ‘__repr__’, ‘__setattr__’, ‘__str__’, ‘__weakref__’, ‘bar’, ‘x’]

Рефлексия — это способность компьютерной программы изучать и модифицировать свою структуру и поведение (значения, мета-данные, свойства и функции) во время выполнения. Простым языком: она позволяет вам вызывать методы объектов, создавать новые объекты, модифицировать их, даже не зная имён интерфейсов, полей, методов во время компиляции. Из-за такой природы рефлексии её труднее реализовать в статически типизированных языках, поскольку ошибки типизации возникают во время компиляции, а не исполнения программы. Тем не менее, она возможна, ведь такие языки, как Java, C# и другие допускают использование как интроспекции, так и рефлексии (но не C++, он позволяет использовать лишь интроспекцию).

По той же причине рефлексию проще реализовать в интерпретируемых языках, поскольку когда функции, объекты и другие структуры данных создаются и вызываются во время работы программы, используется какая-то система распределения памяти. Интерпретируемые языки обычно предоставляют такую систему по умолчанию, а для компилируемых понадобится дополнительный компилятор и интерпретатор, который следит за корректностью рефлексии.
Это очень мощный принцип, который к тому же является обычной практикой в метапрограммировании. Тем не менее, при использовании рефлексии нужно быть очень внимательным. Хотя у неё и есть свои преимущества, код, использующий рефлексию, значительно менее читаем, он затрудняет отладку, а также открывает двери по-настоящему плохим вещами, например, инъекции кода через выражения eval.

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

Рассмотрим следующий пример кода на Python, который принимает данные из стороннего источника в Сети (это одна из причин, по которой люди пользуются eval-выражениями):

session[‘authenticated’] = False
data = get_data()
foo = eval(data)
Защита программы будет нарушена, если кто-то передаст в метод get_data() такую строку:

“session.update(authenticated=True)”
Для безопасного использования eval-утверждений нужно сильно ограничивать формат входных данных — и обычно это лишь занимает лишнее время.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Компилируемые и интерпретируемые языки

A

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

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

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

Низкоуровневые языки как правило являются компилируемыми, поскольку эффективность обычно ставится выше кроссплатформенности. Кроме того, компилируемые языки дают разработчику гораздо больше возможностей в плане контроля аппаратного обеспечения, например, управления памятью и использованием процессора. Примерами компилируемых языков являются C, C++, Erlang, Haskell и более современные языки, такие как Rust и Go.

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

В отличие от компилируемых языков, интерпретируемым для исполнения программы не нужен машинный код; вместо этого программу построчно исполнят интерпретаторы. Раньше процесс интерпретации занимал очень много времени, но с приходом таких технологий, как JIT-компиляция, разрыв между компилируемыми и интерпретируемыми языками сокращается. Примерами интерпретируемых языков являются PHP, Perl, Ruby и Python. Вот некоторые из концептов, которые стали проще благодаря интерпретируемым языкам:

Независимость от платформы;
Рефлексия;
Динамическая типизация;
Меньший размер исполняемых файлов:
Динамические области видимости.
Основным недостатком интерпретируемых языком является их невысокая скорость исполнения. Тем не менее, JIT-компиляция позволяет ускорить процесс благодаря переводу часто используемых последовательностей инструкции в машинный код.

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

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Принципы паттернов проектирования

A

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

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

Шаблоны бывают следующих трех видов:

Порождающие.
Структурные.
Поведенческие.

Порождающие шаблоны — шаблоны проектирования, которые абстрагируют процесс инстанцирования. Они позволяют сделать систему независимой от способа создания, композиции и представления объектов. Шаблон, порождающий классы, использует наследование, чтобы изменять наследуемый класс, а шаблон, порождающий объекты, делегирует инстанцирование другому объекту.

Существуют следующие порождающие шаблоны:

простая фабрика (Simple Factory);
фабричный метод (Factory Method);
абстрактная фабрика (Abstract Factory);
строитель (Builder);
прототип (Prototype);
одиночка (Singleton).

Структурные шаблоны в основном связаны с композицией объектов, другими словами, с тем, как сущности могут использовать друг друга. Ещё одним объяснением было бы то, что они помогают ответить на вопрос «Как создать программный компонент?».
Структурные шаблоны — шаблоны проектирования, в которых рассматривается вопрос о том, как из классов и объектов образуются более крупные структуры.

Список структурных шаблонов проектирования:
адаптер (Adapter);
мост (Bridge);
компоновщик (Composite);
декоратор (Decorator);
фасад (Facade);
приспособленец (Flyweight);
заместитель (Proxy).

Поведенческие шаблоны связаны с распределением обязанностей между объектами. Их отличие от структурных шаблонов заключается в том, что они не просто описывают структуру, но также описывают шаблоны для передачи сообщений / связи между ними. Или, другими словами, они помогают ответить на вопрос «Как запустить поведение в программном компоненте?»
Поведенческие шаблоны — шаблоны проектирования, определяющие алгоритмы и способы реализации взаимодействия различных объектов и классов.

Поведенческие шаблоны:
цепочка обязанностей (Chain of Responsibility);
команда (Command);
итератор (Iterator);
посредник (Mediator);
хранитель (Memento);
наблюдатель (Observer);
посетитель (Visitor);
стратегия (Strategy);
состояние (State);
шаблонный метод (Template Method).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

Паттерн Простая фабрика (Simple Factory)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Паттерн Фабричный метод (Fabric Method)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Паттерн Абстрактная фабрика (Abstract Factory)

A

Абстрактная фабрика — порождающий шаблон проектирования, предоставляет интерфейс для создания семейств взаимосвязанных или взаимозависимых объектов, не специфицируя их конкретных классов. Шаблон реализуется созданием абстрактного класса Factory, который представляет собой интерфейс для создания компонентов системы (например, для оконного интерфейса он может создавать окна и кнопки). Затем пишутся классы, реализующие этот интерфейс.
Простыми словами: Фабрика фабрик. Фабрика, которая группирует индивидуальные, но связанные/зависимые фабрики без указания их конкретных классов.
Когда использовать: Когда есть взаимосвязанные зависимости с не очень простой логикой создания.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Паттерн Строитель (Builder)

A

Строитель — порождающий шаблон проектирования, который предоставляет способ создания составного объекта. Предназначен для решения проблемы антипаттерна «Телескопический конструктор».
Простыми словами: Шаблон позволяет вам создавать различные виды объекта, избегая засорения конструктора. Он полезен, когда может быть несколько видов объекта или когда необходимо множество шагов, связанных с его созданием.
Когда использовать: Когда может быть несколько видов объекта и надо избежать «телескопического конструктора». Главное отличие от «фабрики» — это то, что она используется, когда создание занимает один шаг, а «строитель» применяется при множестве шагов.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Паттерн Прототип (Prototype)

A

Задаёт виды создаваемых объектов с помощью экземпляра-прототипа и создаёт новые объекты путём копирования этого прототипа. Он позволяет уйти от реализации и позволяет следовать принципу «программирование через интерфейсы». В качестве возвращающего типа указывается интерфейс / абстрактный класс на вершине иерархии, а классы-наследники могут подставить туда наследника, реализующего этот тип.
Простыми словами: Прототип создает объект, основанный на существующем объекте при помощи клонирования.

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

Паттерн Одиночка (Singleton)

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

Паттерн Адаптер (Adapter)

A

Адаптер — структурный шаблон проектирования, предназначенный для организации использования функций объекта, недоступного для модификации, через специально созданный интерфейс.
Простыми словами: Шаблон позволяет обернуть несовместимые объекты в адаптер, чтобы сделать их совместимыми с другим классом.

43
Q

Паттерн Мост (Bridge)

A

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

44
Q

Паттерн Компоновщик (Composite)

A

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

45
Q

Паттерн Декоратор (Decorator)

A

Декоратор — структурный шаблон проектирования, предназначенный для динамического подключения дополнительного поведения к объекту. Шаблон декоратор предоставляет гибкую альтернативу практике создания подклассов с целью расширения функциональности.
Простыми словами: Шаблон декоратор позволяет вам динамически изменять поведение объекта во время работы, оборачивая их в объект класса декоратора.

46
Q

Паттерн Фасад (Facade)

A

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

47
Q

Приспособленец (Flyweight)

A

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

48
Q

Паттерн Заместитель (Proxy)

A

Заместитель — структурный шаблон проектирования, который предоставляет объект, который контролирует доступ к другому объекту, перехватывая все вызовы (выполняет функцию контейнера).
Простыми словами: Используя шаблон заместитель, класс отображает функциональность другого класса.

49
Q

Паттерн Цепочка обязанностей (Chain of Responsibility)

A

Цепочка обязанностей — поведенческий шаблон проектирования предназначенный для организации в системе уровней ответственности.
Простыми словами: цепочка обязанностей помогает строить цепочки объектов. Запрос входит с одного конца и проходит через каждый объект, пока не найдет подходящий обработчик.

50
Q

Паттерн Команда (Command)

A

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

51
Q

Паттерн Итератор (Iterator)

A

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

52
Q

Паттерн Посредник (Mediator)

A

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

53
Q

Паттерн Хранитель (Memento)

A

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

Простыми словами: Шаблон хранитель фиксирует и хранит текущее состояние объекта, чтобы оно легко восстанавливалось.

54
Q

Паттерн Наблюдатель (Observer)

A

Наблюдатель — поведенческий шаблон проектирования, также известен как «подчинённые» (Dependents). Создает механизм у класса, который позволяет получать экземпляру объекта этого класса оповещения от других объектов об изменении их состояния, тем самым наблюдая за ними.
Простыми словами: Шаблон определяет зависимость между объектами, чтобы при изменении состояния одного из них зависимые от него узнавали об этом.

55
Q

Паттерн Посетитель (Visitor)

A

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

56
Q

Паттерн Стратегия (Strategy)

A

Стратегия — поведенческий шаблон проектирования, предназначенный для определения семейства алгоритмов, инкапсуляции каждого из них и обеспечения их взаимозаменяемости. Это позволяет выбирать алгоритм путём определения соответствующего класса. Шаблон Strategy позволяет менять выбранный алгоритм независимо от объектов-клиентов, которые его используют.
Простыми словами: Шаблон стратегия позволяет переключаться между алгоритмами или стратегиями в зависимости от ситуации.
Пример: сортировка пузырьком когда данных мало, быстрая когда много

57
Q

Паттерн Состояние (State)

A

Состояние — поведенческий шаблон проектирования. Используется в тех случаях, когда во время выполнения программы объект должен менять своё поведение в зависимости от своего состояния.
Простыми словами: Шаблон позволяет менять поведение класса при изменении состояния.

58
Q

Паттерн Шаблонный метод (Template Method)

A

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

59
Q

Устройство процессора

A

АЛУ - арифметико-логическое устройство
Управляющий автомат
Внутренняя память - регистры (меньше и быстрее основной памяти, некоторые доступны пользователям, некоторые используются для управления и статусов)
регистр флагов - статусы операций

60
Q

Общие правила анализа скорости роста функций

A
  • постоянные множители (константы) можно опускать
  • многочлен более высокой степени растет быстрее
  • экспонента растет быстрее многочлена
  • многочлен растет быстрее логарифма
  • медленно растущие слагаемые можно опускать
f(x) = O (g(x)) - функция  f(x) растет медленнее, чем g(x)
f(x) = тэта (g(x))  - функция f(x) растет так же, как g(x)
f(x) = омега (g(x)) - функция f(x) растет быстрее, чем g(x)
61
Q

Порядок роста функций

A

logn < sqrt(n) < n < nlogn < n^2 < 2^n

62
Q

Компоненты процесса

A
  • Идентификатор
  • Состояние
  • Приоритет
  • Счетчик команд
  • Указатели на память
  • Контекст
  • Информация о статусе I/O
  • Другая информация

процессы образуют очередь (по приоритету и живому порядку)

63
Q

Условия уничтожения процесса

A
  • сигнал HALT
  • действие пользователя
  • ошибка
  • завершение родительского процесса
64
Q

создание процесса

A
  • присвоение уникального идентификатора
  • предоставление памяти
  • инициализация контрольного блока
  • создание или изменение существующих структур
65
Q

переключение процесса

A
  • сохранить состояние процесса (регистры)
  • обновить контрольный блок процесса, который запущен в данный момент
  • перенести контрольный блок процесса в соответствующую очередь - ready; blocked; ready/suspend
  • выбрать другой процесс для выполнения
  • обновить контр.блок процесса, на кот. нужно переключиться
  • обновить структуры данных управления памятью
  • восстановить состояние процесса
66
Q

Порядки роста

A

Константный — O(1)
Порядок роста O(1) означает, что вычислительная сложность алгоритма не зависит от размера входных данных.
Линейный — O(n)
Порядок роста O(n) означает, что сложность алгоритма линейно растет с увеличением входного массива. Такие алгоритмы легко узнать по наличию цикла по каждому элементу входного массива.
Логарифмический – O( log n)
Порядок роста O( log n) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива. Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность.
Линеарифметический — O(n·log n)
Линеарифметический (или линейно-логарифмический) алгоритм имеет порядок роста O(n·log n). Некоторые алгоритмы типа «разделяй и властвуй» попадают в эту категорию. (напр., сортировка слиянием и быстрая сортировка)
Квадратичный — O(n 2)
Время работы алгоритма с порядком роста O(n 2) зависит от квадрата размера входного массива. Несмотря на то, что такой ситуации иногда не избежать, квадратичная сложность — повод пересмотреть используемые алгоритмы или структуры данных. Проблема в том, что они плохо масштабируются. (напр., пузырьковая сортировка)

67
Q

Реализация связного списка

A

Метод Add
Поведение: Добавляет элемент в конец списка.
Сложность: O(1)
Добавление элемента в связный список производится в три этапа:

Создать экземпляр класса LinkedListNode.
Найти последний узел списка.
Установить значение поля Next последнего узла списка так, чтобы оно указывало на созданный узел.
Основная сложность заключается в том, чтобы найти последний узел списка. Можно сделать это двумя способами. Первый — сохранять указатель на первый узел списка и перебирать узлы, пока не дойдем до последнего. В этом случае нам не требуется сохранять указатель на последний узел, что позволяет использовать меньше памяти (в зависимости от размера указателя на вашей платформе), но требует прохода по всему списку при каждом добавлении узла. Это значит, что метод Add займет O(n) времени.

Второй метод заключается в сохранении указателя на последний узел списка, и тогда при добавлении нового узла мы поменяем указатель так, чтобы он указывал на новый узел. Этот способ предпочтительней, поскольку выполняется за O(1) времени.

Метод Remove
Поведение: Удаляет первый элемент списка со значением, равным переданному. Возвращает true, если элемент был удален и false в противном случае.
Сложность: O(n)
Основной алгоритм удаления элемента такой:

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

Список может быть пустым, или значение, которое мы передаем в метод может не присутствовать в списке. В этом случает список останется без изменений.
Удаляемый узел может быть единственным в списке. В этом случае мы установим значения полей _head и _tail равными null.
Удаляемый узел будет в начале списка. В этом случае мы записываем в _head ссылку на следующий узел.
Удаляемый узел будет в середине списка.
Удаляемый узел будет в конце списка. В этом случае мы записываем в _tail ссылку на предпоследний узел, а в его поле Next записываем null.

Метод Contains
Поведение: Возвращает true или false в зависимости от того, присутствует ли искомый элемент в списке.
Сложность: O(n)
Метод Contains достаточно простой. Он просматривает каждый элемент списка, от первого до последнего, и возвращает true как только найдет узел, чье значение равно переданному параметру. Если такой узел не найден, и метод дошел до конца списка, то возвращается false.

68
Q

Реализация двусвязного списка

A

Метод AddFirst
В то время, как односвязный список позволяет добавлять элементы только в конец, используя двусвязный список мы можем добавлять элементы как в начало, так и в конец, с помощью методов AddFirst и AddLast соответственно.
Поведение: Добавляет переданный элемент в начало списка.
Сложность: O(1)
При добавлении элемента в начало списка последовательность действий примерно такая же, как и при добавлении элемента в односвязный список.

Установить значение поля Next в новом узле так, чтобы оно указывало на бывший первый узел.
Установить значение поля Previous в бывшем первом узле так, чтобы оно указывало на новый узел.
Обновить поле _tail при необходимости и инкрементировать поле Count

69
Q

Сортировка пузырьком

A

Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Соседние элементы последовательности сравниваются между собой и, в случае необходимости, меняются местами. Аналогично алгоритм продолжает выполняться до тех пор, пока все элементы массива не окажутся на своих местах. Всего для этого потребуется N*(N-1) сравнений.
В лучшем случае сортировка пузырьком потребует O(n) времени, а в среднем и худшем – O(n2).

70
Q

Сортировка выбором

A

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

Сложность в лучшем случае О(n), в худшем O(n^2)

71
Q

Сортировка вставками

A

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

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

мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex. Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки.

Сложность в лучшем случае О(n), в худшем O(n^2)

72
Q

Сортировка Шелла

A

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

Идея метода заключается в сравнение разделенных на группы элементов последовательности, находящихся друг от друга на некотором расстоянии. Изначально это расстояние равно d или N/2, где N — общее число элементов. На первом шаге каждая группа включает в себя два элемента расположенных друг от друга на расстоянии N/2; они сравниваются между собой, и, в случае необходимости, меняются местами. На последующих шагах также происходят проверка и обмен, но расстояние d сокращается на d/2, и количество групп, соответственно, уменьшается. Постепенно расстояние между элементами уменьшается, и на d=1 проход по массиву происходит в последний раз.
Сортировка Шелла уступает в эффективности быстрой сортировки, но выигрывает у сортировки вставками.

73
Q

Быстрая сортировка

A

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

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

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

В следующих пяти пунктах описана общая схема разбиения массива (сортировка по возрастанию):

вводятся указатели first и last для обозначения начального и конечного элементов последовательности, а также опорный элемент mid;
вычисляется значение опорного элемента (first+last)/2, и заносится в переменную mid;
указатель first смещается с шагом в 1 элемент к концу массива до тех пор, пока Mas[first]>mid. А указатель last смещается от конца массива к его началу, пока Mas[last] 1», нужно действовать примерно по следующей схеме:

Имеется массив Mas[L..R], где L и R – индексы крайних элементов этого массива. По окончанию разбиения, указатели first и last оказались примерно в середине последовательности, тем самым образуя два отрезка: левый от L до last и правый от first до R. Выполнить рекурсивное упорядочивание левой части нужно в том случае, если выполняется условие L

74
Q

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

A

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

Несколько детально этот процесс можно расписать так:

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

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

75
Q

Динамический массив

A

ArrayList — это коллекция, которая реализует интерфейс IList и использует массив для хранения элементов. Как и связный список, ArrayList может хранить произвольное число элементов (ограниченное только объемом доступной памяти), но в остальном ведет себя как массив.
Вставка элементов
Вставка элементов в динамический массив отличается от вставки в связный список. На то есть две причины. Первая: динамический массив поддерживает вставку в середину массива, тогда как в связный список можно вставлять только в конец или начало. Вторая: вставка элемента в связный список всегда выполняется за константное время. Вставка в динамический массив может занимать как O(1), так и O(n) времени.

Расширение массива
По мере добавления элементов внутренний массив может переполниться. В этом случае необходимо сделать следующее:

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

Увеличение вдвое (подход Mono и Rotor)
Существуют две реализации ArrayList, код которых можно найти в сети: Mono и Rotor. Обе используют простой алгоритм увеличения размера массива, увеличивая его вдвое при необходимости. Если изначальный размер массива равен нулю, то новый будет вмещать 16 элементов

Метод Insert
Поведение: добавляет элемент по указанному индексу. Если индекс равен количеству элементов или больше него, кидает исключение.
Сложность: O(n).
Вставка по определенному индексу требует сдвига всех элементов, начиная с этого индекса, на одну позицию вправо. Если внутренний массив заполнен, вставка потребует увеличения его размера.

Метод Add
Поведение: добавляет элемент в конец списка.
Сложность: O(1), если осталось более одного свободного места; O(n), если необходимо расширение массива.

Удаление элементов
Метод RemoveAt
Поведение: удаляет элемент, расположенный по заданному индексу.
Сложность: O(n).
Удаление элемента по индексу — операция, обратная вставке. Указанный элемент удаляется, а остальные сдвигаются на одну позицию влево.

Метод Remove
Поведение: удаляет первый элемент, значение которого равно предоставленному. Возвращает true, если элемент был удален, или false в противном случае.
Сложность: O(n).

Метод IndexOf
Поведение: возвращает индекс первого элемента, значение которого равно предоставленному, или -1, если такого значения нет.
Сложность: O(n).

Метод Item
Поведение: позволяет прочитать или изменить значение по индексу.
Сложность: O(1).

Метод Contains
Поведение: возвращает true, если значение есть в списке, и false в противном случае.
Сложность: O(n).

76
Q

Бинарный поиск

A

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

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

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

зона поиска (на первом шаге ей является весь массив) делиться на две равные части, путем определения ее среднего (mid) элемента;
средний элемент сравнивается с искомым (key), результатом этого сравнения будет один из трех случаев:
keymid. Крайней левой границей области поиска становится следующий за средним элемент (left ← mid+1);
key=mid. Значения среднего и искомого элементов совпадают, следовательно элемент найден, работа алгоритма завершается.
если для проверки не осталось ни одного элемента, то алгоритм завершается, иначе выполняется переход к пункту 1.
В среднем и худшем случае время работы алгоритма составляет O(logn), что значительно быстрее, чем у линейного поиска, требующего линейного времени.

77
Q

Линейный поиск

A

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

78
Q

Интерполяционный поиск

A

Интерполирование – нахождение промежуточных значений величины по имеющемуся дискретному набору известных значений. Интерполяционный поиск работает только с упорядоченными массивами; он похож на бинарный, в том смысле, что на каждом шаге вычисляется некоторая область поиска, которая, по мере выполнения алгоритма, сужается.

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

mid = left + (((key-A[left])*(right-left))//(A[right]-A[left]))

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

79
Q

Стек

A

Операция добавления элемента на стек называется «push», удаления — «pop». Последний добавленный элемент называется верхушкой стека, или «top», и его можно посмотреть с помощью операции «peek».

Метод Push
Поведение: Добавляет элемент на вершину стека.
Сложность: O(1).
Поскольку мы используем связный список для хранения элементов, можно просто добавить новый в конец списка.

Метод Pop
Поведение: Удаляет элемент с вершины стека и возвращает его. Если стек пустой, кидает InvalidOperationException.
Сложность: O(1).
Push добавляет элементы в конец списка, поэтому забирать их будет также с конца. В случае, если список пуст, будет выбрасываться исключение.

Метод Peek
Поведение: Возвращает верхний элемент стека, но не удаляет его. Если стек пустой, кидает InvalidOperationException.
Сложность: O(1).

80
Q

Очередь

A

Очередь
Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов. Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO). Очереди часто используются в программах для реализации буфера, в который можно положить элемент для последующей обработки, сохраняя порядок поступления. Например, если база данных поддерживает только одно соединение, можно использовать очередь потоков, которые будут, как ни странно, ждать своей очереди на доступ к БД.

Метод Enqueue
Поведение: Добавляет элемент в очередь.
Сложность: O(1).
Новые элементы очереди можно добавлять как в начало списка, так и в конец. Важно только, чтобы элементы доставались с противоположного края.

Метод Dequeue
Поведение: Удаляет первый помещенный элемент из очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException.
Сложность: O(1).
Поскольку мы вставляем элементы в начало списка, убирать мы их будем с конца. Если список пуст, кидается исключение.

Метод Peek
Поведение: Возвращает элемент, который вернет следующий вызов метода Dequeue. Очередь остается без изменений. Если очередь пустая, кидает InvalidOperationException.
Сложность: O(1).

Метод Count
Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
Сложность: O(1).

81
Q

Двусторонняя очередь

A

Двусторонняя очередь (Double-ended queue), или дек (Deque), расширяет поведение очереди. В дек можно добавлять или удалять элементы как с начала, так и с конца очереди. Такое поведение полезно во многих задачах, например, планирование выполнения потоков или реализация других структур данных.

Класс Deque проще всего реализовать с помощью двусвязного списка. Он позволяет просматривать, удалять и добавлять элементы в начало и в конец списка. Основное отличие двусторонней очереди от обычной — методы Enqueue, Dequeue, и Peek разделены на пары для работы с обоими концами списка.

Метод EnqueueFirst
Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst.
Сложность: O(1).

Метод EnqueueLast
Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast.
Сложность: O(1).

Метод DequeueFirst
Поведение: Удаляет элемент из начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException.
Сложность: O(1).

Метод DequeueLast
Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException.
Сложность: O(1).

Метод PeekFirst
Поведение: Возвращает элемент из начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException.
Сложность: O(1).

82
Q

Бинарное дерево

A

Метод Add
Поведение: Добавляет элемент в дерево на корректную позицию.
Сложность: O(log n) в среднем; O(n) в худшем случае.
Добавление узла не представляет особой сложности. Оно становится еще проще, если решать эту задачу рекурсивно. Есть всего два случая, которые надо учесть:

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

Метод Remove
Поведение: Удаляет первый узел с заданным значением.
Сложность: O(log n) в среднем; O(n) в худшем случае.
Удаление узла из дерева — одна из тех операций, которые кажутся простыми, но на самом деле таят в себе немало подводных камней.

В целом, алгоритм удаления элемента выглядит так:

Найти узел, который надо удалить.
Удалить его.
Первый шаг достаточно простой. Мы рассмотрим поиск узла в методе Contains ниже. После того, как мы нашли узел, который необходимо удалить, у нас возможны три случая.

Случай 1: У удаляемого узла нет правого ребенка.
В этом случае мы просто перемещаем левого ребенка (при его наличии) на место удаляемого узла.

Случай 2: У удаляемого узла есть только правый ребенок, у которого, в свою очередь нет левого ребенка. В этом случае нам надо переместить правого ребенка удаляемого узла на его место.

Случай 3: У удаляемого узла есть первый ребенок, у которого есть левый ребенок. В этом случае место удаляемого узла занимает крайний левый ребенок правого ребенка удаляемого узла. Мы дожны поместить на место удаляемого узел со значением, меньшим или равным любому узлу справа от него. Для этого нам необходимо найти наименьшее значение в правом поддереве. Поэтому мы берем крайний левый узел правого поддерева.

Метод Contains
Поведение: Возвращает true если значение содержится в дереве. В противном случает возвращает false.
Сложность: O(log n) в среднем; O(n) в худшем случае.
Метод Contains выполняется с помощью метода FindWithParent, который проходит по дереву, выполняя в каждом узле следующие шаги:

Если текущий узел null, вернуть null.
Если значение теккущего узна равно искомому, вернуть текущий узел.
Если искомое значение меньше значения текущего узла, установить левого ребенка текущим узлом и перейти к шагу 1.
В противном случае, установить правого ребенка текущим узлом и перейти к шагу 1.

83
Q

Обход деревьев

A

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

Метод Preorder (или префиксный обход)
Поведение: Обходит дерево в префиксном порядке, выполняя указанное действие над каждым узлом.
Сложность: O(n)
При префиксном обходе алгоритм получает значение текущего узла перед тем, как перейти сначала в левое поддерево, а затем в правое.

Метод Postorder (или постфиксный обход)
Поведение: Обходит дерево в префиксном порядке, выполняя указанное действие над каждым узлом.
Сложность: O(n)
При постфиксном обходе мы посещаем левое поддерево, правое поддерево, а потом, после обхода всех детей, переходим к самому узлу.

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

Метод Inorder (или инфиксный обход)
Поведение: Обходит дерево в инфиксном порядке, выполняя указанное действие над каждым узлом.
Сложность: O(n)
Инфиксный обход используется тогда, когда нам надо обойти дерево в порядке, соответствующем значениям узлов.

84
Q

Потоки (треды)

A

Поток - элемент выполнения процесса (наименьшая единица обработки с т.з. ОС)
Задача - элемент владения
Многопоточность - способность платформы или приложения запускать несколько параллельных потоков внутри процесса

Компоненты потока:

  • Состояние
  • Контекст
  • Локальные данные
  • Стек выполнения
  • Доступ к ресурсам процессора

Отличия от процессов:

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

Симметричная мультипроцессорность

A

Ядро может запускать процессы на любом процессоре

Части ядра могут работать параллельно на разных процессорах

86
Q

Множества

A

Множество — это коллекция, которая реализует основные математические операции над множествами: пересечения (intersection), объединение (union), разность (difference) и симметрическая разность (symmetric difference).

Метод Add
Поведение: Добавляет элементы в множество. Если элемент уже присутствует в множестве, бросается исключение InvalidOperationException.
Сложность: O(n)

Метод AddRange
Поведение: Добавляет несколько элементов в множество. Если какой-либо из добавляемых элементов присутствует в множестве, или в добавляемых элементах есть дублирующиеся, выбрасывается исключение InvalidOperationException.
Сложность: O(m·n), где m — количество вставляемых элементов и n — количество элементов множества.

Метод Remove
Поведение: Удаляет указанный элемент из множества и возвращает true. В случае, если элемента нет, возвращает false.
Сложность: O(n)

Метод Contains
Поведение: Возвращает true, если множество содержит указанный элемент. В противном случае возвращает false.
Сложность: O(n)

Метод Count
Поведение: Возвращает количество элементов множества или 0, если множество пусто.
Сложность: O(1)

Метод Union
Поведение: Возвращает множество, полученное операцией объединения его с указанным.
Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.
Объединение множеств — это множество, которое содержит элементы, присутствующие хотя бы в одном из двух.

Метод Intersection
Поведение: Возвращает множество, полученное операцией пересечения его с указанным.
Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.
Пересечение множеств содержит только те элементы, которые есть в обоих множествах.

Метод Difference
Поведение: Возвращает множество, являющееся разностью текущего с указанным.
Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.
Разность множеств — это все элементы, которые содержатся в одном множестве (том, у которого вызывается метод), но не содержатся в другом (том, которое передается аргументом).

Метод Symmetric Difference
Поведение: Возвращает множество, являющееся симметрической разностью текущего с указанным.
Сложность: O(m·n), где m и n — количество элементов переданного и текущего множеств соответственно.
Симметрическая разность — это все элементы, которые содержатся только в одном из рассматриваемых множеств.

87
Q

Поиск в ширину

A

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

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

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

88
Q

Поиск в глубину

A

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

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

89
Q

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

A

Алгоритм голландского ученого Эдсгера Дейкстры находит все кратчайшие пути из одной изначально заданной вершины графа до всех остальных. С его помощью, при наличии всей необходимой информации, можно, например, узнать какую последовательность дорог лучше использовать
Минусом данного метода является невозможность обработки графов, в которых имеются ребра с отрицательным весом,
оскольку самые выгодные пути только предстоит найти, в каждый элемент вектора distance записывается такое число, которое заведомо больше любого потенциального пути (обычно это число называют бесконечностью, но в программе используют, например максимальное значение конкретного типа данных). В качестве исходного пункта выбирается вершина s и ей приписывается нулевой путь: distance[s]=0, т. к. нет ребра из s в s (метод не предусматривает петель).

Далее, находятся все соседние вершины (в которые есть ребро из s) [пусть таковыми будут t и u] и поочередно исследуются, а именно вычисляется стоимость маршрута из s поочередно в каждую из них:

distance[t]=distance[s]+вес инцидентного s и t ребра;
distance[u]=distance[s]+ вес инцидентного s и u ребра.
Но вполне вероятно, что в ту или иную вершину из s существует несколько путей, поэтому цену пути в такую вершину в массиве distance придется пересматривать, тогда наибольшее (неоптимальное) значение игнорируется, а наименьшее ставиться в соответствие вершине.

После обработки смежных с s вершин она помечается как посещенная: visited[s]=true, и активной становится та вершина, путь из s в которую минимален. Допустим, путь из s в u короче, чем из s в t, следовательно, вершина u становиться активной и выше описанным образом исследуются ее соседи, за исключением вершины s. Далее, u помечается как пройденная: visited[u]=true, активной становится вершина t, и вся процедура повторяется для нее. Алгоритм Дейкстры продолжается до тех пор, пока все доступные из s вершины не будут исследованы.

90
Q

Алгоритм Флойда – Уоршелла

A

Алгоритм Флойда – Уоршелла – динамический алгоритм вычисления значений кратчайших путей для каждой из вершин графа. Метод работает на взвешенных графах, с положительными и отрицательными весами ребер, но без отрицательных циклов, являясь, таким образом, более общим в сравнении с алгоритмом Дейкстры, т. к. последний не работает с отрицательными весами ребер, и к тому же классическая его реализация подразумевает определение оптимальных расстояний от одной вершины до всех остальных.
Ключевая часть алгоритма, состоя из трех циклов, выражения и условного оператора, записывается довольно компактно:

Для k от 1 до |V| выполнять
Для i от 1 до |V| выполнять
Для j от 1 до |V| выполнять
Если D[i][k]+D[k][j]

91
Q

Алгоритм Беллмана-Форда

A

Также как и алгоритм Дейкстры, алгоритм Беллмана — Форда вычисляет во взвешенном графе кратчайшие пути от одной вершины до всех остальных. Он подходит для работы с графами, имеющими ребра с отрицательным весом. Но спектр применимости алгоритма затрагивает не все такие графы, ввиду того, что каждый очередной проход по пути, составленному из ребер, сумма весов которых отрицательна (т. е. по отрицательному циклу), лишь улучшает требуемое значение. Бесконечное число улучшений делает невозможным определение одного конкретного значения, являющегося оптимальным. В связи с этим алгоритм Беллмана — Форда не применим к графам, имеющим отрицательные циклы, но он позволяет определить наличие таковых
Решить задачу, т. е. найти все кратчайшие пути из вершины s до всех остальных, используя алгоритм Беллмана — Форда, это значит воспользоваться методом динамического программирования: разбить ее на типовые подзадачи, найти решение последним, покончив тем самым с основной задачей. Здесь решением каждой из таких подзадач является определение наилучшего пути от одного отдельно взятого ребра, до какого-либо другого.
Для хранения результатов работы алгоритма заведем одномерный массив d[]. В каждом его i-ом элементе будет храниться значение кратчайшего пути из вершины s до вершины i (если таковое имеется). Изначально, присвоим элементам массива d[] значения равные условной бесконечности (например, число заведомо большее суммы всех весов), а в элемент d[s] запишем нуль.

Так мы задействовали известную и необходимую информацию, а именно известно, что наилучший путь из вершины s в нее же саму равен 0, и необходимо предположить недоступность других вершин из s. По мере выполнения алгоритма, для некоторых из них, это условие окажется ложным, и вычисляться оптимальные стоимости путей до этих вершин из s.
Для i от 1 до n-1 выполнять
Для j от 1 до m выполнять
Если d[v] + w(v, u) < d[u] то
d[u] < d[v] + w(v, u)
На каждом n-ом шаге осуществляются попытки улучшить значения элементов массива d[]: если сумма, составленная из веса ребра w(v, u) и веса хранящегося в элементе d[v], меньше веса d[u], то она присваивается последнему.
Основная часть алгоритма Беллмана – Форда (проверка условия) выполняется m*(n-1) раз, т. к. число повторений внешнего цикла равно n-1, а внутреннего – m. Отказ от n-ой итерации целесообразен, поскольку алгоритм справляется со своей задачей за n-1 шаг, но запуск внешнего цикла n раз позволит выявить наличие отрицательного цикла в графе.

92
Q

Решето Эратосфена

A

нахождение всех простых чисел до некоторого заданного числа N.
Дана упорядоченная по возрастанию последовательность натуральных чисел. Следуя методу Эратосфена, возьмем некоторое число P изначально равное 2 – первому простому числу, и вычеркнем из последовательности все числа кратные P: 2P, 3P, 4P, …, iP (iP≤N). Далее, из получившегося списка в качестве P берется следующее за двойкой число – тройка, вычеркиваются все кратные ей числа (6, 9, 12, …). По такому принципу алгоритм продолжает выполняться для оставшейся части последовательности, отсеивая все составные числа в заданном диапазоне.
Программная реализация алгоритма Эратосфена потребует:

организовать логический массив и присвоить его элементам из диапазона от 2 до N логическую единицу;
в свободную переменную P записать число 2, являющееся первым простым числом;
исключить из массива все числа кратные P2, ступая с шагом по P;
записать в P следующее за ним не зачеркнутое число;
повторять действия, описанные в двух предыдущих пунктах, пока это возможно.
Обратите внимание: на третьем шаге мы исключаем числа, начиная сразу с P2, это связано с тем, что все составные числа меньшие P будут уже зачеркнуты. Поэтому процесс фильтрации следует остановить, когда P2 станет превышать N. Это важное замечание позволяет улучшить алгоритм, уменьшив число выполняемых операций.
Решето Эратосфена для выявления всех простых чисел в заданной последовательности ограниченной некоторым N потребует O(Nlog (log N)) операций. Поэтому уместнее использовать данный метод чем, например, наиболее тривиальный и затратный перебор делителей.

93
Q

Бинарный алгоритм вычисления НОД (алгоритм Стейна)

A

В эффективности данный алгоритм превосходит метод Евклида, что связано с использованием сдвигов, то есть операций деления на степень 2-ки, в нашем случае на 2.
НОД(2A, 2B) = 2НОД(A, B)
НОД(2A, 2B+1) = НОД(A, 2B+1)
НОД(-A, B) = НОД(A, B)

инициализируем переменную k значением 1. Ее задача – подсчитывать «несоразмерность», полученную в результате деления. В то время как A и Bсокращаются вдвое, она будет увеличиваться вдвое;
пока A и B одновременно не равны нулю, выполняем
если A и B – четные числа, то делим надвое каждое из них: A←A/2, B←B/2, а k увеличивать вдвое: k←k2, до тех пор, пока хотя бы одно из чисел A или B не станет нечетным;
если A – четное, а B – нечетное, то делим A, пока возможно деление без остатка;
если B – четное, а A – нечетное, то делим B, пока возможно деление без остатка;
если A≥B, то заменим A разностью A и B, иначе B заменим разностью Bи A.
после выхода из 2-ого пункта, остается вернуть в качестве результата произведение B и k: НОД(A, B)=B
k.

94
Q

Быстрое возведение в степень

A

Пусть имеется некоторая степень x^n, где x – действительное число, а n – натуральное. Тогда для x^n справедливо равенство:

x^n = (x^m)^k

При этом m*k=n

Общая формула перехода: x^n = x^(n-1)*x

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

95
Q

Хеш-таблица

A

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

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

Принцип организации хеш-таблицы методом открытого хеширования заключается в реализации логически связанных цепочек, начинающихся в ячейках хеш-таблицы. Под цепочками подразумеваются связанные списки, указатели на которые хранятся в ячейках хеш-таблицы. Каждый элемент связанного списка – блок данных, и если с некоторым указателем, хранящимся по адресу i, связаны n таких блоков (n>1), то это свидетельствует о том, что n ключей получили один и тот же хеш-код i, т. е. имеет место коллизия. Но метод открытого хеширования устраняет конфликт, поскольку данные хранятся не в самой таблице, а в связных списках, которые увеличиваются при возникновении конфликта.
Если в исходном массиве было всего N элементов (столько же будут содержать в совокупности и все списки), то средняя длина списков будет равна α=N/M, где M – число элементов хеш-таблицы, α – коэффициент заполнения хеш-таблицы. Предположив, например, что в списке на рисунке выше M=5 (заклеив 4-ую по счету строку), получим среднее число списков α=2.
Чтобы увеличить скорость работы операций поиска, вставки и удаления нужно, зная N, подобрать M примерно равное ему, т. к. тогда α будет равняться 1-ому или ≈1-ому, следовательно, можно рассчитывать на оптимальное время, в лучшем случае равное O(1). В худшем случае все N элементов окажутся в одном списке, и тогда, например, операция нахождения элемента (в худшем случае) потребует O(N) времени.

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

Сам процесс заполнения хеш-таблицы с использованием алгоритма закрытого хеширования осуществляется следующим образом:

имеется изначально пустая хеш-таблица T размера M, массив A размера N (M≥N) и хеш-функция h(), пригодная для обработки ключей массива A;
элемент xi, ключ которого keyi, помещается в одну из ячеек хеш-таблицы, руководствуясь следующим правилом:
a) если h(keyi) – номер свободной ячейки таблицы T, то в последнюю записывается xi;

b) если h(keyi) – номер уже занятой ячейки таблицы T, то на занятость проверяется другая ячейка, если она свободна то xi заноситься в нее, иначе вновь проверяется другая ячейка, и так до тех пор, пока не найдется свободная или окажется, что все M ячеек таблицы заполнены.

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

96
Q

Хеш-функции

A

Хеш-функция – функция, преобразовывающая входную последовательность данных произвольного размера в выходную последовательность фиксированного размера. Процесс преобразования данных называется хешированием. Результат хеширования – хеш-код (хеш-сумма, хеш).

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

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

Метод деления.
Пусть k – ключ (тот, что необходимо хешировать), а N – максимально возможное число хеш-кодов. Тогда метод хеширования посредством деления будет заключаться во взятии остатка от деления k на N:

h(k)=k mod N, где mod – операция взятия остатка от деления. Во избежание большого числа коллизий рекомендуется выбирать N простым числом, и не рекомендуется степенью с основанием 2 и показателем m (2m). Вообще, по возможности, следует выбирать N, опираясь на значения входящих ключей.

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

h(k)=⌊N({kA})⌋

Здесь A – рациональное число, по модулю меньшее единицы (0<a></a>

97
Q

Теория графов

A

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

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

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

98
Q

АВЛ-дерево

A

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

АВЛ-дерево – сбалансированное двоичное дерево поиска с k=1. Для его узлов определен коэффициент сбалансированности (balance factor). Balance factor – это разность высот правого и левого поддеревьев, принимающая одно значение из множества {-1, 0, 1}.

Сбалансированное дерево эффективно в обработке, что следует из следующих рассуждений. Максимальное количество шагов, которое может потребоваться для обнаружения нужного узла, равно количеству уровней самого бинарного дерева поиска. А так как поддеревья сбалансированного дерева, «растущие» из произвольного корня, практически симметричны, то и его листья расположены на сравнительно невысоком уровне, т. е. высота дерева сводиться к оптимальному минимуму. Поэтому критерий баланса положительно сказывается на общей производительности. Но в процессе обработки АВЛ-дерева, балансировка может нарушиться, тогда потребуется осуществить операцию балансировки. Помимо нее, над АВЛ-деревом определены операции вставки и удаления элемента. Именно выполнение последних может привести к дисбалансу дерева.

Доказано, что высота АВЛ-дерева, имеющего N узлов, примерно равна log2N. Беря в виду это, а также то, то, что время выполнения операций добавления и удаления напрямую зависит от операции поиска, получим временную сложность трех операций для худшего и среднего случая – O(logN).

Балансировка.
Если после выполнения операции добавления или удаления, коэффициент сбалансированности какого-либо узла АВЛ-дерева становиться равен 2, т. е. |h(Ti, R)-h(Ti, L)|=2, то необходимо выполнить операцию балансировки. Она осуществляется путем вращения (поворота) узлов – изменения связей в поддереве. Вращения не меняют свойств бинарного дерева поиска, и выполняются за константное время. Всего различают 4 их типа:

малое правое вращение;
большое правое вращение;
малое левое вращение;
большое левое вращение.

Оба типа больших вращений являются комбинацией малых вращений (право-левым или лево-правым вращением).

Добавление узлов
Операция вставки нового узла в АВЛ-дерево выполняется рекурсивно. По ключу данного узла, производиться поиск места вставки: спускаясь вниз по дереву, алгоритм сравнивает ключ добавляемого узла со встречающимися ключами, далее происходит вставка нового элемента; по возвращению из рекурсии, выполняется проверка всех показателей сбалансированности узлов и, в случае необходимости, выполняется балансировка. Для осуществления балансировки следует знать, с каким из рассмотренных выше случаев дисбаланса имеем дело. Допустим, мы добавили узел x в левое поддерево, для которого выполнялось h(Ti, R) < h(Ti, L), т. е. высота левого поддерева изначально превышала высоту правого. Если левое поддерево этого узла выше правого, то потребуется большое вращение, иначе – малое.

Удаление узлов.
Также как и вставку узла, его удаление удобно задать рекурсивно. Пусть x – удаляемый узел, тогда если x – лист (терминальный узел), то алгоритм удаления сводиться к простому исключению узла x, и подъему к корню с переопределением balance factor’ов узлов. Если же x не является листом, то он либо имеет правое поддерево, либо не имеет его. Во втором случае, из свойства АВЛ-дерева, следует, что левое поддерево имеет высоту 1, и здесь алгоритм удаления сводиться к тем же действиям, что и при терминальном узле. Остается ситуация когда у x есть правое поддерево. В таком случае нужно в правом поддереве отыскать следующий по значению за x узел y, заменить x на y, и рекурсивно вернуться к корню, переопределяя коэффициенты сбалансированности узлов. Из свойства двоичного дерева поиска следует, что узел y имеет наименьшее значение среди всех узлов правого поддерева узла x.

99
Q

Конечный автомат

A

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

100
Q

Условия взаимного исключения (ОС)

A
  • Только один процесс может находиться в критической секции для ресурса
  • Процесс, который завершается в некритической секции, не должен мешать другим процессам
  • Нет взаимной блокировки и ресурсного голодания
  • Процесс не должен ждать доступа к критической секции ресурса, если он свободен
  • Не должно быть никаких допущений о последовательности и количестве процессов
  • Процесс может находиться в критической секции ограниченное количество времени
101
Q

Семафор

A
Целочисленный счетчик, ограничивающий количество процессов, которые могут войти в определенный участок кода
Три атомарные операции:
- Инициализация
- Увеличение (signal)
- Уменьшение (wait)
- Если 0 - блокировка
102
Q

Условия возникновения дедлоков

A
  • Взаимное исключение
  • hold and wait (процесс блокирует ресурс и ждет освобождения другого ресурса)
  • система не может “отбирать” ресурсы у процесса
  • циклическое ожидание
103
Q

Подкачка страниц

A

Страница - участок памяти стандартного размера (логический блок)
Процессы видят память постранично
Каждый процесс видит свой приватный набор страниц со своей логической адресацией
При обращении к памяти ОС конвертирует логический адрес в абсолютный
Физическая память - фреймы (одного размера со страницами)
Таблица соответствия страниц фреймам
Отдельная область памяти - отступ (оффсет)