Что такое гал в алгоритме
GAL files are simply text files with the extension .gal . For example, foo.gal is a valid GAL filename. Each file defines a single GAL specification that may contain one or more type declarations, a main instance, and properties.
GAL Type Declaration
A GAL type declaration (or just a GAL) is characterized by a name, and contains a sequence of declarations (variables, transitions).
A GAL is declared with the keyword gal, followed by the system name. The name must start with a letter of the alphabet and should be a C-style identifier (only using letters, underscore and numbers).
A good practice is to give a meaningful name to the system created, particularly if it will be reused in a Composite ITS definition.
The body (variable and transitions) of the system name are then placed between a pair of braces.
Here is a declaration of an example GAL system named emptySystem.
Variable declarations
A GAL model declares variables. The variables manipulated in GAL can be integers or fixed size arrays of integer. There are no dedicated Boolean or char basic types, nor struct declarations.
There are no dynamic allocation or variable length structures such as lists. To model these using an array is only possible if an upper bound on its size is known a priori.
Integers are C-style signed integers, 32 bit (4 bytes) wide, with the same overflow semantics as in C ( (2 31 -1) + 1 = — 2 31 ).
In this section, we describe how variables of a GAL are declared.
Integer variables
Plain integer variables are introduced with the keyword int followed by the variable name starting with a letter. The variable name may contain alphanumeric characters as well as the “.” character (which may help trace structs from of your source language if you are using GAL as a transformation target).
The name must be unique, and cannot be reused for another variable.
Each variable can be initialized, this is done using the “=” symbol followed by the initial value of this variable. The default initial value for integer variables is 0.
The initial value can be expressed using an integer expression built of constants and/or type parameters, but it cannot refer to other variables. The declaration ends with a semicolon.
Below is an example of a system with two GAL variable declarations :
Array declarations
An array declaration allows to declare a fixed size array of integers. Like simple integer variables, each entry in the array needs to be initialized.
A GAL array variable is declared using the keyword array followed by the array size N within square brackets, then the array name.
Each cell of the array needs to be initialized, to this end, a list of N comma separated integers surrounded by parenthesis (or integer expressions of constants and/or type parameters) should be provided. If no initialization is provided, all array cells are set to 0 initially. A semicolon ends the array declaration.
Here is an example of a system with a declaration of an array:
Expressions
GAL expressions can be either integer expressions or Boolean expressions, depending on the context. We give here the syntax of these expressions, which is mostly directly taken from C (or Java).
Usual priorities between operators are observed (e.g. Boolean AND stronger than OR, integer multiplication stronger than addition). If in doubt, parenthesis can be used to force an evaluation order.
Boolean expressions
Boolean expressions are allowed in guards of transitions. It is also possible to write arithmetic expressions, with boolean appearance (as in C), which will be worth 1 or 0 depending on whether they are true or false (see Wrapper)
The basic expressions are true and false.
The usual boolean operators are present in GAL,
| Operation | Operator |
| Disjunction (OR) | || |
| Conjunction (AND) | && |
| Negation (NOT) | ! |
Basic Boolean expressions can be any kind of comparison of two integer expressions using one of the comparison operators :
| Operation | Operator |
| Greater than | > |
| Lesser than | < |
| Greater or equal | >= |
| Lesser or equal | <= |
| Equals | == |
| Not equal | != |
Integer expressions
Binary Operators
The standard linear integer arithmetic operators are provided. Division is integer division.
| Operation | Operator | Example | Result |
| Addition | + | 3 + 2 | 5 |
| Subtraction | — | 3 — 2 | 1 |
| Modulo | % | 7 % 2 | 1 |
| Division | / | 7 / 2 | 3 |
We also provide multiplications useful in some contexts
| Operation | Operator | Example | Result |
| Multiplication | * | 3 * 2 | 6 |
| Power | ** | 2 ** 3 | 8 |
Finally, we offer bitwise manipulation operators :
| Operation | Operator | Example | Result |
| bitwise OR | | | 2 | 3 | 3 |
| bitwise AND | & | 2 & 3 | 2 |
| bitwise XOR | ^ | 2 ^ 3 | 1 |
| Left shift | << | 1 « 3 | 8 |
| Right shift | >> | 7 » 2 | 1 |
Unary operators
Standard prefix unary operators are provided :
Terminal expressions
Terminal integer expressions are simply :
- a reference to plain integer variables, var
- a reference the cell of an array tab[index],
- or a reference to a parameter $param
When accessing a cell of an array tab[index], the index expression is inductively an arbitrarily complex integer expression.
Wrapper of boolean expressions
Boolean expressions can be raised to integer expressions with the interpretation 1 for true and 0 for false, by surrounding the Boolean expression with parenthesis.
This encapsulation of Boolean expressions as integers enables many (programming/modeling) tricks commonly encountered in C.
Note that the reverse is not possible, in particular, assignments cannot be nested within Boolean conditions, they do not return a value like in C. Hence all Boolean expressions are by construction side-effect free.
Example : myVariable = (a == 0) * 100 ;_//myVariable is 100 or 0_
Transitions
Transition declaration
Transitions allow to step atomically from a source state to a (set of) successor state(s). Transitions are enabled by a guard, which is a Boolean expression and may carry a label that is a string. If the guard is true in the current state, the transition can be fired, executing all the actions it contains in sequence. Actions can be assignments, calls to a label or other statements as described below. Labeled actions cannot be fired if they are not called from another transition or synchronized externally (see ITS composite). Transitions without a label are “private” and can be fired any time their guard is true, with interleaving semantics. A self-contained GAL (not intended for further composition) typically bears no labels on transitions.
Syntactically, a transition is declared with the keyword transition , followed by a unique identifier for the transition. The transition guard (a Boolean expression) is surrounded by brackets (that can be “true” if the transition is always enabled). The transition can optionally be labeled, as introduced with the keyword label followed by double quoted string defining the label. Finally the statements comprising the transition body are placed in a block surrounded by curly braces.
This example system contains two transitions of which one is labeled :
Statements
Statements are operations that generally update the state of the system variables.
Statements are sequentially composed using a semi-column ; within the body of a transition.
The most common type of statement is the assignment of an integer expression on system variables to a system variable.
The call to a label statement introduces non-determinism in the execution by offering several alternatives (any transition bearing the label can be fired).
Other basic statements include an if-then-else control structure, and an *abort instruction.
Other statements such as limited for-loop control structure are provided (see parametric GAL).
Assignment
Assignments are composed of a left-hand side (lhs), that must be a reference to a variable or to the cell of an array, and a right-hand side (rhs) that is an integer expression.
Example : a=3+(b-x);
When the lhs is a reference to an array, the target index within the array can be expressed using an arbitrarily complex integer expression.
Example : tab[a+b]= 42;
GAL also support increment and decrement to a variable, using a += or -= notation. The semantics are the same as in other languages : a+=b is equivalent to a=a+b, a-=b is equivalent to a=a-b, where a is a variable and b an arbitrary integer expression.
Call action
The call action allows to call a label of the current GAL system, i.e. non-deterministically choose any of the enabled transitions that bear this label, and execute its actions.
This powerful mechanism allows to model much more concisely when the transition relation carries non-determinism.
For instance, a transition that non deterministically assigns a value between 0 and N to two variables X and Y can be represented as containing two calls to labels “assignX” and “assignY”. We can then build N transitions tX0, tX1… (resp. tY0, tY1…) bearing label “assignX” (resp. “assignY”), each of them with a [true] guard and a single assignment of a value to the designated variable. We thus accurately represent the transition relation with 2N+1 transitions rather than N^2 transitions.
Calls can also be used to simulate some control structures. For instance, If-Then-Else(cond, actif, actelse) can be simulated by two transitions bearing label “ite”, with guards cond and not cond respectively, and body actif and actelse respectively.
Calling label “ite” in a transition body is like executing an if-then-else block.
Note that the whole ITS semantics is defined using sets, i.e. the successor relation returns a set of successors. Hence if no labeled action is enabled in some states at the point of call, no successors are produced, canceling the effect of the calling the enclosing transition for the concerned states, like an abort action.
Syntactically, a call is introduced by the keyword self , followed by a column ‘.’, followed by a label between double quotes.
This example shows a use of a call to non deterministically update a variable.
If-Then-Else action
To ease modeling, GAL provide the if-then-else alternative control structure. As mentioned above this behavior can also be implemented using calls.
The semantics are those you could expect, if the condition is true the “if” block is executed, otherwise the “else” block is executed (or nothing is done if there is no else block).
The syntax is taken from C or Java, if followed by a Boolean condition between parenthesis, followed by a block between curly braces. Optionally, the statement can be completed by an else followed by a second block of actions.
This example shows a use of an if then else to invert the value of a Boolean variable.
Abort action
The semantics of GAL (based on ITS definitions) allow a statement to return a set of successors, since GAL natively support non-determinism. The abort statement returns the empty set of successors, hence it interrupts the current transition which then yields no successors.
The abort statement is mainly used to model transition relations where Boolean conditions with side effects need to be represented. It allows to have a transition with a guard, a few statements then typically an if-then-else or a variant using a call, of which some branches may encounter abort and cancel the transition effect for this branch.
The following example shows a use of abort to model the transition relation of a Time Petri net with two places a and b, and a transition t that moves tokens from a to b, with earliest firing time eft and latest firing time lft. Time cannot elapse if an enabled transition has reached its latest firing time, but this test is complex, particularly when there are many transitions. Use of abort allows to concisely represent the semantics.
Gale Shapley algorithm
Gale Shapley algorithm is used to solve the stable matching problem. It is also known as the Deferred Acceptance algorithm.
Stable Matching Problem
Stable Matching Problem (also known as Stable Marriage Problem) is the problem to find stable matching between two equally sized sets. The matching is based on the given order of preferences. A matching from one set to the other set is a bijection. Every element in one set is paired with an element in the other set.
Let (A, B) be two matched pairs. A belongs to the first set and B belongs to the second set. (A, B) is an not stable match if
- There is an element X in the first set that prefers B more than A prefers B and
- B also prefers X more than it prefers A.
- There is an element Y in the second set that prefers A more than B prefers A and
- A also prefers Y more than it prefers B.
Gale Shapley algorithm forms matching between elements of the two set such that every matched pair is stable.
To make things simpler, we will define the Stable Matching Problem as a problem to engage N men and N women. We define the problem as
Given N men and N women with their preferences of members of the opposite sex. We need to match each man with a woman such that all matched pairs are stable.
Steps
- Each unengaged man proposes to the woman he prefers the most to whom he has not proposed yet.
- If a man proposes to an unengaged woman then both the man and woman are engaged to each other.
- If a man proposes to a woman who is already engaged, then the woman checks who she prefers more. If the woman prefers the new man over her currently engaged man, then the woman breaks her engagement with the currently engaged man and is now engaged to the new man. The man to whom the woman was previously engaged becomes unengaged.
- The above steps are repeated until everyone is engaged.
Prove that everyone is engaged at the end of algorithm
At the end of the algorithm, all men and women will be engaged. This is because each woman will eventually be proposed by atleast one man, thus every woman will be engaged to someone.
Prove all matching pairs are Stable
We will show that all pairs formed by Gale Shapley algorithm are stable. Refer to the previous section to understand what a stable pair is.
Let (John, Lucy) and (Tim, Lia) be two matched pairs obtained on completion of the Gale Shapley algorithm. It is not possible for John and Lia to prefer each other over their current partner. If John prefers Lia over Lucy, then John would have proposed to Lia before Lucy. John and Lia not being married indicate that Lia dumbed John over someone she prefers more, that is Tim. Similarly, if you assume Lia prefers John more than Tim. John and Lia not being engaged mean John never proposed to Lia. That means John is already engaged to a girl who he prefers more than he prefers Lia. Thus, we conclude that all matched pairs are stable.
Program to Implement Gale Shapley algorithm
In this section, we will discuss how to implement Gale Shapley algorithm.
Input
The input consists of two N X N matrices – manPref and womanPref. Each row of manPref is a list of preferences of women. Similarly, each row of womenPref is a list of preferences of men. The men/women that appear first in the list are preferred over those that appear last.

The program is well commented. If you still face any problem, feel free to comment.
Output
Time Complexity
The time complexity of Gale Shapley algorithm is
. The total size of
matrix is
. We visit each index of
at-most once. Thus, the time complexity is
.
Existence of Multiple Matchings
Stable matchings are not unique. Man and women can be engaged in multiple ways.
In the Gale Shapley algorithm, if a man proposes to a woman, then man and woman are matched such that the woman chooses the best man out of all the man who proposed to her. Whereas if a woman proposes to a man, then the man chooses the best woman out of all the woman who proposed to him.
PAL, GAL и путешествие в цифровое ретро
Идея сделать цифровые логические микросхемы с изменяемой структурой была всегда. Почему? Достаточно посмотреть на толстенный каталог чипов серии TTL 74xx (или советской К155), чтобы такая идея самозародилась. В СССР почти у каждого инженера и радиолюбителя был справочник В.Л. Шило «Популярные цифровые микросхемы», который вышел каким-то невероятным тиражом. Но всё равно, хотелось иметь некий «универсальный кристалл», из которого можно сделать все остальные микросхемы (ну хорошо, не все, но многие).
Конечно же, полупроводниковая промышленность тоже была не прочь удовлетворить такой спрос. Поэтому, начиная с конца 1960-х, на рынке каждый год появлялось огромное количество подобных устройств из класса PLD (Programmable Logical Device), самых разнообразных архитектур. Это было интереснейшее время! На рынке постоянно появлялось что-нибудь новенькое. Здесь были и различные ULA и БМК и EPROM-устройства на базе пережигаемых перемычек (82Sxxx) и PLA, у которых программировались оба слоя: «И» и «ИЛИ» (привет нашим К556РТ1 и К556РТ2) и т.д. Обзор этих ретро-технологий – тема для отдельной статьи. Мы же сделаем лишь обзор того, что «выстрелило» и стало мэйнстримом.
Сразу хочется попросить извинения у опытных электронщиков и разработчиков FPGA. Эта статья нисколько не имеет цели вторгнуться на их территорию, а только дает исторический обзор «как это было».
А в конце мы попробуем соединить теорию с какой-то осмысленной практикой, поглядеть, как это применяется в реальной жизни. Светодиод, например, зажечь или там даже семисегментный индикатор…
Так вот, в далекие 1970-е годы компания-производитель ПЗУ Monolithic Memories Inc. (MMI) выпустила на рынок очередное семейство программируемых чипов. Семейство ВНЕЗАПНО оказалось настолько удачным, что в 1978 году MMI зарегистрировала торговую марку PAL® (Programmable Array Logic) и стала лицензировать технологию таким гигантам, как Texas Instruments (серия TIBPAL), National Semiconductor, Philips (PLUS), AMD (AMPAL) и другим.

Даже в СССР не отставали и выпустили клоны, серию К1556.

В чем же секрет? Спроектированное инженерами и для инженеров семейство MMI PAL представляло собой практически чистое воплощение идеи ДНФ (Дизъюнктивная Нормальная Форма).
Здесь надо сделать логическое отступление и взглянуть, что же это такое, ДНФ и откуда оно взялось.
Матлогика
Дискретная математика и мат-логика вообще – наука большая и развесистая. Мы не будем залезать в дебри и высокую теорию, а лишь рассмотрим узкий срез — работу с логическими (булевыми или же переключательными) функциями и соответствующими комбинационными схемами.
Лирическое отступление: есть огромное искушение ничего не писать, а просто посоветовать взять и прочитать недавно переведенный учебник Харрис&Харрис «Цифровая схемотехника и архитектура компьютера», а конкретно главу 2 «Проектирование комбинационной логики». Это отличная книга! Там даже есть параграф про PAL (п.5.6 «Матрицы логических элементов»), но такое ощущение, что его безжалостно сократили в очередной редакции.
А для тех, кто захотел канонично, «от печки», разобраться в предмете поглубже (бывает!) можно порекомендовать книги 60-х годов по проектированию ЭВМ. Например, книгу “Синтез цифровых автоматов” В.М. Глушкова (тот самый, который ОГАС!) (М. Государственное издательство физико-математической литературы, 1962г). Книга настолько олдовая, что фамилия Карно записывается как Карнаут. Или можно предложить книгу ”Синтез схем электронных цифровых машин” (Е.Н.Вавилов, Г.П.Портной М. ”Советское радио” 1963).
В современных отечественных учебниках, чем дальше, тем больше этот раздел ужимается.
Например учебник Угрюмов Е.П. «Цифровая схемотехника» издания 2007 года еще содержал главу про PAL, а издания 2010 — уже нет. В настоящее время данная наука почти полностью перекочевала в пыльные бумажные методички кафедр по специальности 230101. Вдобавок, попытка дать студентам этот материал наталкивается на стойкое сопротивление: разговоры про «основы» воспринимаются учащимися как «too old» то есть как совершенно ненужный, устаревший хлам. Даже тут, на Хабре есть несколько статей на данную тему, и комментарии наполнены стонами ”Да-да! Нас тоже зачем-то насиловали этим весь первый курс!”.
Так вот, автор сбрасывает себя обязанность писать про пресловутые ”основы”. Предполагается, что читатель, который заглянул на огонек, всё-таки понимает, что такое булева алгебра, что такое И, ИЛИ, НЕ, знает теорему де Моргана и умеет читать схемы на логических элементах.
ПРИМЕЧАНИЕ: Мне тут подсказывают, что в современном курсе цифровой электроники эта дисциплина (Дискретная математика) и Цифровая схемотехника чаще всего разделены на два предмета и учебники у них — разные. А Харрис&Харрис в попытке впихнуть все в одну книгу породил монстра на 1600 страниц. Ну OK.
Ах да, ДНФ. В старых книжках говорится (объясняется — почему), что при достаточно сложном логическом выражении его лучше всего представить (и это можно сделать для любого выражения!) в виде дизъюнктивной нормальной формы (sum of product, SOP). Несмотря на страшное название, это очень просто. Возьмем логическую функцию Y от трех переменных, A, B, C. Пусть она принимает значение «истина» тогда и только тогда, когда все три входные переменные равны нулю или же все они равны единице. В ДНФ это запишется крайне просто:

Это так называемая алгебраическая форма. Операция «ИЛИ» тут записывается как «+», а операция «И» — как умножение и, как в обычной алгебре, опускается. Так получилось, что существует множество форматов записи (синтаксисов) булевых выражений. Вот в другой записи:

Си-шное выражение для bool переменных:

Или даже так (синтаксис PALASM):

То есть ДНФ (в алгебраической форме) выглядит как цепочка сложений т.е. многочлен (логическое ИЛИ) из произведений (логическое И) входных переменных (sum of product), причем только тех комбинаций, для которых должна получаться «истина». Интуитивно это довольно понятно: Истина, когда это И это, ИЛИ же когда то И то. Как выше упоминалось, в форме ДНФ можно представить любое логическое выражение (и помним, что мы не углубляемся в СДНФ, КНФ, СКНФ, критерий Поста и т.д.).
Оптимизация, оптимизация
Другая, ныне забытая дисциплина при изучении данной науки – это методы оптимизации логических выражений. Современному разработчику практически не надо заботиться об оптимизации, за него все сделает «умный» компилятор. Да, напрямую к PAL оптимизация выражений отношения не имеет, но чтобы понять дух эпохи, давайте посмотрим.
На самом деле, методов оптимизации существует довольно много. Самый простой — алгебраический, когда преобразуется выражение по законам булевой алгебры (она слегка похожа на обычную, но чуть другая). Можно еще упомянуть теорему Квайна (и метод Квайна – Мак-Класки), метод получения тупиковых форм, метод испытания членов, метод импликантных матриц и т.д. Отдельно где-то парит полином Жегалкина на базисе Исключающее-ИЛИ. Методов много. Самыми удобными оказались диаграммы Вейча или, в усовершенствованном виде — карты Карно.
Для изучения механизма работы карты Карно можно, опять же, отправить к учебнику Харрис&Харрис глава 2.7. Но очень уж изящное решение! Кроме того, карты Карно иногда спрашивают на собеседованиях. Карты Карно предназначены для визуального безкомпьютерного упрощения выражений с количеством переменных до 6.
Давайте посмотрим на типичную карту Карно, например на 4 переменных:

Самое важное (и в чем состоит суть изобретения Мориса Карно) – это то, что соседние клеточки по вертикали и горизонтали отличаются значением ровно одной переменной. А если в соседних ячейках стоят «1» то эту переменную можно исключить. Причем «края» карты Карно подразумеваются «склеенными». Так что наша функция ужимается до

Если попытаться изобразить в 3D карту Карно для 4-х переменных, ее можно будет представить как развертку такого «угловатого тора», имеющего 16 граней (нарисовано в OpenSCAD ).

Возвращаясь к PAL
Обогатившись такими знаниями, давайте вернемся к нашим PAL-кам и посмотрим на их внутреннее устройство. И опять же, хорошим подспорьем тут будет учебник Харрис&Харрис «Цифровая схемотехника и архитектура компьютера», а конкретно параграф про PAL (п.5.6 «Матрицы логических элементов»).
При разработке PAL применяется своеобразная графическая запись, первоначально, видимо, предназначенная для ручного кодирования (до появления PALASM).
Давайте возьмем одну ячейку PAL, самого классического PAL16L8:

Итак, сверху вниз идут колонки – входные переменные. Из них: 10 шт. – это самые настоящие входы, то есть «ножки» микросхемы, а 6 шт. – это «возвраты» внутри чипа, что позволяет создавать более сложные многоступенчатые выражения. Понятно, что каждая из этих 16 переменных существует в прямой и инверсной форме, итого мы видим 16*2=32 колонки. Слева мы видим ввод одной переменной в матрицу, в прямом и инверсном виде (вывод 2).
Все эти «вертикальные» переменные одновременно поступают на элементы «И», которые могут использовать некоторые их них (а могут не использовать). Схема примерно такая (тут нарисованы две входные переменные и два элемента «И»):

Мы видим «плавкие перемычки» (fuse, F1..F4 и F5..F8), которые задают, какие переменные подключены к «И». Именно эти fuse и программируются и задают логическую функцию PAL. Картинка получается довольно громоздкая, поэтому применяют такую сокращенную графическую запись (крестики – это подключенные входы):

Вернемся к схеме ячейки PAL:

Как видите, в каждой строке (горизонтали) можно собрать функцию «И» из 16 (32, учитывая инверсию) возможных входов (переменных). То есть такая вот строка – это на самом деле 32-входовый элемент «И» (программируемый). Чуть позже мы посмотрим, как эти соединения выглядят в прошивке.
Далее по схеме мы видим, что в PAL16L8 имеется 7 штук таких «И-шек», объединенных по «ИЛИ». Структура у «ИЛИ» у PAL фиксированная (в отличии от PLA и других архитектур) и не программируется. Кстати, обратите внимание, можно использовать меньшее количество «ИЛИ» (просто не задавая функций у «И» в ячейке), а вот больше – нельзя!
Как несложно заметить, такая конструкция и является физической реализацией ДНФ или SOP (Sum Of Product – то есть сумма произведений). Бинго!
Такие устройства стали называться SPLD (Simple PLD) в противовес CPLD (Complex PLD) и FPGA. Про CPLD кстати, имеется отдельная статья.
Такая простая и элегантная конструкция быстро стала чрезвычайно популярной и стала быстро вытеснять остальные семейства. Вот почему такие гранды, как AMD, Philips, National Semiconductor лицензировали ее.
Популярность PAL-ок пришлась на середину 80-х и начало 90-х. Многие производители чипов, прямо в Datasheet-ах публиковали листинги на PALASM для подключения своих микросхем к другим чипам и к разнообразным микропроцессорным шинам. Некоторые платы начала 90-х представляли собой «россыпи» PAL-ок, на которых были реализованы сложнейшие схемы. Это позволяло быстро выйти на рынок, до начала производства заказных микросхем LSI. (Погуглите, ну скажем, картинки материнской платы EISA i486 Everex Step Mega Cube или Intel iSBC 386. Все узкие микросхемы с бумажками – это PAL ).
Сейчас эту нишу занимают CPLD и FPGA.
Компания MMI выпускала книжки, содержащие массу примеров применения своих микросхем, которые сопровождались забавными рисунками (извините, утащил).

Или даже так, ужас-ужас (Текст: В этой конструкции одна PAL16R8 заменяет 15 TTL микросхем малой и средней степени интеграции ):

Семейство PAL было довольно обширное. Существовали разновидности на разное количество ячеек и входов. Были разновидности с триггерами, что позволяло делать на них синхронные схемы и даже маленькие конечные автоматы (например PAL16R8). Существовали универсальные (Versatile) разновидности, в которых можно выбирать комбинаторную логику или триггера (PAL16V8). Существовали чуть более крупные PAL-ки в 24-выводном корпусе, типа PAL22V10. Микросхемы могли быть упакованы в различные корпуса и могли быть разной «скорости», от -5 до -25 наносекунд. Наконец, существовали низкопотребляющие варианты и варианты в CMOS исполнении (например Texas Instrument TICPAL или Cypress Semiconductor PALC).

PALASM
Невероятный успех микросхемам PAL фирмы MMI принёс еще один компонент, без которого покорение рынка было бы немыслимо. Это — утилита PALASM. С ее помощью создание прошивки для PAL стало делом настолько легким и простым, что любой инженер с нормальной подготовкой, понимал идею практически сразу. В PALASM вводится названия пинов и логические выражения в человеческой алгебраической форме (которые обычно выглядят как ДНФ), после чего PALASM выдает файл прошивки для программатора (JEDEC). Грубо говоря, компания MMI сделала тот шаг, который когда-то в 1950-е прошли обычные компьютеры, при переходе от ручного выписывания двоичных кодов к более понятной записи выражений машинного языка (ассемблера). А сам PALASM первых версий, в свою очередь, был написан на языке FORTRAN IV и распространялся в исходных текстах, что позволяло запускать его на любой тогдашней машине, где был компилятор, вплоть до ранних персоналок под CP/M и DOS. Да, да, когда-то FORTRAN был общим системным языком для переноса программ…
Позже вышел PALASM2, синтаксис немного изменился, оброс разнообразными возможностями, появилось некоторое подобие макросов, оптимизатор, поддержка конечных автоматов и даже симулятор. Компания MMI тоже претерпела изменения, ее активы были поглощены AMD, потом выделены в отдельную компанию Vantis, которую позже купила Lattice Semiconductor. Сам входной язык PALASM послужил прообразом множества подобных и более продвинутых языков, его следы есть в ABEL, CUPL и в VHDL (а вообще-то он сам вырос из FORTRAN-а ).
Наиболее развитый PALASM – это версия PALASM4 v1.5a от AMD 1992 года. Понятно, что такая ретро-программа требует для запуска ретро-DOS. Но к счастью, этот вопрос давно решен. Тут нам поможет прекрасная утилита DOSBOX, позволяющая запускать DOS-программы даже на современном Windows 10 64-бит. Хотя DOSBOX вообще-то, предназначен для запуска ретро-игр, но и не-игровые DOS-утилиты неплохо в нем живут и PALASM — не исключение. Компания AMD сделала широкий жест и отпустила PALASM в Public Domain, так что пользоваться им можно совершенно легально.
Тут можно найти инструкцию, как поставить PALASM на DOSBOX и также скачать саму программу. Конфигурационный файл DOSBOX хранится в профиле пользователя
C:\Users\%USERNAME\AppData\Local\DOSBox\ dosbox-0.74.conf
Лучше дополнить секцию [autoexec]:
Из под Linux тоже можно запустить PALASM например с помощью того же DOSBOX или похожего DOSEMU.
Из PAL в GAL
При всём своём удобстве PAL-ы имели и некоторые проблемы. Одна из таких проблем состоит в том, что PAL – это однократно программируемое устройство (OTP) с плавкими титано-вольфрамовыми перемычками (Ti-W fuse). При появлении исправлений и замене прошивки приходилось старую микросхему просто выкидывать. Так что многие производители стали предлагать ”стираемые” PAL-ки. История тут длинная, можно, например, вспомнить УФ-стираемые чипы с «окошечком», или тот факт, что очень хотелось сохранить совместимость с парком программаторов и алгоритмами прошивки оригинальных PAL (серии PALCE и PEEL от International CMOS Technology (ICT) Corporation) и т.д.
Наконец фирма Lattice Semiconductor в 1985 г. выпустила семейство GAL, которое можно считать своеобразной вершиной PAL-строения. Подобно исходным MMI PAL-ам c буковкой V ( Versatile) (например PAL16V8) чипы GAL (соответственно название будет GAL16V8) могут принимать прошивки ВСЕХ (ну почти) моделей PAL, а вдобавок чип GAL — электрически стираемый и многократно прошиваемый. Устройства GAL практически вытеснили все остальные SPLD, за исключением, пожалуй Atmel (нынче Microchip) серии ATF (аналогичный чип у них будет называться ATF16V8).

Для переноса JEDEC файлов (прошивок) старых PAL фирма Lattice Semiconductor выпустила утилиту PALTOGAL (тоже бесплатную и тоже под DOS).
ПРМЕЧАНИЕ: Фирма Lattice Semicronductor рекомендует использовать для разработки ABEL (пакет ispLEVER), а фирма Atmel – CUPL (WinCUPL или ProChip Designer). National Semiconductor предлагала свой Opal JR. Но мы в ретро-целях останемся верны PALASM.
ПРИМЕЧАНИЕ2: (для совсем нердов) У GAL все же есть некоторые мелкие отличия, связанные с тем, что MMI PAL – это ТТЛШ микросхема, а GAL – CMOS.
И конечно же, для прошивки микросхем GAL (и ATF) потребуется специальный программатор. Существуют и PAL-ы, прошиваемые по JTAG, но это редкость (Lattice ispGAL). Хотя программатор для GAL можно сделать самостоятельно (ищется по именам GALBLAST и ATFBLAST), всё же лучше приобрести готовый. Например, TL866 (известный еще как Minipro), которыми забит Aliexpress:

Сами чипы GAL или ATF можно приобрести на том же Aliexpress. Цена за десяток может доходить до 5$ и менее. Не стоит ожидать чудес, чипы будут б/у (помним, что их можно и нужно(!) стереть) и могут иметь следы пайки и маркировку краской или лазером от погибших неведомых устройств, откуда их вытащили трудолюбивые китайцы. Lattice GAL сняты с производства в 2011, но запасов из старой техники хватит еще на пару десятков лет. ATF еще выпускаются.
7-SEG LED
Если помните, в начале статьи мы собирались зажечь светодиод. А точнее — не один, а целых семь! Да- да, речь пойдет о 7-сегментном индикаторе, а точнее – о реализации банального дешифратора HEX-to-7SEG.

Почему-то так сложилось, что готовых микросхем с такой функцией не так уж и много. Есть десятичные BCD дешифраторы (т.е. без шестнадцатеричных символов ABCDEF), например 7446/7447/7448/7449 и 74246/74247/74248/74249). Полных HEX дешифраторов не так много — например Motorola MC14495 Hexadecimal-to-Seven Segment Driver или Fairchild DM9368.
Но цены на PAL (GAL) упали настолько, что сделать дешифратор на SPLD дешевле и быстрее! Вот и давайте для практики его и сделаем, включая шестнадцатеричные цифры ABCDEF (Нет, ЕГГОГ мы декодировать не будем ). Отличное приложение наших олдскульных знаний по матлогике и старым программируемым микросхемам.

Построение такого дешифратора является каноническим примером комбинационной логики и типовой лабораторной работой. В учебнике Харрис&Харрис «Цифровая схемотехника и архитектура компьютера» пункт 2.7.2 «Логическая минимизация на картах Карно» содержит пример 2.10 построения такого дешифратора, но только BCD.
На Википедии есть статья, в которой даже приведена нужная нам таблица перекодировки для полного HEX.
Вот эта же самая таблица, только здесь зажигание нужного светодиода отмечено красными клеточками. Как видите, никакой регулярности, только таблица, только хардкор!

Давайте для примера рассмотрим сегмент D (нижний). Как мы видим, он загорается 11 раз из 16 возможных входных комбинаций (вертикаль «d»). Если выписать ДНФ, то формула будет такой:

Но здесь есть проблема! Как мы писали выше, матрица обычных PAL (например в PAL16L8) имеет только 7 «ИЛИ» (сложений), а у нас — 11. Надо или применять более сложный чип или выражение придется оптимизировать.
ПРИМЕЧАНИЕ: В PALASM4 есть встроенный оптимизатор. Вероятно, он смог бы упростить это выражение, только надо эту оптимизацию включить. Но для сохранения ретро-духа пройдем этот этап вручную.
Давайте оптимизируем это выражение по карте Карно. Можно сделать это вручную и получить удовольствие, а можно воспользоваться сайтами, где на JavaScript реализованы эти алгоритмы, например:

Как видите, наше выражение для сегмента D превращается в короткое:

Тут всего 5 штук «ИЛИ» вместо 11 так что выражение влезает в ячейку PAL. Проделаем это для всех сегментов.
Откомпилируем файл .PDS в файл .JED с помощью PALASM:

Очень интересно, как PALASM разложил наши выражения на плавкие перемычки. Для этого можно заглянут в файл Fuse plot (рисунок перемычек).
Этот файл лучше рассматривать одновременно с документацией на PAL16L8. Ее можно найти, например, на сайте Texas Istruments: pal16r8am.pdf страница 5.
Сегмент D у нас выведен на 16-й вывод микросхемы. Если мы посмотрим схему PAL, то за него отвечают перемычки, начиная с номера 768. Как несложно догадаться 768 / 32 = 24 – это 24-я строка. Сама она отвечает за управление выходом и поэтому пустая. Логические выражения начинаются с перемычки 800, то есть строки 25. Если посмотреть на схему, то в 25-й строке собираются по «И»: прямой вход D0 (вывод микросхемы 2), инверсия D1 (вывод 3) и прямой вход D2 (пин 4). Это в точности соответствует первому минитерму в формуле для сегмента D! Остальные минитермы из выражения также транслируются в перемычки и в конце объединяются по «ИЛИ». Так что PALASM, не мудрствуя лукаво, просто переводит наши ДНФ-выражения в прошивку один в один.
Именно таким способом проектировали прошивки до появления PALASM, в самой старой документации MMI как раз описан этот способ. Надо отметить, что другие семейства, например PLA, не получили вообще или получили утилиты класса PALASM довольно поздно (например ICT PEEL Array PLACE) и не стали такими популярными.
Для программирования GAL полученный файл 7SEG.JED отконвертируем утилитой PALTOGAL:
При подключении индикатора к FPGA (на VHDL и Verilog) или к микроконтроллеру логические функции раскладывать нет необходимости и просто используют таблицу. Можно погуглить или посмотреть на Youtube, поиск «Семисегментный индикатор».
Практика
Давайте соберем модель декодера семисегментного индикатора (и сдадим курсовик, ха-ха). В качестве генератора импульсов применим обычную микросхемку NE555 (К1006ВИ1). Для наблюдения нам нужен период примерно 1 секунда. Для делителя на 16 в коде 1-2-4-8 можно применить что-нибудь типа К155/К555 ИЕ5 или ИЕ7 (совсем круто было бы сделать счетчик тоже на GAL, но это в следующий раз). В коробочке нашлась К555ИЕ7 (SN74LS193), значит так тому и быть. На вывод «R» подадим ноль, на выводы «V» и «-1» — единицу, на вывод «+1» — тактовые импульсы с NE555. Счетчик начал считать. Возьмем семисегментный индикатор с общим анодом и нашу GAL. Перед этим сотрем её и прошьем JEDEC файлом. Индикатор попался LTS-4801WC, OK. Выводы счетчика Q0,Q1,Q2,Q3 соединим со входами D0,D1,D2,D3 GAL, а выходы GAL – с катодами индикатора через 7 резисторов на 330 Ом.
Получается как-то так:
Заключение
Итак, мы окунулись в историю программируемых логических микросхем (PLD). Мы увидели, что за конструкцией PAL скрывается Древняя Могучая Теория. Выяснилось, что даже сейчас, вполне еще можно применять эти устройства в небольших самоделках. Мы рассмотрели вполне боевой «workflow», как это сделать. И да, PAL и GAL совместимы с олдовой теплой 5V TTL электроникой.
Конечно, в такой короткой статье невозможно отразить все аспекты. Вот кратко, про что мы не рассказали:
Не рассмотрели работу симулятора. В PALASM (2 и 4) встроен довольно мощный симулятор, практически язык программирования, с циклами, условными операторами и т.д.
Не рассмотрели построение на PALASM конечных автоматов. Как-нибудь в другой раз.
Не рассмотрели тонкости и ограничения оптимизации, но зато сделали оптимизацию вручную, по карте Карно. Это исключительно в ретро-целях! Сейчас так никто уже не делает (как и сами разработки на PAL).
Не ответили на вопрос: можно ли вводить в PALASM выражения не в ДНФ? Конечно можно. Если выражение синтаксически корректно, PALASM скорее всего его поймет. Но внутри все равно преобразует в ДНФ для воплощения в перемычках.
Не рассмотрели вопрос программирования (прошивки) исходных MMI PAL. Проблема здесь в том, что это однократно программируемые микросхемы и сейчас довольно сложно найти чистые PAL. И их не стереть. А программировались они специальным программатором (например, российский «Стерх» это умеет). Изначально у MMI был даже метод прошивать PAL как ПЗУ 512×4 на старых программаторах с помощью специальной «personality card» — у первых PAL было ровно 2048 перемычек, но ныне этот способ утрачен.
Алгоритм Гейла – Шепли — Gale–Shapley algorithm
В математике, экономике и информатике, то алгоритм Гейла-Шепли (также известный как отложенный алгоритм принятия или предложить, и режекторный алгоритм ) является алгоритм для нахождения решения проблемы стабильной согласования, названный в честь Дэвида Гейла и Ллойд Шепли который описал это как решение как проблемы поступления в колледж, так и проблемы стабильного брака . Это занимает полиномиальное время, и время линейно зависит от размера входных данных алгоритма. Это правдивый механизм с точки зрения предлагающих участников, для которых решение всегда будет оптимальным.
СОДЕРЖАНИЕ
Задний план
Задача стабильного сопоставления в своей самой простой форме принимает в качестве входных данных равное количество участников двух типов (например, n мужчин и n женщин или n студентов-медиков и n стажировок), а также порядок для каждого участника с указанием их предпочтений. кого сравнивать среди участников другого типа. Устойчивое сопоставление всегда существует, и алгоритмическая проблема, решаемая алгоритмом Гейла – Шепли, заключается в его поиске. Соответствующий является не стабильным, если:
- Существует элемент A первого согласованного набора, который предпочитает некоторый заданный элемент B второго согласованного набора элементу, с которым A уже согласован, и
- B также предпочитает A элементу, которому уже соответствует B.
Другими словами, соответствие стабильно, когда нет совпадения ( A, B ), когда оба участника предпочитают кого-то другого своему текущему партнеру.
Решение
В 1962 году Дэвид Гейл и Ллойд Шепли доказали, что для любого равного числа мужчин и женщин всегда возможно решить SMP и сделать все браки стабильными. Они представили алгоритм для этого. В 1984 году Элвин Э. Рот заметил, что, по сути, тот же алгоритм уже использовался на практике с начала 1950-х годов в Национальной программе подбора жильцов .
Алгоритм Гейла-Шепли включает в себя ряд «раундов» (или « итераций »):
- В первом раунде сначала а ) каждый незанятый мужчина делает предложение женщине, которую он предпочитает больше всего, а затем б ) каждая женщина отвечает «может быть» своему поклоннику, которого она предпочитает больше всего, и «нет» всем остальным женихам. Затем она временно «обручена» с женихом, которого она до сих пор предпочитает больше всего, и этот жених также временно обручен с ней.
- В каждом последующем раунде сначала а ) каждый незанятый мужчина делает предложение наиболее предпочтительной женщине, которой он еще не сделал предложение (независимо от того, была ли женщина уже помолвлена), а затем б ) каждая женщина отвечает «возможно», если она в настоящее время не помолвлена или если она предпочитает этого мужчину своему нынешнему временному партнеру (в этом случае она отвергает своего нынешнего временного партнера, который становится незанятым). Временный характер помолвки сохраняет право уже обрученной женщины «обменять» (и, в процессе, «бросить» своего бывшего партнера).
- Этот процесс повторяется до тех пор, пока все не будут задействованы.
Сложность выполнения этого алгоритма в том, где — количество мужчин или женщин. Поскольку списки предпочтений ввода также имеют размер, пропорциональный, время выполнения линейно зависит от размера ввода. О ( п 2 ) )> п п 2 >
Этот алгоритм гарантирует, что:
Все женятся В конце концов, не может быть ни мужчины, ни женщины одновременно незанятыми, поскольку он должен был сделать ей предложение в какой-то момент (поскольку мужчина в конечном итоге сделает предложение всем, если это необходимо), и, получив предложение, она обязательно будет помолвлена ( кому-то) после этого. Браки стабильны Пусть Алиса и Боб оба помолвлены, но не друг с другом. По завершении алгоритма Алиса и Боб не могут предпочесть друг друга своим текущим партнерам. Если Боб предпочитает Алису своему нынешнему партнеру, он, должно быть, сделал предложение Алисе до того, как сделал предложение своему нынешнему партнеру. Если Алиса приняла его предложение, но в конце концов не вышла за него замуж, она, должно быть, бросила его ради того, кто ей больше нравится, и, следовательно, не любит Боба больше, чем ее нынешний партнер. Если Алиса отклонила его предложение, она уже была с кем-то, кто ей нравился больше, чем Боб.
Алгоритм
Оптимальность решения
![]()
Существование различных стабильных сопоставлений поднимает вопрос: какое сопоставление возвращает алгоритм Гейла-Шепли? Подбор лучше для мужчин, для женщин или для среднего? В приведенном выше примере алгоритм сходится в одном раунде к оптимальному для мужчин решению, поскольку каждая женщина получает ровно одно предложение и, следовательно, выбирает это предложение, гарантируя, что у каждого мужчины есть принятое предложение, и завершение матча.
Это общий факт: алгоритм Гейла-Шепли, в котором мужчины делают предложения женщинам, всегда дает стабильное соответствие, которое является лучшим для всех мужчин среди всех стабильных сопоставлений. Точно так же, если женщины делают предложение, то полученное соответствие будет лучшим среди всех стабильных совпадений для всех женщин . Эти два сопоставления являются верхним и нижним элементами решетки устойчивых сопоставлений .
Чтобы убедиться в этом, рассмотрите иллюстрацию справа. Пусть A будет сопоставлением, генерируемым алгоритмом предложения мужчин, а B — альтернативным стабильным сопоставлением, которое лучше, по крайней мере, для одного человека, скажем, m 0 . Предположим, что m 0 совпадает в B с женщиной w 1, которую он предпочитает своему совпадению в A. Это означает, что в A m 0 посетил w 1, но она его отвергла (это обозначено зеленой стрелкой от m 0. к w 1 ). w 1 отвергла его в пользу какого-то мужчины, которого она предпочитает, скажем m 2 . Таким образом, в B, w 1 соответствует m 0, но «тоскует» (хочет, но не соответствует) для m 2 (это обозначено красной стрелкой от w 1 до m 2 ).
Поскольку B — стабильное соответствие, m 2 должен быть сопоставлен в B с какой-нибудь женщиной, которую он предпочитает w 1, скажем, w 3 . Это означает, что в A m 2 посетил w 3 до того, как достиг w 1, что означает, что w 3 отверг его. По аналогичным соображениям и поскольку граф конечен, мы должны в конечном итоге иметь направленный цикл, в котором каждый мужчина был отвергнут в A следующей женщиной в цикле, которая отвергла его в пользу следующего мужчины в цикле. Но это невозможно, поскольку такой «цикл отказов» не может начаться нигде: предположим от противного, что он начинается, например, с m 0 — первым мужчиной, отвергнутым соседней женщиной ( w 1 ). По предположению, это отклонение происходит только после того, как m 2 дойдет до w 1 . Но это может произойти только после того, как w 3 отвергнет m 2 — противоречие с тем, что m 0 является первым.
Стратегические соображения
Алгоритм GS — правдивый механизм с точки зрения мужчин (предлагающей стороны). То есть ни один мужчина не может добиться лучшего соответствия для себя, искажая свои предпочтения. Более того, алгоритм GS является доказательством даже групповой стратегии для мужчин, т. Е. Никакая коалиция мужчин не может координировать искажение своих предпочтений так, чтобы все мужчины в коалиции были строго в лучшем положении. Тем не менее, некоторая коалиция может искажать свои предпочтения так, что одни мужчины живут лучше, а другие мужчины сохраняют того же партнера.
Алгоритм GS не соответствует действительности для женщин (проверяющая сторона): каждая женщина может исказить свои предпочтения и получить лучшее соответствие.
Реализация в программных пакетах
- Р : Гейла-Шепли алгоритм (также называемый алгоритм отложенного приема) для стабильного брака и больниц / резидентов проблема доступна как часть matchingMarkets и matchingR пакетов.
- API : API MatchingTools предоставляет бесплатный интерфейс прикладного программирования для алгоритма Гейла – Шепли.
- Python : Алгоритм Гейла – Шепли включен в matching библиотеку вместе с несколькими другими хорошо известными игровыми алгоритмами сопоставления, а QuantEcon/MatchingMarkets.py пакет включает несколько других для обобщенных игр сопоставления.
- MATLAB : алгоритм Гейла-Шепли реализован в assign2DStable функции, которая является частью бесплатной библиотеки компонентов трекера Лаборатории военно-морских исследований США .
Признание
Шепли и Рот были удостоены Нобелевской премии по экономическим наукам 2012 года «за теорию стабильного распределения и практику рыночного дизайна »; Гейл умер в 2008 году.
PAL, GAL и путешествие в цифровое ретро
Идея сделать цифровые логические микросхемы с изменяемой структурой была всегда. Почему? Достаточно посмотреть на толстенный каталог чипов серии TTL 74xx (или советской К155), чтобы такая идея самозародилась. В СССР почти у каждого инженера и радиолюбителя был справочник В.Л. Шило «Популярные цифровые микросхемы», который вышел каким-то невероятным тиражом. Но всё равно, хотелось иметь некий «универсальный кристалл», из которого можно сделать все остальные микросхемы (ну хорошо, не все, но многие).
Конечно же, полупроводниковая промышленность тоже была не прочь удовлетворить такой спрос. Поэтому, начиная с конца 1960-х, на рынке каждый год появлялось огромное количество подобных устройств из класса PLD (Programmable Logical Device), самых разнообразных архитектур. Это было интереснейшее время! На рынке постоянно появлялось что-нибудь новенькое. Здесь были и различные ULA и БМК и EPROM-устройства на базе пережигаемых перемычек (82Sxxx) и PLA, у которых программировались оба слоя: «И» и «ИЛИ» (привет нашим К556РТ1 и К556РТ2) и т.д. Обзор этих ретро-технологий – тема для отдельной статьи. Мы же сделаем лишь обзор того, что «выстрелило» и стало мэйнстримом.
Сразу хочется попросить извинения у опытных электронщиков и разработчиков FPGA. Эта статья нисколько не имеет цели вторгнуться на их территорию, а только дает исторический обзор «как это было».
А в конце мы попробуем соединить теорию с какой-то осмысленной практикой, поглядеть, как это применяется в реальной жизни. Светодиод, например, зажечь или там даже семисегментный индикатор…
Так вот, в далекие 1970-е годы компания-производитель ПЗУ Monolithic Memories Inc. (MMI) выпустила на рынок очередное семейство программируемых чипов. Семейство ВНЕЗАПНО оказалось настолько удачным, что в 1978 году MMI зарегистрировала торговую марку PAL® (Programmable Array Logic) и стала лицензировать технологию таким гигантам, как Texas Instruments (серия TIBPAL), National Semiconductor, Philips (PLUS), AMD (AMPAL) и другим.

Даже в СССР не отставали и выпустили клоны, серию К1556.

В чем же секрет? Спроектированное инженерами и для инженеров семейство MMI PAL представляло собой практически чистое воплощение идеи ДНФ (Дизъюнктивная Нормальная Форма).
Здесь надо сделать логическое отступление и взглянуть, что же это такое, ДНФ и откуда оно взялось.
Матлогика
Дискретная математика и мат-логика вообще – наука большая и развесистая. Мы не будем залезать в дебри и высокую теорию, а лишь рассмотрим узкий срез — работу с логическими (булевыми или же переключательными) функциями и соответствующими комбинационными схемами.
Лирическое отступление: есть огромное искушение ничего не писать, а просто посоветовать взять и прочитать недавно переведенный учебник Харрис&Харрис «Цифровая схемотехника и архитектура компьютера», а конкретно главу 2 «Проектирование комбинационной логики». Это отличная книга! Там даже есть параграф про PAL (п.5.6 «Матрицы логических элементов»), но такое ощущение, что его безжалостно сократили в очередной редакции.
А для тех, кто захотел канонично, «от печки», разобраться в предмете поглубже (бывает!) можно порекомендовать книги 60-х годов по проектированию ЭВМ. Например, книгу “Синтез цифровых автоматов” В.М. Глушкова (тот самый, который ОГАС!) (М. Государственное издательство физико-математической литературы, 1962г). Книга настолько олдовая, что фамилия Карно записывается как Карнаут. Или можно предложить книгу ”Синтез схем электронных цифровых машин” (Е.Н.Вавилов, Г.П.Портной М. ”Советское радио” 1963).
В современных отечественных учебниках, чем дальше, тем больше этот раздел ужимается.
Например учебник Угрюмов Е.П. «Цифровая схемотехника» издания 2007 года еще содержал главу про PAL, а издания 2010 — уже нет. В настоящее время данная наука почти полностью перекочевала в пыльные бумажные методички кафедр по специальности 230101. Вдобавок, попытка дать студентам этот материал наталкивается на стойкое сопротивление: разговоры про «основы» воспринимаются учащимися как «too old» то есть как совершенно ненужный, устаревший хлам. Даже тут, на Хабре есть несколько статей на данную тему, и комментарии наполнены стонами ”Да-да! Нас тоже зачем-то насиловали этим весь первый курс!”.
Так вот, автор сбрасывает себя обязанность писать про пресловутые ”основы”. Предполагается, что читатель, который заглянул на огонек, всё-таки понимает, что такое булева алгебра, что такое И, ИЛИ, НЕ, знает теорему де Моргана и умеет читать схемы на логических элементах.
ПРИМЕЧАНИЕ: Мне тут подсказывают, что в современном курсе цифровой электроники эта дисциплина (Дискретная математика) и Цифровая схемотехника чаще всего разделены на два предмета и учебники у них — разные. А Харрис&Харрис в попытке впихнуть все в одну книгу породил монстра на 1600 страниц. Ну OK.
Ах да, ДНФ. В старых книжках говорится (объясняется — почему), что при достаточно сложном логическом выражении его лучше всего представить (и это можно сделать для любого выражения!) в виде дизъюнктивной нормальной формы (sum of product, SOP). Несмотря на страшное название, это очень просто. Возьмем логическую функцию Y от трех переменных, A, B, C. Пусть она принимает значение «истина» тогда и только тогда, когда все три входные переменные равны нулю или же все они равны единице. В ДНФ это запишется крайне просто:

Это так называемая алгебраическая форма. Операция «ИЛИ» тут записывается как «+», а операция «И» — как умножение и, как в обычной алгебре, опускается. Так получилось, что существует множество форматов записи (синтаксисов) булевых выражений. Вот в другой записи:

Си-шное выражение для bool переменных:

Или даже так (синтаксис PALASM):

То есть ДНФ (в алгебраической форме) выглядит как цепочка сложений т.е. многочлен (логическое ИЛИ) из произведений (логическое И) входных переменных (sum of product), причем только тех комбинаций, для которых должна получаться «истина». Интуитивно это довольно понятно: Истина, когда это И это, ИЛИ же когда то И то. Как выше упоминалось, в форме ДНФ можно представить любое логическое выражение (и помним, что мы не углубляемся в СДНФ, КНФ, СКНФ, критерий Поста и т.д.).
Оптимизация, оптимизация
Другая, ныне забытая дисциплина при изучении данной науки – это методы оптимизации логических выражений. Современному разработчику практически не надо заботиться об оптимизации, за него все сделает «умный» компилятор. Да, напрямую к PAL оптимизация выражений отношения не имеет, но чтобы понять дух эпохи, давайте посмотрим.
На самом деле, методов оптимизации существует довольно много. Самый простой — алгебраический, когда преобразуется выражение по законам булевой алгебры (она слегка похожа на обычную, но чуть другая). Можно еще упомянуть теорему Квайна (и метод Квайна – Мак-Класки), метод получения тупиковых форм, метод испытания членов, метод импликантных матриц и т.д. Отдельно где-то парит полином Жегалкина на базисе Исключающее-ИЛИ. Методов много. Самыми удобными оказались диаграммы Вейча или, в усовершенствованном виде — карты Карно.
Для изучения механизма работы карты Карно можно, опять же, отправить к учебнику Харрис&Харрис глава 2.7. Но очень уж изящное решение! Кроме того, карты Карно иногда спрашивают на собеседованиях. Карты Карно предназначены для визуального безкомпьютерного упрощения выражений с количеством переменных до 6.
Давайте посмотрим на типичную карту Карно, например на 4 переменных:

Самое важное (и в чем состоит суть изобретения Мориса Карно) – это то, что соседние клеточки по вертикали и горизонтали отличаются значением ровно одной переменной. А если в соседних ячейках стоят «1» то эту переменную можно исключить. Причем «края» карты Карно подразумеваются «склеенными». Так что наша функция ужимается до

Если попытаться изобразить в 3D карту Карно для 4-х переменных, ее можно будет представить как развертку такого «угловатого тора», имеющего 16 граней (нарисовано в OpenSCAD ).

Возвращаясь к PAL
Обогатившись такими знаниями, давайте вернемся к нашим PAL-кам и посмотрим на их внутреннее устройство. И опять же, хорошим подспорьем тут будет учебник Харрис&Харрис «Цифровая схемотехника и архитектура компьютера», а конкретно параграф про PAL (п.5.6 «Матрицы логических элементов»).
При разработке PAL применяется своеобразная графическая запись, первоначально, видимо, предназначенная для ручного кодирования (до появления PALASM).
Давайте возьмем одну ячейку PAL, самого классического PAL16L8:

Итак, сверху вниз идут колонки – входные переменные. Из них: 10 шт. – это самые настоящие входы, то есть «ножки» микросхемы, а 6 шт. – это «возвраты» внутри чипа, что позволяет создавать более сложные многоступенчатые выражения. Понятно, что каждая из этих 16 переменных существует в прямой и инверсной форме, итого мы видим 16*2=32 колонки. Слева мы видим ввод одной переменной в матрицу, в прямом и инверсном виде (вывод 2).
Все эти «вертикальные» переменные одновременно поступают на элементы «И», которые могут использовать некоторые их них (а могут не использовать). Схема примерно такая (тут нарисованы две входные переменные и два элемента «И»):

Мы видим «плавкие перемычки» (fuse, F1..F4 и F5..F8), которые задают, какие переменные подключены к «И». Именно эти fuse и программируются и задают логическую функцию PAL. Картинка получается довольно громоздкая, поэтому применяют такую сокращенную графическую запись (крестики – это подключенные входы):

Вернемся к схеме ячейки PAL:

Как видите, в каждой строке (горизонтали) можно собрать функцию «И» из 16 (32, учитывая инверсию) возможных входов (переменных). То есть такая вот строка – это на самом деле 32-входовый элемент «И» (программируемый). Чуть позже мы посмотрим, как эти соединения выглядят в прошивке.
Далее по схеме мы видим, что в PAL16L8 имеется 7 штук таких «И-шек», объединенных по «ИЛИ». Структура у «ИЛИ» у PAL фиксированная (в отличии от PLA и других архитектур) и не программируется. Кстати, обратите внимание, можно использовать меньшее количество «ИЛИ» (просто не задавая функций у «И» в ячейке), а вот больше – нельзя!
Как несложно заметить, такая конструкция и является физической реализацией ДНФ или SOP (Sum Of Product – то есть сумма произведений). Бинго!
Такие устройства стали называться SPLD (Simple PLD) в противовес CPLD (Complex PLD) и FPGA. Про CPLD кстати, имеется отдельная статья.
Такая простая и элегантная конструкция быстро стала чрезвычайно популярной и стала быстро вытеснять остальные семейства. Вот почему такие гранды, как AMD, Philips, National Semiconductor лицензировали ее.
Популярность PAL-ок пришлась на середину 80-х и начало 90-х. Многие производители чипов, прямо в Datasheet-ах публиковали листинги на PALASM для подключения своих микросхем к другим чипам и к разнообразным микропроцессорным шинам. Некоторые платы начала 90-х представляли собой «россыпи» PAL-ок, на которых были реализованы сложнейшие схемы. Это позволяло быстро выйти на рынок, до начала производства заказных микросхем LSI. (Погуглите, ну скажем, картинки материнской платы EISA i486 Everex Step Mega Cube или Intel iSBC 386. Все узкие микросхемы с бумажками – это PAL ).
Сейчас эту нишу занимают CPLD и FPGA.
Компания MMI выпускала книжки, содержащие массу примеров применения своих микросхем, которые сопровождались забавными рисунками (извините, утащил).

Или даже так, ужас-ужас (Текст: В этой конструкции одна PAL16R8 заменяет 15 TTL микросхем малой и средней степени интеграции ):

Семейство PAL было довольно обширное. Существовали разновидности на разное количество ячеек и входов. Были разновидности с триггерами, что позволяло делать на них синхронные схемы и даже маленькие конечные автоматы (например PAL16R8). Существовали универсальные (Versatile) разновидности, в которых можно выбирать комбинаторную логику или триггера (PAL16V8). Существовали чуть более крупные PAL-ки в 24-выводном корпусе, типа PAL22V10. Микросхемы могли быть упакованы в различные корпуса и могли быть разной «скорости», от -5 до -25 наносекунд. Наконец, существовали низкопотребляющие варианты и варианты в CMOS исполнении (например Texas Instrument TICPAL или Cypress Semiconductor PALC).

PALASM
Невероятный успех микросхемам PAL фирмы MMI принёс еще один компонент, без которого покорение рынка было бы немыслимо. Это — утилита PALASM. С ее помощью создание прошивки для PAL стало делом настолько легким и простым, что любой инженер с нормальной подготовкой, понимал идею практически сразу. В PALASM вводится названия пинов и логические выражения в человеческой алгебраической форме (которые обычно выглядят как ДНФ), после чего PALASM выдает файл прошивки для программатора (JEDEC). Грубо говоря, компания MMI сделала тот шаг, который когда-то в 1950-е прошли обычные компьютеры, при переходе от ручного выписывания двоичных кодов к более понятной записи выражений машинного языка (ассемблера). А сам PALASM первых версий, в свою очередь, был написан на языке FORTRAN IV и распространялся в исходных текстах, что позволяло запускать его на любой тогдашней машине, где был компилятор, вплоть до ранних персоналок под CP/M и DOS. Да, да, когда-то FORTRAN был общим системным языком для переноса программ…
Позже вышел PALASM2, синтаксис немного изменился, оброс разнообразными возможностями, появилось некоторое подобие макросов, оптимизатор, поддержка конечных автоматов и даже симулятор. Компания MMI тоже претерпела изменения, ее активы были поглощены AMD, потом выделены в отдельную компанию Vantis, которую позже купила Lattice Semiconductor. Сам входной язык PALASM послужил прообразом множества подобных и более продвинутых языков, его следы есть в ABEL, CUPL и в VHDL (а вообще-то он сам вырос из FORTRAN-а ).
Наиболее развитый PALASM – это версия PALASM4 v1.5a от AMD 1992 года. Понятно, что такая ретро-программа требует для запуска ретро-DOS. Но к счастью, этот вопрос давно решен. Тут нам поможет прекрасная утилита DOSBOX, позволяющая запускать DOS-программы даже на современном Windows 10 64-бит. Хотя DOSBOX вообще-то, предназначен для запуска ретро-игр, но и не-игровые DOS-утилиты неплохо в нем живут и PALASM — не исключение. Компания AMD сделала широкий жест и отпустила PALASM в Public Domain, так что пользоваться им можно совершенно легально.
Тут можно найти инструкцию, как поставить PALASM на DOSBOX и также скачать саму программу. Конфигурационный файл DOSBOX хранится в профиле пользователя
C:\Users\%USERNAME\AppData\Local\DOSBox\ dosbox-0.74.conf
Лучше дополнить секцию [autoexec]:
Из под Linux тоже можно запустить PALASM например с помощью того же DOSBOX или похожего DOSEMU.
Из PAL в GAL
При всём своём удобстве PAL-ы имели и некоторые проблемы. Одна из таких проблем состоит в том, что PAL – это однократно программируемое устройство (OTP) с плавкими титано-вольфрамовыми перемычками (Ti-W fuse). При появлении исправлений и замене прошивки приходилось старую микросхему просто выкидывать. Так что многие производители стали предлагать ”стираемые” PAL-ки. История тут длинная, можно, например, вспомнить УФ-стираемые чипы с «окошечком», или тот факт, что очень хотелось сохранить совместимость с парком программаторов и алгоритмами прошивки оригинальных PAL (серии PALCE и PEEL от International CMOS Technology (ICT) Corporation) и т.д.
Наконец фирма Lattice Semiconductor в 1985 г. выпустила семейство GAL, которое можно считать своеобразной вершиной PAL-строения. Подобно исходным MMI PAL-ам c буковкой V ( Versatile) (например PAL16V8) чипы GAL (соответственно название будет GAL16V8) могут принимать прошивки ВСЕХ (ну почти) моделей PAL, а вдобавок чип GAL — электрически стираемый и многократно прошиваемый. Устройства GAL практически вытеснили все остальные SPLD, за исключением, пожалуй Atmel (нынче Microchip) серии ATF (аналогичный чип у них будет называться ATF16V8).

Для переноса JEDEC файлов (прошивок) старых PAL фирма Lattice Semiconductor выпустила утилиту PALTOGAL (тоже бесплатную и тоже под DOS).
ПРМЕЧАНИЕ: Фирма Lattice Semicronductor рекомендует использовать для разработки ABEL (пакет ispLEVER), а фирма Atmel – CUPL (WinCUPL или ProChip Designer). National Semiconductor предлагала свой Opal JR. Но мы в ретро-целях останемся верны PALASM.
ПРИМЕЧАНИЕ2: (для совсем нердов) У GAL все же есть некоторые мелкие отличия, связанные с тем, что MMI PAL – это ТТЛШ микросхема, а GAL – CMOS.
И конечно же, для прошивки микросхем GAL (и ATF) потребуется специальный программатор. Существуют и PAL-ы, прошиваемые по JTAG, но это редкость (Lattice ispGAL). Хотя программатор для GAL можно сделать самостоятельно (ищется по именам GALBLAST и ATFBLAST), всё же лучше приобрести готовый. Например, TL866 (известный еще как Minipro), которыми забит Aliexpress:

Сами чипы GAL или ATF можно приобрести на том же Aliexpress. Цена за десяток может доходить до 5$ и менее. Не стоит ожидать чудес, чипы будут б/у (помним, что их можно и нужно(!) стереть) и могут иметь следы пайки и маркировку краской или лазером от погибших неведомых устройств, откуда их вытащили трудолюбивые китайцы. Lattice GAL сняты с производства в 2011, но запасов из старой техники хватит еще на пару десятков лет. ATF еще выпускаются.
7-SEG LED
Если помните, в начале статьи мы собирались зажечь светодиод. А точнее — не один, а целых семь! Да- да, речь пойдет о 7-сегментном индикаторе, а точнее – о реализации банального дешифратора HEX-to-7SEG.

Почему-то так сложилось, что готовых микросхем с такой функцией не так уж и много. Есть десятичные BCD дешифраторы (т.е. без шестнадцатеричных символов ABCDEF), например 7446/7447/7448/7449 и 74246/74247/74248/74249). Полных HEX дешифраторов не так много — например Motorola MC14495 Hexadecimal-to-Seven Segment Driver или Fairchild DM9368.
Но цены на PAL (GAL) упали настолько, что сделать дешифратор на SPLD дешевле и быстрее! Вот и давайте для практики его и сделаем, включая шестнадцатеричные цифры ABCDEF (Нет, ЕГГОГ мы декодировать не будем ). Отличное приложение наших олдскульных знаний по матлогике и старым программируемым микросхемам.

Построение такого дешифратора является каноническим примером комбинационной логики и типовой лабораторной работой. В учебнике Харрис&Харрис «Цифровая схемотехника и архитектура компьютера» пункт 2.7.2 «Логическая минимизация на картах Карно» содержит пример 2.10 построения такого дешифратора, но только BCD.
На Википедии есть статья, в которой даже приведена нужная нам таблица перекодировки для полного HEX.
Вот эта же самая таблица, только здесь зажигание нужного светодиода отмечено красными клеточками. Как видите, никакой регулярности, только таблица, только хардкор!

Давайте для примера рассмотрим сегмент D (нижний). Как мы видим, он загорается 11 раз из 16 возможных входных комбинаций (вертикаль «d»). Если выписать ДНФ, то формула будет такой:

Но здесь есть проблема! Как мы писали выше, матрица обычных PAL (например в PAL16L8) имеет только 7 «ИЛИ» (сложений), а у нас — 11. Надо или применять более сложный чип или выражение придется оптимизировать.
ПРИМЕЧАНИЕ: В PALASM4 есть встроенный оптимизатор. Вероятно, он смог бы упростить это выражение, только надо эту оптимизацию включить. Но для сохранения ретро-духа пройдем этот этап вручную.
Давайте оптимизируем это выражение по карте Карно. Можно сделать это вручную и получить удовольствие, а можно воспользоваться сайтами, где на JavaScript реализованы эти алгоритмы, например:

Как видите, наше выражение для сегмента D превращается в короткое:
Тут всего 5 штук «ИЛИ» вместо 11 так что выражение влезает в ячейку PAL. Проделаем это для всех сегментов.
Откомпилируем файл .PDS в файл .JED с помощью PALASM:

Очень интересно, как PALASM разложил наши выражения на плавкие перемычки. Для этого можно заглянут в файл Fuse plot (рисунок перемычек).
Этот файл лучше рассматривать одновременно с документацией на PAL16L8. Ее можно найти, например, на сайте Texas Istruments: pal16r8am.pdf страница 5.
Сегмент D у нас выведен на 16-й вывод микросхемы. Если мы посмотрим схему PAL, то за него отвечают перемычки, начиная с номера 768. Как несложно догадаться 768 / 32 = 24 – это 24-я строка. Сама она отвечает за управление выходом и поэтому пустая. Логические выражения начинаются с перемычки 800, то есть строки 25. Если посмотреть на схему, то в 25-й строке собираются по «И»: прямой вход D0 (вывод микросхемы 2), инверсия D1 (вывод 3) и прямой вход D2 (пин 4). Это в точности соответствует первому минитерму в формуле для сегмента D! Остальные минитермы из выражения также транслируются в перемычки и в конце объединяются по «ИЛИ». Так что PALASM, не мудрствуя лукаво, просто переводит наши ДНФ-выражения в прошивку один в один.
Именно таким способом проектировали прошивки до появления PALASM, в самой старой документации MMI как раз описан этот способ. Надо отметить, что другие семейства, например PLA, не получили вообще или получили утилиты класса PALASM довольно поздно (например ICT PEEL Array PLACE) и не стали такими популярными.
Для программирования GAL полученный файл 7SEG.JED отконвертируем утилитой PALTOGAL:
При подключении индикатора к FPGA (на VHDL и Verilog) или к микроконтроллеру логические функции раскладывать нет необходимости и просто используют таблицу. Можно погуглить или посмотреть на Youtube, поиск «Семисегментный индикатор».
Практика
Давайте соберем модель декодера семисегментного индикатора (и сдадим курсовик, ха-ха). В качестве генератора импульсов применим обычную микросхемку NE555 (К1006ВИ1). Для наблюдения нам нужен период примерно 1 секунда. Для делителя на 16 в коде 1-2-4-8 можно применить что-нибудь типа К155/К555 ИЕ5 или ИЕ7 (совсем круто было бы сделать счетчик тоже на GAL, но это в следующий раз). В коробочке нашлась К555ИЕ7 (SN74LS193), значит так тому и быть. На вывод «R» подадим ноль, на выводы «V» и «-1» — единицу, на вывод «+1» — тактовые импульсы с NE555. Счетчик начал считать. Возьмем семисегментный индикатор с общим анодом и нашу GAL. Перед этим сотрем её и прошьем JEDEC файлом. Индикатор попался LTS-4801WC, OK. Выводы счетчика Q0,Q1,Q2,Q3 соединим со входами D0,D1,D2,D3 GAL, а выходы GAL – с катодами индикатора через 7 резисторов на 330 Ом.
Получается как-то так:
Заключение
Итак, мы окунулись в историю программируемых логических микросхем (PLD). Мы увидели, что за конструкцией PAL скрывается Древняя Могучая Теория. Выяснилось, что даже сейчас, вполне еще можно применять эти устройства в небольших самоделках. Мы рассмотрели вполне боевой «workflow», как это сделать. И да, PAL и GAL совместимы с олдовой теплой 5V TTL электроникой.
Конечно, в такой короткой статье невозможно отразить все аспекты. Вот кратко, про что мы не рассказали:
Не рассмотрели работу симулятора. В PALASM (2 и 4) встроен довольно мощный симулятор, практически язык программирования, с циклами, условными операторами и т.д.
Не рассмотрели построение на PALASM конечных автоматов. Как-нибудь в другой раз.
Не рассмотрели тонкости и ограничения оптимизации, но зато сделали оптимизацию вручную, по карте Карно. Это исключительно в ретро-целях! Сейчас так никто уже не делает (как и сами разработки на PAL).
Не ответили на вопрос: можно ли вводить в PALASM выражения не в ДНФ? Конечно можно. Если выражение синтаксически корректно, PALASM скорее всего его поймет. Но внутри все равно преобразует в ДНФ для воплощения в перемычках.
Не рассмотрели вопрос программирования (прошивки) исходных MMI PAL. Проблема здесь в том, что это однократно программируемые микросхемы и сейчас довольно сложно найти чистые PAL. И их не стереть. А программировались они специальным программатором (например, российский «Стерх» это умеет). Изначально у MMI был даже метод прошивать PAL как ПЗУ 512×4 на старых программаторах с помощью специальной «personality card» — у первых PAL было ровно 2048 перемычек, но ныне этот способ утрачен.
Gale–Shapley algorithm simply explained
![]()
From this article, you will learn about stable pairing or stable marriage problem. You will learn how to solve that problem using Game Theory and the Gale-Shapley algorithm in particular. We will use Python to create our own solution using theorem from the original paper from 1962.
What is a stable marriage or pairing problem?
In the real world, there are cases when we facing paring problem: student choosing their future universities, man and women seeking each other to create families, internet services that need to be connected with users with the smallest amount of time. In all these cases we need to create stable pairs that need to satisfied certain criteria. We can imagine a stable pair for (A, a) as a pair where no A or a have any better options.
Best way to understand it is to solve practical examples, I can recommend book Insights into Game Theory [1], it contains plenty of exercises that you can solve on paper. But here I wanna use Python to solve that 🙂
Problem definition:
In our example, we will have two groups, women and man. Women’s names will start with a capital letter: A, B, C, D and men with lowercase latter: a, b, c, d. We need to create stable pairs. Before doing that we made a survey to gather some information as our starting point. Each of them was asked to rank people of the opposite sex by their personal sympathy. Where 1 place person that they like the most and 4 people they like the least.
For example, women A answered this way: d, c, a, b
In python, we can create two data frames man and women:
In data frames, a rank was replaced by number for convenience. For example, if we wanna know the preferences of the women A, we can read column A in the women data frame: 3, 4, 2, 1 for men a, b, c, d respectively. If we wanna know the preferences of the men a we can read a row in the man data frame: 1, 2, 3, 4 for women A, B, C, D respectively.
Thus pair of man and women can be represented as a pair of numbers, for example, pair A and a will create a pair with numbers (3,1). For the women A man a is third in her list, but for the men a, women A is number one in his list.
So in this case men a is fully happy, but women A can try to create a pair with someone higher from her list, for example, man c, and if for c will be better to create a pair with A than with his current partner, both pair will collapse and create new pairs.
That is an example of an unstable pair, a pair in which one or both participants can improve the situation but creating more preferable pairs for them.
So the task is to find stable pairs for all participants. And turns out that there is a way to achieve equilibrium!
The Gale-Shapley algorithm in Python
David Gale and Lloyd Shapley proved that in cases with when two sets are equal there always a way to create stable pairs. I recommend reading the original paper[2] to be familiar with the elegant prove they provided.
There are different implementations of the Gale-Shapley algorithm in Python [3, 4, 5], let’s create this algorithm closer to pseudocode solution without going into complicated OOP.
In a pseudocode solution looks like this [6]:
In Python I was able to create this solution:
Summary:
Game Theory is very fun because it operates with situations from the real world. And it’s also most of the time do not require complicated math apparatus, especially in cooperative games.
There are many things about the Gale-Shapley algorithm that we didn’t touch: general case when the number of men is not equal to the number of women and how many maximum iterations this algorithm may take.
After looking at open-source solutions I was sure that I will be able to create more minimalistic and even more Pythonic solution. But I ended up with a pretty messy while cycle. ♂️
Алгоритм Гейла – Шепли — Gale–Shapley algorithm
В математике , экономике и информатике , то алгоритм Гейла-Шепли (также известный как отложенный алгоритм принятия или предложить, и режекторный алгоритм ) является алгоритм для нахождения решения проблемы стабильной согласования , названный в честь Дэвида Гейла и Ллойд Шепли который описал это как решение как проблемы поступления в колледж, так и проблемы стабильного брака . Это занимает полиномиальное время , и время линейно зависит от размера входных данных алгоритма. Это правдивый механизм с точки зрения предлагающих участников, для которых решение всегда будет оптимальным.
СОДЕРЖАНИЕ
Задний план
Задача стабильного сопоставления в своей самой простой форме принимает в качестве входных данных равное количество участников двух типов (например, n мужчин и n женщин или n студентов-медиков и n стажировок), а также порядок для каждого участника с указанием их предпочтений. кого сравнивать среди участников другого типа. Устойчивое сопоставление всегда существует, и алгоритмическая проблема, решаемая алгоритмом Гейла – Шепли, заключается в его поиске. Соответствующий является не стабильным , если:
- Существует элемент A первого согласованного набора, который предпочитает некоторый заданный элемент B второго согласованного набора элементу, с которым A уже согласован, и
- B также предпочитает A элементу, которому уже соответствует B.
Другими словами, соответствие стабильно, когда нет совпадения ( A , B ), когда оба участника предпочитают кого-то другого своему текущему партнеру.
Решение
В 1962 году Дэвид Гейл и Ллойд Шепли доказали, что для любого равного числа мужчин и женщин всегда возможно решить SMP и сделать все браки стабильными. Они представили алгоритм для этого. В 1984 году Элвин Э. Рот заметил, что, по сути, тот же алгоритм уже использовался на практике с начала 1950-х годов в Национальной программе подбора жильцов .
Алгоритм Гейла-Шепли включает в себя ряд «раундов» (или « итераций »):
- В первом раунде сначала а ) каждый незанятый мужчина делает предложение женщине, которую он предпочитает больше всего, а затем б ) каждая женщина отвечает «может быть» своему поклоннику, которого она предпочитает больше всего, и «нет» всем остальным женихам. Затем она временно «обручена» с женихом, которого она до сих пор предпочитает больше всего, и этот жених также временно обручен с ней.
- В каждом последующем раунде сначала а ) каждый незанятый мужчина делает предложение наиболее предпочтительной женщине, которой он еще не сделал предложение (независимо от того, была ли женщина уже помолвлена), а затем б ) каждая женщина отвечает «возможно», если она в настоящее время не помолвлена или если она предпочитает этого мужчину своему нынешнему временному партнеру (в этом случае она отвергает своего нынешнего временного партнера, который становится незанятым). Временный характер помолвки сохраняет право уже обрученной женщины «обменять» (и, в процессе, «бросить» своего бывшего партнера).
- Этот процесс повторяется до тех пор, пока все не будут задействованы.
Сложность выполнения этого алгоритма в том, где — количество мужчин или женщин. Поскольку списки предпочтений ввода также имеют размер, пропорциональный , время выполнения линейно зависит от размера ввода. О ( п 2 ) <\ Displaystyle О (п ^ <2>)> п <\ displaystyle n>п 2 <\ Displaystyle п ^ <2>>
Этот алгоритм гарантирует, что:
Все женятся В конце концов, не может быть ни мужчины, ни женщины одновременно незанятыми, поскольку он должен был сделать ей предложение в какой-то момент (поскольку мужчина в конечном итоге сделает предложение всем, если это необходимо), и, получив предложение, она обязательно будет помолвлена ( кому-то) после этого. Браки стабильны Пусть Алиса и Боб оба помолвлены, но не друг с другом. По завершении алгоритма Алиса и Боб не могут предпочесть друг друга своим текущим партнерам. Если Боб предпочитает Алису своему нынешнему партнеру, он, должно быть, сделал предложение Алисе до того, как сделал предложение своему нынешнему партнеру. Если Алиса приняла его предложение, но в конце концов не вышла за него замуж, она, должно быть, бросила его ради того, кто ей больше нравится, и, следовательно, не любит Боба больше, чем ее нынешний партнер. Если Алиса отклонила его предложение, она уже была с кем-то, кто ей нравился больше, чем Боб.
Алгоритм
Оптимальность решения
![]()
Существование различных стабильных сопоставлений поднимает вопрос: какое сопоставление возвращает алгоритм Гейла-Шепли? Подбор лучше для мужчин, для женщин или для среднего? В приведенном выше примере алгоритм сходится в одном раунде к оптимальному для мужчин решению, поскольку каждая женщина получает ровно одно предложение и, следовательно, выбирает это предложение, гарантируя, что у каждого мужчины есть принятое предложение, и завершение матча.
Это общий факт: алгоритм Гейла-Шепли, в котором мужчины делают предложения женщинам, всегда дает стабильное соответствие, которое является лучшим для всех мужчин среди всех стабильных сопоставлений. Точно так же, если женщины делают предложение, то полученное соответствие будет лучшим среди всех стабильных совпадений для всех женщин . Эти два сопоставления являются верхним и нижним элементами решетки устойчивых сопоставлений .
Чтобы убедиться в этом, рассмотрите иллюстрацию справа. Пусть A будет сопоставлением, генерируемым алгоритмом предложения мужчин, а B — альтернативным стабильным сопоставлением, которое лучше, по крайней мере, для одного человека, скажем, m 0 . Предположим, что m 0 совпадает в B с женщиной w 1 , которую он предпочитает своему совпадению в A. Это означает, что в A m 0 посетил w 1 , но она его отвергла (это обозначено зеленой стрелкой от m 0. к w 1 ). w 1 отвергла его в пользу какого-то мужчины, которого она предпочитает, скажем m 2 . Таким образом, в B, w 1 соответствует m 0, но «тоскует» (хочет, но не соответствует) для m 2 (это обозначено красной стрелкой от w 1 до m 2 ).
Поскольку B — стабильное соответствие, m 2 должен быть сопоставлен в B с какой-нибудь женщиной, которую он предпочитает w 1 , скажем, w 3 . Это означает, что в A m 2 посетил w 3 до того, как достиг w 1 , что означает, что w 3 отверг его. По аналогичным соображениям и поскольку граф конечен, мы должны в конечном итоге иметь направленный цикл, в котором каждый мужчина был отвергнут в A следующей женщиной в цикле, которая отвергла его в пользу следующего мужчины в цикле. Но это невозможно, поскольку такой «цикл отказов» не может начаться нигде: предположим от противного, что он начинается, например, с m 0 — первым мужчиной, отвергнутым соседней женщиной ( w 1 ). По предположению, это отклонение происходит только после того, как m 2 дойдет до w 1 . Но это может произойти только после того, как w 3 отвергнет m 2 — противоречие с тем, что m 0 является первым.
Стратегические соображения
Алгоритм GS — правдивый механизм с точки зрения мужчин (предлагающей стороны). То есть ни один мужчина не может добиться лучшего соответствия для себя, искажая свои предпочтения. Более того, алгоритм GS является доказательством даже групповой стратегии для мужчин, т. Е. Никакая коалиция мужчин не может координировать искажение своих предпочтений так, чтобы все мужчины в коалиции были строго в лучшем положении. Тем не менее, некоторая коалиция может искажать свои предпочтения так, что одни мужчины живут лучше, а другие мужчины сохраняют того же партнера.
Алгоритм GS не соответствует действительности для женщин (проверяющая сторона): каждая женщина может исказить свои предпочтения и получить лучшее соответствие.
Реализация в программных пакетах
- Р : Гейла-Шепли алгоритм (также называемый алгоритм отложенного приема) для стабильного брака и больниц / резидентов проблема доступна как часть matchingMarkets и matchingR пакетов.
- API : API MatchingTools предоставляет бесплатный интерфейс прикладного программирования для алгоритма Гейла – Шепли.
- Python : Алгоритм Гейла – Шепли включен в matching библиотеку вместе с несколькими другими хорошо известными игровыми алгоритмами сопоставления , а QuantEcon/MatchingMarkets.py пакет включает несколько других для обобщенных игр сопоставления.
- MATLAB : алгоритм Гейла-Шепли реализован в assign2DStable функции, которая является частью бесплатной библиотеки компонентов трекера Лаборатории военно-морских исследований США .
Признание
Шепли и Рот были удостоены Нобелевской премии по экономическим наукам 2012 года «за теорию стабильного распределения и практику рыночного дизайна »; Гейл умер в 2008 году.