 |
Тема 5.7 Базовые манипуляции с текстами: перекодировка, вставка, удаление, замена.
|
|
|
|
Тема 5. 7 Базовые манипуляции с текстами: перекодировка, вставка, удаление, замена.
При работе с текстом часто приходится выделять и преобразовывать части строк. Часть текста (подстроку) можно скопировать или вырезать, а затем вставить в другое место в тексте. Строка или ее часть может быть заменена на другую строку. Команды для выполнения операций по работе с фрагментом текста представлены в таблице.
| Команда | Описание |
| substr(n, k) | Копирует часть строки в другую строку |
| erase(n, k) | Удаляет символы строки |
| insert(n, s1) | Вставляет подстроку s1 в строку |
| replace(n, k, s1) | Заменяет символы строкой s1 |
| Empty() | Возвращает true, если строка пуста, false — если не пуста |
| Push_back(c) | Добавляет в конец строки символ с |
| Pop_back() | Удаляет один символ в конце строки |
Во всех командах переменная n обозначает позицию (номер) символа, начиная с которого выполняют операцию, а переменная k — количество символов. Разберем команды подробнее (пример 9. 9).
В результате выполнения команды substr строка s не изменяется. Результат работы функции присваивается другой строке.
Команды erase, insert и replace изменяют исходную строку s.
В примере 9. 10 показано, как применяются указанные команды.
Функции insert и replace имеют еще один вариант реализации. Этот вариант позволяет использовать при вставке не всю строку s1, а только ее часть. В этом случае задаются два дополнительных параметра: позиция n1 и количество символов k1, относящихся к строке s1. Параметры позволяют выделить подстроку в строке s1, которая и вставляется в исходную строку:
insert(n, s1, n1, k1),
replace(n, k, s1, n1, k1).
Пример 9. 11. Написать программу, которая определит, сколько раз встречается заданная подстрока в строке.
|
|
|
Этапы выполнения задания
I. Исходные данные: переменная s — исходная строка, p — исходная подстрока.
II. Результат: k — искомое количество.
III. Алгоритм решения задачи.
1. Вводим исходные данные.
2. Инициализируем значение счетчика k = 0.
3. Определяем длины n1 и n2 для строки s и подстроки p.
4. В цикле for от 1до разницы в длинах строки sи подстроки p.
4. 1. Выделим из строки s подстроку t такой же длины, что и длина p, начиная с текущего символа.
4. 2. Сравним подстроки. Если они равны, то увеличиваем значение счетчика на 1.
5. Вывод результата.
IV. Описание переменных: s, p, t — string, n1, n2, k — int.
Тема 5. 8 Логическая обработка данных
SPSS (Statistical Package for the Social Sciences) – наиболее широко используемая при анализе данных социологических исследований стандартная компьютерная программа; здесь приведены команды по версии 6. 0, хотя сегодня все чаще используется более поздние версии (в том числе русифицированные), совместимые с Word (команды те же). В приводимой ниже блок-схеме справа приведены команды, используемые в программе SPSS и переменные, по которым мы делали обработку данных, а слева – пояснения и комментарии.
Таблица 4. Блок - схема обработки данных.
| № | Команды SPSS 6. 0 | Содержание операции |
| Statistics®Summarize®Frequencies [VAR00030; VAR00032; VAR00033] | Расчеты линейного частотного распределения указанных переменных. | |
| File®New®Syntax [missing value var00001; var00002; var00006; var00030] | Исключение всех единиц анализа, в которых переменные №1, 2, 6, 30 равны нулю. Если этого не сделать, средняя величина каждой из переменных будет неоправданно занижена | |
| Statistics®Summarize®Crosstabs…®Row(s) [var00001; var00002; var00006] Column(s) [var00030] Cells®Percentages Row]. | Расчет кросстабов. |
Тема 5. 9 Обработка бит-векторов. Реализация булевых функций
1) Логические функции, Способы описания функций алгебры логики.
Другие названия ФАЛ(функцией алгебры логики): логическая, булева или переключательная функция. В алгебре логики переменная может принимать одно из двух значений: True и False.
|
|
|
2 способа описания:
Словесный способ. Здесь все случаи, при которых функция принимает значения 0 или 1, опи- сываются словесно. Так, функцию «ИЛИ» со многими аргументами можно описать следующим обра- зом: функция принимает значение 1, если хотя бы один из аргументов принимает значение 1, иначе значение функции равна 0.
Табличный способ. Булева функция задается в виде таблицы истинности. В левой части таблицы истинности записываются все возможные n-разрядные двоичные комбинации аргументов, а в правой – значения функции на этих наборах. Таблица ис- тинности содержит 2n строк.
Числовой способ. Функция задается в виде последовательности десятичных эквивалентов тех наборов аргументов, на которых функция принимает значение 1. Например, двоичные наборы 010 и 101 имеют десятичные номера 2 и 5 соответственно.
Аналитический способ. Предполагает описание ФАЛ в виде алгебраического выражения, получаемого путем применения к аргументам операций булевой алгебры.
К 
оординатный способ. При этом способе задания таблица истинности заменяется коорди- натной картой состояний, известной под названием карты Карно. Такая карта содержит 2n клеток по числу возможных наборов из n переменных.
Г 
рафический, или геометрический способ. Булева функция задается с помощью n-мерного куба. Множество наборов, на которых определена функция n переменных, представляется верши- нами n-мерного куба. Отметив точками те вершины куба, в которых функция принимает единичное (либо нулевое) значение, получаем геометрическое представление функции.
2) Элементарные функции алгебры логики.
Алгебра логики (АЛ) является основным инструментом синтеза и анализа дискретных автоматов всех уровней.
Алгебра логики называют также Булевой алгеброй.
АЛ базируется на трёх функциях, определяющих три основные логические операции.
Функция отрицания (НЕ). f1 =`X
Функция логического умножения (конъюнкции). Функция логического умножения записывается в виде f2=X1·X2. Конъюнкцию называют функцией И, элемент, реализующий эту функцию, элементом И.
Логическое сложение (дизъюнкция). Функция логического сложения записывается в виде f3=X1 + X2. функцию дизъюнкции часто называют функцией ИЛИ.
|
|
|
3) Правила алгебры логики.
Правила эти определяются для двух возможных логических значений «1» (True) и «0» (False), а также трех базовых логических опе- раций: «НЕ», «И» и «ИЛИ. Базовые логические операции перечислены в порядке пониже- ния их приоритетности. Учет приоритетности операций позволяет сократить число скобок при записи логических выражений.
1) ассоциативность
2) коммутативность
3 
) дистрибутивность
4) Понятие логического базиса.
Логическим базисом называется минимальный необходимый набор логических функций, с помощью которых может быть реализовано логическое выражение любой сложности.
Функции И, ИЛИ, НЕ образуют основной логический базис.
" И-НЕ" (базис Шеффера)
" ИЛИ-НЕ" (базис Пирса или функция Вебба).
5) Аналитическое представление булевых функций.
При аналити- ческой записи ФАЛ представляется либо в виде логической суммы элементарных логических произ- ведений (дизъюнкции элементарных конъюнкций), либо в виде логического произведения элемен- тарных логических сумм (конъюнкции элементарных дизъюнкций). Первая форма записи носит на- звание дизъюнктивной нормальной формы (ДНФ), вторая – конъюнктивной нормальной формы (КНФ).
Элементарной конъюнкцией (элементарным логическим произведением) называют логическое произведение любого количества переменных (аргументов)
Дизъюнктивная нормальная форма (ДНФ) – это логическая сумма элементарных логических произведений
Минтерм (единичный набор функции) – это логическое произведение всех переменных, взятых с отрицанием или без.
Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, состоящая из всех минтермов булевой функции. Для получения СДНФ на основе таблицы истинности необходимо:
1)каждый из входных наборов, на которых булева функция принимает значение «1»,
представить в виде элементарного произведения (конъюнкции).
2)полученные элементарные логические произведения объединить знаками логического сложения (дизъюнкции).
|
|
|
6) Минимизация логических функций и ее цели.
Проблема минимизации логических выражений проистекает из практических задач создания логических схем. В качестве исходной аналитической формы обычно рассматривают совершенные ДНФ и КНФ, которые во многих случаях оказываются излишне сложными, из-за чего их техническая либо программная реализация получается избыточной. Для упрощения СДНФ и СКНФ используются различные методы минимизации – преобразования логической функции с целью упрощения ее ана- литической записи.
7) Минимизация логических функций методом Квайна
1. Нахождение простых импликант
2. Составление импликантной матрицы и расстановка меток избыточности
3 
. Нахождение существенных импликант и исключение связанных с ними строк и столбцов
4. Определение и запись минимальной нормальной формы
8) Минимизация по методу Квайна – Мак-Класски
Метод Квайна – Мак-Класски отличается от метода Квайна только в той части, которая связана со способом нахождения простых импликант. Описанная модификация заменяет лишь первый шаг метода Квайна, при этом все последую- щие шаги производятся аналогично методу Квайна.
9) Минимизация логических функций методом Петрика.
Метод Петрика (Petrick) также имеет целью упрощение метода Квайна, но в части нахожде- ния всех тупиковых форм по импликантной матрице.
1 
0) Минимизация логических функций методом карт Карно.
11) Минимизация частично определенных функций.
Наиболее удобно это производить с помощью карт Карно.
Принимаю * за 1 или 0.
12) Сигналы в цифровой схемотехнике.
Цифровой сигнал – это сигнал, который может принимать два значения, рассматриваемые как логическая «1» и логический «0». Устройства, работающие только с цифровыми сигналами, называ- ются цифровыми устройствами.
положительный сигнал (сигнал положительной полярности) – сигнал, активный уровень которого – логическая «1» («0» соответствует отсутствию сигнала);
отрицательный сигнал (сигнал отрицательной полярности) – сигнал, активный уровень которого – логический «0» («1» соответствует отсутствию сигнала);
13) Логические элементы и их графическое обозначение.
Логический элемент «НЕ» - противоположное значение сигнала.
Логический элемент «И» - всегда 1
Л 
огический элемент «ИЛИ» -всегда 0
Л 
огический элемент «И-НЕ» -0
Э 
лемент «ИЛИ-НЕ» -1
14) Положительная и отрицательная логика.
Н 
апряжения на входах и выходах логических элементов могут принимать два уровня: высо- кий (H – high) и низкий (L –low). Если высокий уровень соответствует логической «1», а низкий уро- вень – логическому «0», то принято считать, что логический элемент работает с положительной логи- кой. Если высокий уровень соответствует логическому «0», а низкий уровень – логической «1», то элемент работает с отрицательной логикой
|
|
|
15) Мультиплексоры и демультиплексоры.
Mультипле́ ксор — устройство, имеющее несколько сигнальных входов, один или более управляющих входов и один выход. Мультиплексор позволяет передавать сигнал с одного из входов на выход; при этом выбор желаемого входа осуществляется подачей соответствующей комбинации управляющих сигналов.
Мультиплексоры могут использоваться для преобразования параллельного двоичного кода в последовательный. Мультиплексоры могут использоваться в, триггерных устройствах,
Д 
емультиплексор Они обеспечивают подключение единственного входа к одному из m выходов. При необходимости увеличить число выходных каналов можно построить логическую струк- туру демультиплексорного дерева. мультиплексор можно построить на основе точно таких же схем логического " И", как и при построении мультиплексора.
16) Шифраторы и дешифраторы.
Шифратором (кодером) называется комбинационное логическое устройство для преобразо- вания n-разрядного унитарного кода в m-разрядный параллельный код.
Максимальное число входов шифраторов не превышает количества возможных комбинаций выходных сигналов (n < = 2 m ).
В результате шифрации происходит «сжатие» информации.
Одно из основных применений шифратора – ввод данных с клавиатуры, при котором нажатие клавиши с десятичной цифрой должно приводить к передаче в устройство двоичного кода данной цифры
Дешифратором (декодером) называют устройство с несколькими входами и выходами, у ко- торого определённым комбинациям входных сигналов соответствует активное состояние одного из выходо
Дешифратор называется полным, если число выходов равно максимально возможной разрядности выходного слова ( 
). Дешифратор называется неполным, если часть входных разрядов не используется (то есть число выходов меньше ).
они могут преобразовывать двоичный код в разные системы счисления
17) Преобразователи кодов.
Преобразователи кодов (конвертеры) обеспечивают перевод информации из одной формы в другую
Шифраторы, дешифраторы- преобразователи кодов.
18) Схемы контроля четности.
Простой и эффективный способ обнаружения ошибок при записи, чтении и передаче информации основан на допущении, что в каждый момент времени ошибка может возникнуть только в одном разряде, и проявляется она в лишней единице или в потере единицы. В обоих случаях число единиц в коде изменяется на одну. Если передаваемая кодовая комбинация содержит чётное число единиц по всем разрядам, а на конце линии передачи это число окажется нечётным, значит, появилась ошибка
На передающей стороне формируется контрольный, или паритетный бит. бит передаётся вместе с информацией.
Паритет может быть чётным или нечётным
В случае нечётного паритета контрольный бит формируется таким образом, чтобы сумма всех единиц в передаваемом коде, включая контрольный бит, была чётной. На практике нечётный паритет используется чаще, так как позволяет фиксировать полное пропадание информации
При проверке как чётности, так и нечётности в случае отсутствия ошибки на выходе схемы контроля обычно формируется логическая «1», а при ошибочном – логический «0».
19) Цифровые компараторы.
логическое устройство с двумя входами, на которые подаются два разных двоичных слова равной в битах длины и тремя двоичными выходами, на которые выдаётся сравнения входных слов, — первое слово больше второго, меньше или слова равны.
Компараторы широко используются в вычислительной технике, измерительной технике, радио- и проводной связи, бытовых приборах. Например, цифровые часы с будильником содержат цифровой компаратор, при совпадении текущего времени с заданным подается звуковой сигнал.
20) Полусумматор и одноразрядный полный сумматор.
Полусумматор позволяет вычислять сумму A+B, где A и B — это разряды двоичного числа,
Поскольку полусумматор не имеет входа для приёма единицы переноса, то он может быть использован только при сложении младших разрядов чисел. При сложении старших разрядов необ- ходимо использовать так называемый полный сумматор, который учитывает возможный перенос из предшествующего младшего разряда.
Полные сумматоры могут использоваться также для суммирования чисел в отрицательной логике.
На базе полных сумматоров можно реализовать сложение многоразрядных чисел, причём суммирование может быть либо последовательным, либо параллельным.
Сумматор может вычислять не только сумму, но и разность входных кодов, то есть работать в качестве вычитателя. Для этого нужно вычитаемое поразрядно инвертировать, а на вход переноса младшего разряда подать единичный сигнал.
21)Последовательные и параллельные многоразрядные сумматоры.
Используя одноразрядный сумматор, можно построить суммирующее устройство для сложения многоразрядных двоичных чисел. Различают многоразрядные последовательные и параллельные сумматоры.
Последовательный сумматор состоит из одноразрядного сумматора, на входы которого из сдвигающих регистров, хранящих слагаемые А и В, подаются по тактам разряд за разрядом коды этих чисел, начиная с младшего разряда
Недостатком последовательного сумматора является то, что выполнение операции сложения растягивается на множество тактов,
Значительно меньшее время выполнения операции имеет параллельный сумматор. В этом устройстве операция сложения производится одновременно во всех разрядах чисел
22) Программируемые логические устройства.
Программирование ПЛУ осуществляет пользователь – создатель электронной аппаратуры
В процессе программирования в схеме происходят обратимые и необратимые изменения ее началь- ной структуры
. Главное преимущество ПЛУ по сравнению с другими специализированными мик- росхемами – малое время создания нужного варианта схемы
Развитие ПЛУ идет по пути совершенствования их архитектуры и технологии, расширения возможностей и быстродействия, и все это при одновременном снижении потребляемой мощности.
Программируемые логические матрицы и Программируемая матричная логика
Программируемые логические матрицы представляют собой наиболее универсальный вари- ант ПЛУ. В них имеется возможность программировать как матрицу элементов «И», так и матрицу элементов «ИЛИ»
23) Понятие последовательностной схемы.
Последовательностными называют такие логические устройства, в которых выходной сигнал зависит не только от текущих входных логических значений, но и от тех, которые действовали на входе в предыдущие моменты времени
Последовательностная схема состоит как из логических, так и запоминающих элементов
Следовательно, здесь речь идет о хранении результатов воздействия последовательности входных сигналов в предыдущие такты. Поэтому последовательностные схемы называют также многотактными
В последовательностных схемах, как уже отмечалось, кроме логических элементов, обязательно содержатся также элементы памяти, способные хранить установленное состояние неограниченно долго, во всяком случае до следующего такта.
24) RS – триггеры.
RS-триггер – это элемент с двумя входами (S и R) и двумя выходами – прямым (Q) и инверсным (Q ).
триггер, который сохраняет своё предыдущее состояние при нулевых входах и меняет своё выходное состояние при подаче на один из его входов единицы.
RS-триггер используется для создания сигнала с положительным и отрицательным фронтами, отдельно управляемыми посредством стробов, разнесённых во времени.
Асинхронный RS-триггер (или RS-защелка) снабжен только двумя информационными входами: входом сброса R и входом установки S.
Синхронный RS-триггер может быть из получен асинхронного введением дополнительной логической схемы, которая формирует на его входах активные сигналы только при наличии дополнительного сигнала синхронизации на входе
25) D – триггеры.
Он имеет один информационный вход D и один тактирующий вход C.
запоминает состояние входа и выдаёт его на выход.
триггером-защёлкой
П 
о сигналу синхронизации в D-триггер пере- писывается информация, в данный момент присутствующая на входе D. По определению такой триг- гер может быть только синхронным
информация на выходе остается неизменной вплоть до прихода следующего импульса синхронизации.
D-триггер можно образовать из любых RS- или JK-триггеров
26) JK – триггеры.
работает так же как RS-триггер, с одним лишь исключением: при подаче логической единицы на оба входа J и K состояние выхода триггера изменяется на противоположное
На базе JK-триггера возможно построить D-триггер или Т-триггер
Универсальный JK-триггер имеет два информационных входа J и K
Универсальность JK-триггера состоит в том, что он может выполнять функции RS-, Т- и D-триггеров.
Комбинированный JK-триггер отличается от универсального наличием дополнительных асинхронных входов S и R для предварительной установки триггера в определенное состояние (логической 1 или 0).
27) T – триггеры.
П 
ри построении счетчиков возникает необходимость в триггере
имеет один информационный вход T.
Основное свойство T-триггера − деление входной частоты на 2
Очередное состояние Т- триггера определяется лишь его состоянием в предыдущем такте
28) DV – триггеры и TV – триггеры.
D 
V-триггер представляет собой модификацию D-триггера
D-триггер с разрешаю-щим входом называют DV-триггером. При V= 1 он работает как D-триггер, а при V=0 сохраняет свое состояние.
Наличие V -входа расширяет функциональные возможности D-триггера, позволяя в нужные моменты времени сохранять информацию на выходах в течении требуемого числа тактов.
Асинхронные и синхронные TV-триггеры могут быть получены на базе JK-триггера
29) Двухступенчатые триггеры.
Двухступенчатый триггер состоит из двух последовательно соединенных ступеней, причем, каждая ступень содержит по синхронному RS-триггеру
Первая ступень – ведущая или М-секция принимает информацию с входных линий.
Состояние выходов ведущей ступени подается на вторую ступень – ведомую. S секция.
После снятия синхроимпульса приём информации в первую ступень триггера запрещается, а уже имеющаяся информация из первой ступени переписывается во вторую и появляется на выходе триггера.
30) Регистры хранения.
Регистром называется последовательностное устройство, предназначенное для записи, хране- ния и/или сдвига информации, представленной в виде многоразрядного двоичного кода.
Элементами структуры регистров является синхронные триггеры D-типа или JK-типа с дина- мическим или статическим управлением
Занесение информации в регистр называют операцией ввода или записи.
Выдачу информации внешним устройствам называют операцией вывода, или считыва- ния.
В параллельных регистрах информация заносится и считывается параллельно. (для хранения двоичной информации небольшого объёма в течение короткого промежутка времени)
В последовательных регистрах запись и считывание информации производится последова- тельно (разряд за разрядом), начиная со старшего либо младшего разряда регистра.
31) Сдвиговые регистры.
Различают два вида сдвигов: вправо и влево.
Сущность сдвига состоит в том, что с приходом каждого тактового импульса происходит пе- резапись содержимого каждого триггера в соседний триггер без изменения порядка следования еди- ниц и нулей.
Регистры сдвига обычно строятся на базе D- и JK-триггеров.
Регистр, позволяющий производить сдвиг информации в обоих направлениях, называется ре- версивным.
32) Двоичные счетчики с последовательным переносом.
К двоичным относятся счетчики, модуль счета которых равен целой степени числа 2.
Наиболее простую внутреннюю структуру имеют двоичные счетчики с последовательным переносом. В них переключение каждого последующего триггера может произойти только после пе- реключения предыдущего.
Главное достоинство счётчиков с последовательным переносом – простота схемы.
Основной недостаток – сравнительно низкое быстродействие, поскольку триггеры срабатывают последователь- но, один за другим.
33) Двоичные счетчики с параллельным переносом.
Время установления выходного кода счетчика можно уменьшить, если разрядные триггеры будут переключаться не последовательно, а одновременно. Для этого нужно отказаться от асинхрон- ных триггеров в пользу синхронных Т-триггеров и определить алгоритм переключения каждого раз- рядного триггера.
Срабатывание триггеров параллельного счётчика происходит синхронно, задержка переклю- чения всего счётчика равна задержке переключения одного триггера.
Если же для формирования сигнала переноса использовать инверсные выходы триггеров разрядов, счетчик будет вычитающим.
В схемном отношении счётчик с параллельным переносом сложнее счётчиков с последова- тельным переносом
+ быстродействие
34) Счетчики с произвольным коэффициентом пересчета.
Счетчики с коэффициентом пересчета строятся на основе двоичных счетчиков.
Принцип работы таких счетчиков заключается в исключении «лишних» устойчивых М состояний у двоичного счетчика с коэффициентом пересчета 2n.
В счетчиках с произвольным порядком счета в процессе счета счетчик принимает состояния, не соответствующие его эквивалентному представлению в двоичном коде
35) Кольцевой счетчик и счетчик Джонсона.
Построены на базе регистров сдвига, где информационный вход первого триггера соединен с выходом последнего триггера. В результате триггеры регистра сдвига образуют замкнутое кольцо.
Если в один из триггеров регистра ввести логическую единицу, то эта единица с каждым так- товым импульсом будет переходить от одного триггера к другому, повторно возвращаясь в данную позицию с циклом, равным числу триггеров в кльце.
если одну из связей между триггерами сделать перекрёстной, то есть вход одного из триггеров соединить с инверсным выходом предыдущего триггера. Такие устройства называют счётчиками Джонсона.
Недостатки – повышенный расход триггеров и высокая вероятность сбоев
П 
оследний недостаток устраняют введением корректирующей логиче- ской цепи, следящей за состоянием триггеров. При появлении ложных сигналов на вход подаются импульсы, исправляющие положение в новом цикле
36) Метрики параллельных вычислений.
Метрики параллельных вычислений — это система показателей, позволяющая оценить преимущества, получаемые при параллельном решении задачи на n процессорах, по сравнению с последовательным решением той же задачи на единственном процессоре.
n — количество процессоров, используемых для организации параллельных вычислений;
O(n) — объем вычислений, выраженный через количество операций, выполняемых n процессорами в ходе решения задачи;
T(n) — общее время вычислений (решения задачи) с использованием n процессоров.
По существу, можно выделить четыре группы метрик.
Первая группа характеризует скорость вычислений. ( индексом параллелизма и ускорением. )
Вторую группу образуют метрики эффективность и утилизация
Третья группа метрик, — избыточность и сжатие
четвертую группу образует единственная метрика — качество
37) Законы Амдала и Густафсона.
Джин Амдал (Gene Amdahl) — один из разработчиков всемирно известной системы IBM 360.
Проблема рассматривалась Амдалом исходя из положения, что объем решаемой задачи с изменением числа процессоров, участвующих в ее решении, остается неизменным.
Такая постановка характерна для случаев, когда основным требованием является скорость вычислений, например, для задач, выполняемых в реальном времени
В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента
Не для всякой задачи имеет смысл наращивание числа процессоров в вычислительной системе.
Более того, если учесть время, необходимое для передачи данных между узлами вычислительной системы, то зависимость времени вычислений от числа узлов будет иметь максимум.
|
|
|
