Абай атындағы

 
136 
class of languages is generated by precedence grammar. This algorithm is classified as shift-
reduce  and  has  a  finite  description.    Besides  computer  implementation  of  this  algorithm 
analysis shows a relatively high efficiency. 
 
Формальные  грамматики,  являясь  порождающим  инструментом,  точнее,  порождая 
цепочки  языка,  не  вполне    удобны  для  целей  анализа  самих    цепочек.  В  связи,  с  чем 
представляет интерес  такой формальный инструмент как автоматы [1],[2]. Вспомним, 
что  как  и  грамматики  автоматы  разбиты  на  классы  в  зависимости  от  того  какой  тип 
языка  подвергается  анализу.  В  данной  публикации  рассматриваются  особенности 
эффективного детерминированного автомата, осуществляющего анализ снизу-вверх, на 
основе  схемы  предшествования.  В  процессе  анализа  входной  цепочки  анализатор 
использует  правила  вывода  и  отношения  предшествования  между  парами  символов 
грамматики. Причѐм для каждой пары символов (

1
, 

2
) из V
T

V
A
  могут  выполняться 
отношения  предшествования  лишь  трѐх  типов  <
.
  –  читается  как  «раньше», 
.
>  – 
читается  как  «позже», 
.

  –  читается  как  «вместе».  При  этом,  если  между  парой 
символов,  образованной  из  крайне  левого  символа  входной  ленты  и  крайне  правым 
символом  (вершиной  стека)  выполняется  отношение  <
.
,  то  символ  входной  ленты 
записывается в стек, а знак отношения <
.
помещается в стек между этими символами. 
Если  же  между  парой  символов  выполняется  отношение,  то  крайне  левый  символ 
входной  ленты  записывается  в  стек  без  символа 
.

.  Такие  действия  автомата 
идентифицируются  как  «сдвиг».  В  противоположность,  если  для  пары  (

1
, 

2
) 
выполнено  отношение 
.
>,  то  дальнейшие  действия  автомата  идентифицируются  как 
«свѐртка». 
Сформированная  в  стеке  правая  часть  правила  грамматики  вместе  с  ближайшим 
слева  символом  <
.
  заменяется  на  символ  левой  части  этого  правила.  При  этом,  если 
между  символом,  оказавшимся  в  вершине  стека  и  символом  из  левой  части  правила 
имеет  место  отношение  <
.
,  то  символ  <
.
записывается  в  стек  первым  и  лишь  затем 
символ  из  левой  части  правила.  Если  же  имеет  место  отношение 
.

,  то  символ  левой 
части правила записывается сразу в новую вершину стека. И далее процесс повторяется 
для  новой  пары  символов  –  крайне  левого  символа  входной  цепочки  и  символа  в 
вершине  стека.  Процесс  успешно  завершается,  если  входная  цепочка  содержит  лишь 
граничный маркер #, а в стеке находится цепочка #I. 
Пусть  G=<  V
T
,V
A
,  I,  P>
   
это  КС-грамматика.  Пусть  (

1
, 

2
)  –  это  произвольная 
упорядоченная пара символов из {V
T

V
A
}. 
Определение. 1) Будем говорить, что для пары (

1
, 

2
) в грамматике G
 
выполняется 
отношение 
.

, если среди множества правил грамматик Р содержится правило вывода 
вида А







2
1
 , что обозначается так  

1
 
.

 

2
. В противном случае – отношение 
.

 
для  данной  пары  (

1
, 

2
)  не  выполняется.  2)  Будем  говорить,  что  для  пары  (

1
, 

2
)  в 
грамматике G
 
выполняется отношение <
.
  («раньше») если в Р найдѐтся правило  вида 
А






B
1
  и  из  нетерминального  символа  В  выводима  цепочка,  начинающаяся  с 
символа 

2 
:В
*



2
, что обозначается 

1
<
.

2.  
В противном случае считается, что отношение <
.
 для данной пары не имеет места. 
3) Будем говорить, что для пары (

1
, 

2
) в грамматике G
 
выполняется отношение 
.
> 
(«позже»), если справедливо хотя бы одно из следующих утверждений: 
а) в множестве Р найдѐтся правило вывода вида А






2
B
и из нетерминального 

 
137 
символа  В  выводится  цепочка,  заканчивающаяся  символом 

1 
т.е  .  В
*

1

, 
*
T
}
V
{
A
V



 
б) в множестве Р найдѐтся правило вида А





BC
, такое что  В
*

1

 и С
*



2
, 
где В,С
A
V

; 
*
}
{
,
A
T
V
V




. 
В противном случае, отношение 
.
> для пары (

1
, 

2
) считается не выполненным. 
Обратим  внимание  на  то,  что  существуют  КС-грамматики,  для  некоторых  пар 
символов  которых  выполняются  два  или,  более  того,  все  три  отношения 
предшествования. 
Пример 1. Пусть G
 
грамматика с правилами вида: 
 
1)
 
I→ab 
2)
 
I→aB 
3)
 
I→AB 
4)
 
A→Ca 
5)
 
B→bD 
6)
 
C→c 
7)
 
D→d 
Очевидно, что для пары (а,b) выполнены: a
.

b, a <
.
b, a
.
>b. 
Для того чтобы отделить такие случаи, подобные рассмотренному выше, вводится 
Определение  2:  КС-грамматика  G  называется  грамматикой  предшествования,  если 
для каждой упорядоченной пары еѐ символов выполняется не более одного отношения 
предшествования. 
Для  языков,  порождѐнных  грамматиками  предшествования  без  правил  вывода  с 
одинаковыми  правыми  частями,  применим  детерминированный  анализатор  на  основе 
предшествования.  
Напомним, что, сдвигая на каждом такте входную цепочку на один символ влево и 
определяя  на  каждом  такте  отношение  предшествования  для  пары:  крайне  левый 
символ входной ленты и символ в вершине стека, анализатор последовательно находит 
подцепочки,  являющиеся  правыми  частями  правил  грамматики,  и  заменяет  их 
соответствующими левыми частями этих же правил. Если исходная цепочка входит в 
язык,  порождаемый  грамматикой  предшествования,  то  анализатор,  в  конце  концов, 
свернѐт исходную цепочку к начальному символу грамматики. 
Далее проиллюстрируем работу анализатора на одном простом примере. В качестве 
грамматики возьмѐм грамматику с правилами вывода: 
 
1)
 
I→a 
2)
 
I→aT 
3)
 
I→(I) 
4)
 
T→b 
5)
 
T→bT 
 
Очевидно,  что  данная  грамматика  является  грамматикой  предшествования,  а 
матрица предшествования выглядит следующим образом:   
 
 
I 
T 
a 
b 
( 
) 
I 
 
 
 
 
 
.

 
T 
 
 
 
 
 
.
> 
a 
 
.

 
 
<
.
 
 
.
> 
b 
 
.

 
 
<
.
 
 
.
> 
( 
.

 
 
<
.
 
 
<
.
 
 
) 
 
 
 
 
 
.
> 
 

 
138 
Совместим  визуально  входную  ленту  и  магазин  и  проиллюстрируем  работу 
анализатора на примере цепочки (abbb), при этом стрелка → будет означать «сдвиг», а 
стрелка  ←  означат  «свѐртку».  Итак,  имеем  следующую  последовательность 
преобразований: 
[#,(abbb)#]→[# <
.
 (,abbb)#]→[# <
.
 (<
.
a,bbb)#]→ 
[#<
.
 (<
.
a<
.
b,bb)#]→[# <
.
 (<
.
a<
.
b<
.
b,b)#]→ 
      [#<
.
 (<
.
a<
.
b<
.
b<
.
b,)#]←[# <
.
 (<
.
a<
.
b<
.
bT,)#] ← 
      ←[#<
.
 (<
.
a<
.
bT,)#] ←[#<
.
 (<
.
aT,)#] ←[#<
.
 (I,)#] →  
       → [#<
.
 (I),#] ←[#I,#]  , 
откуда следует, что входная цепочка (abbb) допущена и является правильной цепочкой 
языка, порождѐнного исходной грамматикой предшествования.  
Рассмотренный  выше  пример  имел  одну  особенность,  а  именно,  при  свертке, 
несмотря  на  различие  правил,    отношение  между  символом  в  вершине  стека  и 
символом из левой части сворачиваемого правила, во всех случаях, было 


. И в этом 
смысле более интересной оказывается грамматика   с правилами 
 I→ (А              2) I→a                  3)A→ Ia) 
осуществим вывод  цепочки ((((aa)a)a)a)    
I
1

(A
3

(Ia)
1

((Aa)
3

((Ia)a)
1

(((Aa)a)
3

(((Ia)a)a)
1

((((Aa)a)a)
3

((((Ia)a)a)a)
2

 ((((aa)a)a)a)    
Вычислим отношения между символами и заполним  таблицу  
 
 
I 
A 
a 
( 
) 
# 
I 
 
 


 
 
 
.
> 
A 
 
 
.
> 
 
 
 
.
> 
a 
 
 
.
> 
 
 


 
.
> 
( 
<
.
 
 


 
<
.
 
 
<
.
 
 
 
.
> 
) 
 
 
.
> 
 
 
 
.
> 
# 
<
.
 
<
.
 
<
.
 
<
.
 
<
.
 
 
 
детерминированный  процесс    анализа  приводит  к  следующей  последовательности 
изменений конструкции стек - входная лента:  
 [#,((((aa)a)a)a)#]→[# <
.
(, (((aa)a)a)a)#]→[# <
.
(<
.
(, ((aa)a)a)a)#] 
→[# <
.
(<
.
(<
.
(, (aa)a)a)a)#] →[# <
.
(<
.
(<
.
(<
.
( ,aa)a)a)a)#]→ 
 [#<
.
 (, A#]
3

 [#<
.
 (A,#] 
1

 [# ,I#] 
1

[# <
.
I,#] ,  цепочка допущена.    
Таким  образом,  синтаксический  анализ  на  основе  предшествования  является 
достаточно 
привлекательной 
процедурой 
имеющей 
свои 
специфические 
особенности[3].    Одной  из  важнейших  из  них  является  автоматическое  построение 
таблиц предшествования. Заметим, что такая таблица может быть построена на основе 
двух отношений. 
 
 
1.
 
А.  Ахо,  Дж.  Ульман.  Теория  синтаксического  анализа  компиляции  и  перевода. 
Т.1.,М: Мир,1983 
2.
 
Т.  Прат,  М.  Зелковиц.  Языки  программирования.  Разработка  и  реализация.4-е 
издание. Питер.,2002г.   
3.
 
Дюсембаев  А.Е..  Архитектура  компьютеров.Computer  Architecture.  Tempus-Tacis 
Project, Contract#CD_JEP-22077-2001, 2-nd Edition, 2010 

 
139 
УДК 517. 962.2, 519. 876.2 
А.Дж. Сатыбаев 
1
,  Г.А. Калдыбаева 
2
, Т.М. Асилбеков 
1 
 
ЧИСЛЕННАЯ РЕАЛИЗАЦИЯ ОДНОМЕРНОЙ ПРЯМОЙ И ОБРАТНОЙ 
ЗАДАЧИ ТЕРМОУПРУГОСТИ С МГНОВЕННЫМ ИСТОЧНИКОМ 
 
(
г.Ош, Ошский технологический университет
1
, 
Ошский государственный университет
2
, Кыргызстан
) 
 
Мақалада 
термосерпінді 
жылдам 
қоректі 
бірӛлшемді 
тура 
есепті 
характеристикадағы  деректермен  берілген  есепке  келтірілген  және  ақырлы-
айырымдық әдістермен сандық есептеу жұмыстары жүргізілген.  
В  данной  статье  одномерная  прямая  задача  термоупругости  с  мгновенным 
источником  приведена  к  задаче    с  данными  на  характеристиках  и  проведены 
численные расчеты конечно-разностным методом. 
In  this  article, a  direct  one-dimensional problem  of    thermoelasticity  with  instantaneous 
source  is  given  the  problem  with  the  data  on  the  characteristics  and  the  numerical 
calculations of finite-difference method. 
 
Обратные  задачи  термоупругости  в  теоретическом  плане  исследованы  В.Я. 
Козловым  и др. [1]. 
Численное  решение  или  численная  реализация  одномерной  прямой и  обратной 
задачи  термоупругости  рассмотрены  в  [2]  с  различными  начальными  и  граничными 
условиями,  а  в  нашем  случае,  рассмотрено  граничное  условие,  представлено  в  виде  
мгновенного источника, т.е. на границе задается 
 
t

 - дельта функция Дирака.  
Постановка задачи. Рассмотрим задачу 
 
   


   


 
 


 




'
'
'
,
*
2
3
*
z
z
z
tt
tt
t
z
R
z
z
U
z
z
U
z
z
U
z














, 


R
z
, 


R
t
; 
 
 
 
 
 
(1) 
 
0
,
0


t
t
z
u
,  
 
 
t
U
z
z

2
1
0



,  
 
 
(2) 
 
 
t
f
t
z
U
z


0
,
,  
 
T
t
,
0

, 
 
 
 
(3) 
где 
 


 
 



t
z
dy
y
t
z
R
t
x
F
,
0
,
)
,
(



,   
 
y

  -  тепловое  расширение, 
 
z

, 
 
z

  - 
коэффициенты Ламэ, 
 
z

 - плотность среды.  
Прямая  задача  заключается  в  определении  функции 
 
t
z
U ,   -  возмущения 
среды из задачи (1) - (2) при известных коэффициентах 
 
z

, 
 
z

, 
 
z

, 
 
z

. 
Обратная  задача  заключается  в  определении  функции 
 
z

  -  тепловое 
расширение  из  задачи  при  известных  коэффициентах 
 
z

, 
 
z

, 
 
z

,  а  также  при 
известной дополнительной информации 
 
t
f
.  
     Пусть относительно коэффициентов уравнения (1) выполнены условия 
 
z

, 
 
z

, 
 
 


     

  
 
d
C
d
o
d
o
C
z
,
0
6
2
,
,
z
,
z
,
z
supp
,
,









  , 
а относительно  
 
 
d
o
C
z
,
5


 .         
 
 
 
          (*) 
Численное  решение.  Использую  все  выкладки  [3]  из  задачи  (1)  -  (3)  получим 
задачу с данными на характеристиках 

 
140 
 
             


 
t
T
x
t
t
t
x
Z
t
x
o
c
x
C
t
x
V
x
q
t
x
V
t
x
V
x
xx
tt







1
,
0
,
,
,
,
,
,
'

  (4) 
 
 
 
x
t
x
V
x
t



,
, 


t
T
t
x


,
,   
 
 
(5) 
 
 
 
t
f
t
x
V

,
.  
 
t
t
,
0

. 
 
 
 
(6) 
Здесь прямая задача заключается в определении функции 
 
t
x
V
,  из (4) - (5), а 
обратная  задача  в  определении  пары  функций 
 
t
x
V
,   и 
 
t
x
F ,   из  задачи  (4)  -  (6),  
)).
,
(
(
)
,
(
)),
(
2
)
(
3
(
)
,
([
t
x
R
t
x
Z
x
x
t
x







 .  
Связь задачи (4)-(6) с задачей (1) - (3) и их функций даны в [2]. 
 Отметим, что здесь 
 
 
   




x
c
o
c
o
c
x
P
0
2
1
2







d
F
,
'
. 
 
 
(7) 
Прямую  и  обратную  задачу  будем  решать  конечно  –  разностным  методом,  для 
этого  введем  равномерную  сеточную  область,  при  этом  отбрасывая  малые  члены 
порядка 


2
2
, h
O

 получим разностную задачу:  
k
i
xx
tt
LV
V
V


,  


k
i
k
ih



,
; 
             
 
 
(8) 
i
i
i
P
V


,  
 
N
N
i
,


;   
 
 
 
 
(9) 
k
k
o
f
V

, 
 
N
k
2
,...
0

;  
                   
 
 
(10) 
где    




'
,
*
x
k
i
o
i
k
i
i
k
i
t
x
F
c
c
V
q
LV


 . 
Определяя сеточные функции 
k
i
V
 и, 
o
i
P
 в обратной задаче (8) - (10) можем найти 
сеточную функцию 
k
i
F
 по формуле (7). 
 Численная  реализация.  В  начале  при  известных  значениях  функций 
 
z

, 
 
z

, 
 
z

, 
 
z

, вернее при их сеточных значениях вычисляется сеточная функция 
k
i
V
 
- решения прямой задачи (8) - (9), затем при 
k
o
k
V
f

 - вычисляются значении 
k
i
V
, 
i
P  и 
одновременно 
k
i
F
, т.е. решение обратной задачи термоупругости (8)-(9).  
 В качестве модельной функции прямой задачи были взяты следующие функции 
     
1



z
z
z



, тогда  
 
2
1

x
c
;  
 
2
1

x
S
;  
 
0

x
g
;  
 
 




t
z
x
t
x
,
,




; 
 
 


t
z
x
t
x
Z
x
,
5
,
'


;  
 


t
x
R
V
V
xx
tt
,
2
5
'



 *
 


t
x,


; 
 
 


 







x
o
d
t
õ
R
x
P




8
5
8
1
,
8
5
8
1
 , 
получим прямую (11) - (12) и обратную (11) - (13) задачу  
 

  
 
 
 
t
T
x
t
T
o
t
dy
y
t
x
t
x
V
V
x
t
x
o
x
xx
tt
x











,
,
,
2
5
'
,
'
'





 
 
(11) 
 
 
x
P
t
x
V
t
x


,
,  
 
 
 
 
(12) 
 
 
t
f
t
x
V
x


0
,
,    
 
 
 
 
(13) 
где  

 
141 
 
 




x
o
dy
y
x
P

8
5
8
1
,  
 
 
 
(14) 
 
t
x,

 - известная функция. Здесь неизвестной функцией будет 
 
x

.  
 В качестве модельной функции 
 
x

 - заданы следующие:  
1. 
 
 
x
x


2
cos
1
.
2
2


 (рис. 3);    2. 
 
 
x
x


6
cos
*
2
.
0
3
2


 (рис. 4); 
3. 
 
x

 - ступенчатая функция начерченной на графике  (рис. 5); 
4. 
 
x

 - импульсная функция начерченной на графике (рис. 6).  
На  всех  четырех  рисунках  сплошная  зеленая  линия 
 
x


  -  точное  решение, 
 
x


  - приближенное решение  –  пунктирная синяя линия, красная сплошная линия  - 
 
t
f
  -  дополнительная  информация  для  обратной  задачи.  Последняя  получена 
решением  прямой  задачи,  затем  по  ней  решена  обратная  задача,  в  котором 
определялась функция 
 
x


.  
В  рисунке  3  функция 
 
z
C

  задавалась  в  виде  двух  горбов,  а  в  рис.  4  дана  6 
горбовая.  Как  видно  из  этих  рисунков  приближенно  –  вычисленное  решение 
 
x
C

  - 
последовательно  идет  за  точным  решением  и  у  приближенной  функции 
 
x
C

 
периодичность последовательно смещается в право.  
Таким  образом,  в  модельных  задачах  типа  волновой  (рис.  3,  4)  с  увеличением 
переменной  x   приближенное  решение  обратной  задачи  ухудшается,  т.е.  ошибки 
приближения накапливаются и 
 
x
C

 ухудшается.  
В  задачах  землетрясений  обычно  функции  бывают  ступенчатыми  или 
мгновенными,  поэтому  в  качестве 
 
x

  мы  задали  в  виде  ступенчатой  и  мгновенной 
(рис. 5, 6). 
Как  видно  из  этих  рисунков  приближенное  решение  обратной  задачи 
 
x
C

 
последовательно  идут  за  точными  решениями,  что  означает  построенный  алгоритм 
можно  использовать  и  для  слоистой  среды.  Отметим,  что  здесь  на  точках  разрыва 
«склеивание» не проводились. 
Для  анализа  в  первом  и  во  втором  случае  (рис.  3,  рис.  4)  обратную  задачу 
вычислим  в  разных  шагах  равномерной  сетки,  и  соответствующие  точки  проверялись 
численно и в этом абсолютная погрешность очень мала.  
В первом и во втором случае 
 
 
cx
b
a
x
2
cos




 свободные постоянные числа 


0
3
,
1
2




a
a
  последовательно  приблизили  к  функции 
 
cx
b
2
cos

,  тогда 
восстановления 
 
x

 ухудшаются.  
Если  в  двух  примерах  (рис.  3,  рис.  4)  приближенное  решение  хорошо  почти 
совпадает  с  точным  решением,  то  в  других  двух  примерах  (рис.  5,  рис.  6) 
приближенное решение последовательно уходит от точного решения.  
Отметим,  что  увеличивая  шаги  сетки,  мы  можем  увеличивать  глубины 
вычисления.  С  увеличением  горбов  погрешность  вычисления  обратной  задачи  также 
увеличивается.  
Для  проверки  устойчивости  алгоритма  был  увеличен  шаг  сетки 
1
0


z
h
, 
2
0


z
h
, 
3
0


z
h
 и в этом относительная погрешность почти одинакова, что означает, 
алгоритм  устойчив.  
Устойчивость алгоритма решения задачи проверялись:  

 
Во-первых,  измельчением  шагов  дискретизации  и  проверкой  в 
соответствующих точках; 

 
142 

 
Малым изменением в дополнительной информации. 
Проведена также полученная теоретическая оценка 
 
 


T
C
z
i
i
N
i
U
h




4
2
max
,
0


,  с  изменениями  шагов  дискретизации  и  нормы 
решения прямой задачи, т.е. последовательно изменяли шаги и решения прямой задачи.  
               Алгоритм решения одномерной прямой задачи термоупругости  
 Одномерная  прямая  задача  термоупругости  (11)  -  (12)  вычислена  в  области 
указанной  в  рис.  1,  т.е.  в  области  ограниченной  характеристики  уравнений  (11), 
 
 


ih
T
kh
ih
kh
t
ih
x
N
T
h
T
t
t
t
t
k
i
i
h









,
,
,
/
,
,
0
     
 

жүктеу/скачать 4,82 Mb.

Достарыңызбен бөлісу: