CS general Flashcards

Question

JSON

Answer 1

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-число, за исключением того, что используется только десятичный формат (с точкой в качестве разделителя). Пробелы могут быть вставлены между любыми двумя синтаксическими элементами.

Answer 2

веб-сервер и почтовый прокси-сервер, работающий на 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 передаются параметры запроса.

Answer 3

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

Answer 4

В скрам используется всего четыре артефакта: 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). диаграмма обновляется каждый раз, когда завершается какая-либо задача.

Answer 5

Рефакторинг представляет собой процесс такого изменения программной системы, при котором не меняется внешнее поведение кода, но улучшается его внутренняя структура. Это способ систематического приведения кода в порядок, при котором шансы появления новых ошибок минимальны. В сущности, при проведении рефакторинга кода вы улучшаете его дизайн уже после того, как он написан. Правила рефакторинга Обнаружив, что в программу необходимо добавить новую функциональность, но код программы не структурирован удобным для добавления этой функциональности образом, сначала произведите рефакторинг программы, чтобы упростить внесение необходимых изменений, а только потом добавьте функцию. Перед началом рефакторинга убедитесь, что располагаете надежным комплектом тестов. Эти тесты должны быть самопроверяющимися. При применении рефакторинга программа модифицируется небольшими шагами. Ошибку нетрудно обнаружить. Написать код, понятный компьютеру, может каждый, но только хорошие программисты пишут код, понятный людям. Рефакторинг улучшает композицию программного обеспечения, облегчает понимание программного обеспечения, помогает найти ошибки, позволяет быстрее писать программы Применяйте рефакторинг при добавлении новой функции, если требуется исправить ошибку, при разборе кода Методы рефакторинга Инкапсуляция поля (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);

Answer 6

- Данные структурируются в виде объектов, каждый из которых имеет определенный тип, то есть принадлежит к какому-либо классу. - Классы – результат формализации решаемой задачи, выделения главных ее аспектов. - Внутри объекта инкапсулируется логика работы с относящейся к нему информацией. - Объекты в программе взаимодействуют друг с другом, обмениваются запросами и ответами. При этом объекты одного типа сходным образом отвечают на одни и те же запросы. - Объекты могут организовываться с более сложные структуры, например, включать другие объекты или наследовать от одного или нескольких объектов. Главное - Инкапсулируйте все, что может изменяться; - Уделяйте больше внимания интерфейсам, а не их реализациям; - Каждый класс в вашем приложении должен иметь только одно назначение; - Классы — это их поведение и функциональность. Базовые принципы ООП - Абстракция — отделение концепции от ее экземпляра; - Полиморфизм — реализация задач одной и той же идеи разными способами; - Наследование — способность объекта или класса базироваться на другом объекте или классе. Это главный механизм для повторного использования кода. Наследственное отношение классов четко определяет их иерархию; - Инкапсуляция — размещение одного объекта или класса внутри другого для разграничения доступа к ним. Используйте следующее вместе с наследованием - Делегация — перепоручение задачи от внешнего объекта внутреннему; - Композиция — включение объектом-контейнером объекта-содержимого и управление его поведением; последний не может существовать вне первого; - Агрегация — включение объектом-контейнером ссылки на объект-содержимое; при уничтожении первого последний продолжает существование . Не повторяйся (Don’t repeat yourself — DRY) Избегайте повторного написания кода, вынося в абстракции часто используемые задачи и данные. Каждая часть вашего кода или информации должна находиться в единственном числе в единственном доступном месте. Принцип единственной обязанности Для каждого класса должно быть определено единственное назначение. Все ресурсы, необходимые для его осуществления, должны быть инкапсулированы в этот класс и подчинены только этой задаче. Принцип открытости/закрытости Программные сущности должны быть открыты для расширения, но закрыты для изменений. Принцип подстановки Барбары Лисков Методы, использующие некий тип, должны иметь возможность использовать его подтипы, не зная об этом. Принцип разделения интерфейсов Предпочтительнее разделять интерфейсы на более мелкие тематические, чтобы реализующие их классы не были вынуждены определять методы, которые непосредственно в них не используются. Принцип инверсии зависимостей Система должна конструироваться на основе абстракций “сверху вниз”: не абстракции должны формироваться на основе деталей, а детали должны формироваться на основе абстракций.

Answer 7

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

Answer 8

замыкание — функция, которая ссылается на свободные переменные в своей области видимости. Замыкание, так же как и экземпляр объекта, есть способ представления функциональности и данных, связанных и упакованных вместе. Замыкание — это особый вид функции. Она определена в теле другой функции и создаётся каждый раз во время её выполнения. Синтаксически это выглядит как функция, находящаяся целиком в теле другой функции. При этом вложенная внутренняя функция содержит ссылки на локальные переменные внешней функции. Каждый раз при выполнении внешней функции происходит создание нового экземпляра внутренней функции, с новыми ссылками на переменные внешней функции. В случае замыкания ссылки на переменные внешней функции действительны внутри вложенной функции до тех пор, пока работает вложенная функция, даже если внешняя функция закончила работу, и переменные вышли из области видимости.[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 ```

Answer 9

Интроспекция — это способность программы исследовать тип или свойства объекта во время работы программы. Как мы уже упоминали, вы можете поинтересоваться, каков тип объекта, является ли он экземпляром класса. Некоторые языки даже позволяют узнать иерархию наследования объекта. Возможность интроспекции есть в таких языках, как 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-утверждений нужно сильно ограничивать формат входных данных — и обычно это лишь занимает лишнее время.

Answer 10

Код может быть исполнен нативно, в операционной системе после конвертации в машинный (путём компиляции) или же исполняться построчно другой программой, которая делает это вместо ОС (интерпретатор). Компилируемый язык — это такой язык, что программа, будучи скомпилированной, содержит инструкции целевой машины; этот машинный код непонятен людям. Интерпретируемый же язык — это такой, в котором инструкции не исполняются целевой машиной, а считываются и исполняются другой программой (которая обычно написана на языке целевой машины). Главное преимущество компилируемых языков — это скорость исполнения. Поскольку они конвертируются в машинный код, они работают гораздо быстрее и эффективнее, нежели интерпретируемые, особенно если учесть сложность утверждений некоторых современных скриптовых интерпретируемых языков. Низкоуровневые языки как правило являются компилируемыми, поскольку эффективность обычно ставится выше кроссплатформенности. Кроме того, компилируемые языки дают разработчику гораздо больше возможностей в плане контроля аппаратного обеспечения, например, управления памятью и использованием процессора. Примерами компилируемых языков являются C, C++, Erlang, Haskell и более современные языки, такие как Rust и Go. Проблемы компилируемых языков, в общем-то, очевидны. Для запуска программы, написаной на компилируемом языке, её сперва нужно скомпилировать. Это не только лишний шаг, но и значительное усложнение отладки, ведь для тестирования любого изменения программу нужно компилировать заново. Кроме того, компилируемые языки являются платформо-зависимыми, поскольку машинный код зависит от машины, на которой компилируется и исполняется программа. В отличие от компилируемых языков, интерпретируемым для исполнения программы не нужен машинный код; вместо этого программу построчно исполнят интерпретаторы. Раньше процесс интерпретации занимал очень много времени, но с приходом таких технологий, как JIT-компиляция, разрыв между компилируемыми и интерпретируемыми языками сокращается. Примерами интерпретируемых языков являются PHP, Perl, Ruby и Python. Вот некоторые из концептов, которые стали проще благодаря интерпретируемым языкам: ``` Независимость от платформы; Рефлексия; Динамическая типизация; Меньший размер исполняемых файлов: Динамические области видимости. Основным недостатком интерпретируемых языком является их невысокая скорость исполнения. Тем не менее, JIT-компиляция позволяет ускорить процесс благодаря переводу часто используемых последовательностей инструкции в машинный код. ``` Байткод-языки — это такие языки, которые используют для исполнения кода как компиляцию, так и интерпретацию. Java и фреймворк .NET — это типичные примеры байткод-языков. В байткод-языке сперва происходит компиляция программы из человекочитаемого языка в байткод. Байткод — это набор инструкций, созданный для эффективного исполнения интерпретатором и состоящий из компактных числовых кодов, констант и ссылок на память. С этого момента байткод передаётся в виртуальную машину, которая затем интерпретирует код также, как и обычный интерпретатор. При компиляции кода в байткод происходит задержка, но дальнейшая скорость исполнения значительно возрастает в силу оптимизации байткода. Кроме того, байткод-языки являются платформо-независимыми, превосходя при этом по скорости интерпретируемые. Для них также доступна JIT-компиляция. компилируемые языки являются самыми эффективными, поскольку они исполняются как машинный код и позволяют использовать аппаратное обеспечение системы. Однако это вводит дополнительные ограничение на написание кода и делает его платформо-зависимым. Интерпретируемые же языки не зависят от платформы и позволяют использовать такие техники динамического программирования, как метапрограммирование. Тем не менее, в скорости исполнения они значительно уступают компилируемым языкам.

Answer 11

Шаблон проектирования, или паттерн, в разработке программного обеспечения — повторяемая архитектурная конструкция, представляющая собой решение проблемы проектирования, в рамках некоторого часто возникающего контекста. Будьте осторожны шаблоны проектирования не являются решением всех ваших проблем; не пытайтесь использовать их в обязательном порядке — это может привести к негативным последствиям. Шаблоны — это подходы к решению проблем, а не решения для поиска проблем; если их правильно использовать в нужных местах, то они могут стать спасением, а иначе могут привести к ужасному беспорядку. Шаблоны бывают следующих трех видов: Порождающие. Структурные. Поведенческие. Порождающие шаблоны — шаблоны проектирования, которые абстрагируют процесс инстанцирования. Они позволяют сделать систему независимой от способа создания, композиции и представления объектов. Шаблон, порождающий классы, использует наследование, чтобы изменять наследуемый класс, а шаблон, порождающий объекты, делегирует инстанцирование другому объекту. Существуют следующие порождающие шаблоны: ``` простая фабрика (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). ```

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

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

Answer 16

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

Answer 17

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

Answer 18

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

Answer 19

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

Answer 20

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

Answer 21

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

Answer 22

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

Answer 23

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

Answer 24

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

Answer 25

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

Answer 26

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

Answer 27

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

Answer 28

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

Answer 29

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

Answer 30

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

Answer 31

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

Answer 32

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

Answer 33

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

Answer 34

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

Answer 35

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

Answer 36

- постоянные множители (константы) можно опускать - многочлен более высокой степени растет быстрее - экспонента растет быстрее многочлена - многочлен растет быстрее логарифма - медленно растущие слагаемые можно опускать ``` 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) ```

Answer 37

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

Answer 38

- Идентификатор - Состояние - Приоритет - Счетчик команд - Указатели на память - Контекст - Информация о статусе I/O - Другая информация процессы образуют очередь (по приоритету и живому порядку)

Answer 39

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

Answer 40

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

Answer 41

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

Answer 42

Константный — 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) зависит от квадрата размера входного массива. Несмотря на то, что такой ситуации иногда не избежать, квадратичная сложность — повод пересмотреть используемые алгоритмы или структуры данных. Проблема в том, что они плохо масштабируются. (напр., пузырьковая сортировка)

Answer 43

Метод 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.

Answer 44

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

Answer 45

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

Answer 46

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

Answer 47

Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее — нет. Важный момент: сортировка вставками обрабатывает элементы массива по порядку. Поскольку алгоритм проходит по элементам слева направо, мы знаем, что все, что слева от текущего индекса — уже отсортировано. мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex. Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки. Сложность в лучшем случае О(n), в худшем O(n^2)

Answer 48

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

Answer 49

Алгоритм, по принципу функционирования, входит в класс обменных сортировок (сортировка перемешиванием, пузырьковая сортировка и др.), выделяясь при этом высокой скоростью работы. Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков. В следующих пяти пунктах описана общая схема разбиения массива (сортировка по возрастанию): вводятся указатели 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

Answer 50

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

Answer 51

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).

Answer 52

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

Answer 53

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

Answer 54

Интерполирование – нахождение промежуточных значений величины по имеющемуся дискретному набору известных значений. Интерполяционный поиск работает только с упорядоченными массивами; он похож на бинарный, в том смысле, что на каждом шаге вычисляется некоторая область поиска, которая, по мере выполнения алгоритма, сужается. Но в отличие от двоичного, интерполяционный поиск не делит последовательность на две равные части, а вычисляет приблизительное расположение ключа (искомого элемента), ориентируясь на расстояние между искомым и текущим значением элемента. mid = left + (((key-A[left])*(right-left))//(A[right]-A[left])) Интерполяционный поиск в эффективности, как правило, превосходит двоичный, в среднем требуя log(log(N)) операций. Тем самым время его работы составляет O(log(log(N))). Но если, к примеру, последовательность экспоненциально возрастает, то скорость увеличиться до O(N), где N (как и в предыдущем случае) – общее количество элементов в списке. Наибольшую производительность алгоритм показывает на последовательности, элементы которой распределены равномерно относительно друг друга.

Answer 55

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

Answer 56

Очередь Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов. Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO). Очереди часто используются в программах для реализации буфера, в который можно положить элемент для последующей обработки, сохраняя порядок поступления. Например, если база данных поддерживает только одно соединение, можно использовать очередь потоков, которые будут, как ни странно, ждать своей очереди на доступ к БД. Метод Enqueue Поведение: Добавляет элемент в очередь. Сложность: O(1). Новые элементы очереди можно добавлять как в начало списка, так и в конец. Важно только, чтобы элементы доставались с противоположного края. Метод Dequeue Поведение: Удаляет первый помещенный элемент из очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException. Сложность: O(1). Поскольку мы вставляем элементы в начало списка, убирать мы их будем с конца. Если список пуст, кидается исключение. Метод Peek Поведение: Возвращает элемент, который вернет следующий вызов метода Dequeue. Очередь остается без изменений. Если очередь пустая, кидает InvalidOperationException. Сложность: O(1). Метод Count Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая. Сложность: O(1).

Answer 57

Двусторонняя очередь (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).

Answer 58

Метод 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.

Answer 59

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

Answer 60

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

Answer 61

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

Answer 62

Множество — это коллекция, которая реализует основные математические операции над множествами: пересечения (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 — количество элементов переданного и текущего множеств соответственно. Симметрическая разность — это все элементы, которые содержатся только в одном из рассматриваемых множеств.

Answer 63

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

Answer 64

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

Answer 65

Алгоритм голландского ученого Эдсгера Дейкстры находит все кратчайшие пути из одной изначально заданной вершины графа до всех остальных. С его помощью, при наличии всей необходимой информации, можно, например, узнать какую последовательность дорог лучше использовать Минусом данного метода является невозможность обработки графов, в которых имеются ребра с отрицательным весом, оскольку самые выгодные пути только предстоит найти, в каждый элемент вектора 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 вершины не будут исследованы.

Answer 66

Алгоритм Флойда – Уоршелла – динамический алгоритм вычисления значений кратчайших путей для каждой из вершин графа. Метод работает на взвешенных графах, с положительными и отрицательными весами ребер, но без отрицательных циклов, являясь, таким образом, более общим в сравнении с алгоритмом Дейкстры, т. к. последний не работает с отрицательными весами ребер, и к тому же классическая его реализация подразумевает определение оптимальных расстояний от одной вершины до всех остальных. Ключевая часть алгоритма, состоя из трех циклов, выражения и условного оператора, записывается довольно компактно: Для k от 1 до |V| выполнять Для i от 1 до |V| выполнять Для j от 1 до |V| выполнять Если D[i][k]+D[k][j]

Answer 67

Также как и алгоритм Дейкстры, алгоритм Беллмана — Форда вычисляет во взвешенном графе кратчайшие пути от одной вершины до всех остальных. Он подходит для работы с графами, имеющими ребра с отрицательным весом. Но спектр применимости алгоритма затрагивает не все такие графы, ввиду того, что каждый очередной проход по пути, составленному из ребер, сумма весов которых отрицательна (т. е. по отрицательному циклу), лишь улучшает требуемое значение. Бесконечное число улучшений делает невозможным определение одного конкретного значения, являющегося оптимальным. В связи с этим алгоритм Беллмана — Форда не применим к графам, имеющим отрицательные циклы, но он позволяет определить наличие таковых Решить задачу, т. е. найти все кратчайшие пути из вершины 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 раз позволит выявить наличие отрицательного цикла в графе.

Answer 68

нахождение всех простых чисел до некоторого заданного числа 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)) операций. Поэтому уместнее использовать данный метод чем, например, наиболее тривиальный и затратный перебор делителей.

Answer 69

В эффективности данный алгоритм превосходит метод Евклида, что связано с использованием сдвигов, то есть операций деления на степень 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←k*2, до тех пор, пока хотя бы одно из чисел A или B не станет нечетным; если A – четное, а B – нечетное, то делим A, пока возможно деление без остатка; если B – четное, а A – нечетное, то делим B, пока возможно деление без остатка; если A≥B, то заменим A разностью A и B, иначе B заменим разностью Bи A. после выхода из 2-ого пункта, остается вернуть в качестве результата произведение B и k: НОД(A, B)=B*k.

Answer 70

Пусть имеется некоторая степень x^n, где x – действительное число, а n – натуральное. Тогда для x^n справедливо равенство: x^n = (x^m)^k При этом m*k=n Общая формула перехода: x^n = x^(n-1)*x В программе, реализующей алгоритм быстрого возведения в степень, используются указанные свойства: если степень n четная, то переходим к степени вдвое меньшей, иначе заменяем по имеющимся правилам нечетную степень на четную.

Answer 71

Хеш-таблицей называется структура данных, предназначенная для реализации ассоциативного массива, такого в котором адресация реализуется посредством хеш-функции. Хеш-функция – это функция, преобразующая ключ 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 ячеек таблицы заполнены. Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. Последовательность проб задается специальной функцией, например интервал между просматриваемыми ячейками может вычисляться линейно, или увеличиваться на некоторое изменяющееся значение.

Answer 72

Хеш-функция – функция, преобразовывающая входную последовательность данных произвольного размера в выходную последовательность фиксированного размера. Процесс преобразования данных называется хешированием. Результат хеширования – хеш-код (хеш-сумма, хеш). При решении класса практических задач выбирается такая хеш-функция, которая является наиболее оптимальной именно для данного класса. В общем случае следует использовать «хорошую» функцию. Когда хеш-функцию называют «хорошей», то подразумевают под этим, что она: вычисляется достаточно быстро; сводит к минимуму число коллизий. Предотвратить коллизии могут далеко не все хеш-функции, но «хорошие» способны минимизировать вероятность их появления. При определенных обстоятельствах (известна некоторая информация о ключах), можно найти идеальную хеш-функцию, т. е. такую, которая полностью исключает возможность появления коллизий. Метод деления. Пусть k – ключ (тот, что необходимо хешировать), а N – максимально возможное число хеш-кодов. Тогда метод хеширования посредством деления будет заключаться во взятии остатка от деления k на N: h(k)=k mod N, где mod – операция взятия остатка от деления. Во избежание большого числа коллизий рекомендуется выбирать N простым числом, и не рекомендуется степенью с основанием 2 и показателем m (2m). Вообще, по возможности, следует выбирать N, опираясь на значения входящих ключей. Метод умножения. Получить из исходной последовательности ключей последовательность хеш-кодов, используя метод умножения (мультипликативный метод), значит воспользоваться хеш-функцией: h(k)=⌊N*({k*A})⌋ Здесь A – рациональное число, по модулю меньшее единицы (0

Answer 73

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

Answer 74

Сбалансированным называется такое двоичное дерево поиска, в котором высота каждого из поддеревьев, имеющих общий корень, отличается не более чем на некоторую константу 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.

Answer 75

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

Answer 76

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

Answer 77

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

Answer 78

- Взаимное исключение - hold and wait (процесс блокирует ресурс и ждет освобождения другого ресурса) - система не может "отбирать" ресурсы у процесса - циклическое ожидание

Answer 79

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