file_name: Паскаль_ДинСтруктурыДанных.ppt

alt: Тема 1. Указатели Динамические структуры данных (язык

description:
Тема 1. Указатели

Динамические структуры данных(язык Паскаль)

alt: Статические данные переменная (массив) имеет имя , по которому к ней можно обращаться размер заранее известен (задается при написании программы) память выделяется при объявлении размер…

description:
2

Статические данные

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

var x, y: integer;
    z: real;
    A: array[1..10] of real;
    str: string;

alt: Динамические данные размер заранее неизвестен, определяется во время работы программы память выделяется во время работы программы нет имени?

description:
3

Динамические данные

размер заранее неизвестен, определяется во время работы программы
память выделяется во время работы программы
нет имени?

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

alt: Указатели Указатель – это переменная, в которую можно записывать адрес другой переменной (или блока памяти)

description:
4

Указатели

Указатель – это переменная, в которую можно записывать адрес другой переменной (или блока памяти).
Объявление:

Как записать адрес:

var pC: ^char;    // адрес символа
    pI: ^integer; // адрес целой переменной
    pR: ^real;    // адрес вещ. переменной

var m: integer;    // целая переменная
    pI: ^integer;  // указатель
	A: array[1..2] of integer; // массив
...
pI:= @ m;    // адрес переменной m
pI:= @ A[1]; // адрес элемента массива A[1]
pI:= nil;   // нулевой адрес

@

^

nil

указатель

адрес ячейки

alt: Обращение к данным через указатель program qq; var m, n: integer; pI: ^integer; begin m := 4; pI := @m; writeln('Адрес m = ', pI);…

description:
5

Обращение к данным через указатель

program qq;
var m, n: integer;
    pI: ^integer;
begin
  m := 4;
  pI := @m;
  writeln('Адрес m = ', pI); // вывод адреса
  writeln('m = ', pI^); // вывод значения
  n := 4*(7 - pI^);     // n = 4*(7 - 4) = 12
  pI^ := 4*(n - m);     // m = 4*(12 – 4) = 32
end.

^

«вытащить» значение по адресу

alt: Обращение к данным (массивы) program qq; var i: integer;

description:
6

Обращение к данным (массивы)

program qq;
var i: integer;
    A: array[1..4] of integer;
    pI: ^integer;
begin
  for i:=1 to 4 do A[i] := i;
  pI := @A[1]; // адрес A[1]
  while ( pI^ <= 4 ) // while( A[i]  <= 4 )
    do begin
    pI^ := pI^ * 2;  // A[i] :=  A[i]*2;
    pI := pI + 1; // к следующему элементу
  end;
end.

переместиться к следующему элементу = изменить адрес на sizeof(integer)

alt: Что надо знать об указателях указатель – это переменная, в которой можно хранить адрес другой переменной; при объявлении указателя надо указать тип переменных, на которых…

description:
7

Что надо знать об указателях

указатель – это переменная, в которой можно хранить адрес другой переменной;
при объявлении указателя надо указать тип переменных, на которых он будет указывать, а перед типом поставить знак  ^ ;
знак  @  перед именем переменной обозначает ее адрес;
запись  p^  обозначает значение ячейки, на которую указывает указатель p;
nil – это нулевой указатель, он никуда не указывает
при изменении значения указателя на n он в самом деле сдвигается к n-ому следующему числу данного типа (для указателей на целые числа – на  n*sizeof(integer) байт).

alt: Тема 2. Динамические массивы Динамические структуры данных (язык

description:
Тема 2. Динамические массивы

Динамические структуры данных(язык Паскаль)

alt: Где нужны динамические массивы?

description:
9

Где нужны динамические массивы?

Задача. Ввести размер массива, затем – элементы массива. Отсортировать массив и вывести на экран.
Проблема:
	размер массива заранее неизвестен.
Пути решения:
выделить память «с запасом»;
выделять память тогда, когда размер стал известен.
Алгоритм:
ввести размер массива;
выделить память ;
ввести элементы массива;
отсортировать и вывести на экран;
удалить массив.

выделить память

удалить массив

alt: Использование указателей (Delphi) program qq; type intArray = array[1

description:
10

Использование указателей (Delphi)

program qq;
type intArray = array[1..1] of integer;
var A: ^intArray;
    i, N: integer;
begin
  writeln('Размер массива>');
  readln(N);
  GetMem(pointer(A), N*sizeof(integer));
  for i := 1 to N do
    readln(A[i]);
  ... { сортировка }
  for i := 1 to N do
    writeln(A[i]);
  FreeMem(pointer(A));
end.

выделить память

освободить память

работаем так же, как с обычным массивом!

какой-то массив целых чисел

alt: Использование указателей для выделения памяти используют процедуру

description:
11

Использование указателей

для выделения памяти используют процедуру GetMem
   GetMem( указатель, размер в байтах );
указатель должен быть приведен к типу pointer –указатель без типа, просто адрес какого-то байта в памяти;
с динамическим массивом можно работать так же, как и с обычным (статическим);
для освобождения блока памяти нужно применить процедуру FreeMem:
 		FreeMem ( указатель );

alt: Ошибки при работе с памятью Запись в «чужую» область памяти: память не была выделена, а массив используется

description:
12

Ошибки при работе с памятью

Запись в «чужую» область памяти:
память не была выделена, а массив используется.
Что делать: так не делать.
Выход за границы массива:
обращение к элементу массива с неправильным номером, при
записи портятся данные в «чужой» памяти.
Что делать: если позволяет транслятор, включать проверку         выхода за границы массива.
Указатель удаляется второй раз:
структура памяти нарушена, может быть все, что угодно.
Что делать : в удаленный указатель лучше записывать nil,            ошибка выявится быстрее.
Утечка памяти:
ненужная память не освобождается.
Что делать : убирайте «мусор»          (в среде .NET есть сборщик мусора!)

alt: Динамические массивы (Delphi) program qq; var

description:
13

Динамические массивы(Delphi)

program qq;
var A: array of integer;
    i, N: integer;
begin
  writeln('Размер массива>');
  readln(N);
  SetLength ( A, N );
  for i := 0 to N-1 do
    readln(A[i]);
  ... { сортировка }
  for i := 0 to N-1 do
    writeln(A[i]);
  SetLength( A, 0 );
end.

выделить память

освободить память

какой-то массив целых чисел

нумерация с НУЛЯ!

alt: Динамические массивы (Delphi) при объявлении массива указывают только его тип, память не выделяется: var

description:
14

Динамические массивы (Delphi)

при объявлении массива указывают только его тип, память не выделяется:
   var A: array of integer;
для выделения памяти используют процедуру SetLength (установить длину)
    SetLength ( массив, размер );
номера элементов начинаются с НУЛЯ!
для освобождения блока памяти нужно установить нулевую длину через процедуру SetLength:
 		SetLength ( массив, 0 );

alt: Динамические матрицы (Delphi)

description:
15

Динамические матрицы (Delphi)

Задача. Ввести размеры матрицы и выделить для нее место в памяти во время работы программы.
Проблема:
	размеры матрицы заранее неизвестны
Решение:

var A: array of array of integer;
    N, M: integer;
begin
  writeln('Число строк и столбцов>');
  readln(N, M);
  SetLength ( A, N, M );
  ... // работаем, как с обычной матрицей
  SetLength( A, 0, 0 );
end.

alt: Тема 3. Структуры (записи) Динамические структуры данных (язык

description:
Тема 3. Структуры (записи)

Динамические структуры данных(язык Паскаль)

alt: Структуры (в Паскале – записи )

description:
17

Структуры (в Паскале – записи)

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

Свойства:
автор (строка)
название (строка)
год издания (целое число)
количество страниц (целое число)

Задача: объединить эти данные в единое целое

Размещение в памяти

автор

название

год издания

количество страниц

40 символов

80 символов

целое

alt: Одна запись readln(Book.author); // ввод readln(Book

description:
18

Одна запись

readln(Book.author);   // ввод
readln(Book.title);
Book.year := 1998;     // присваивание
if Book.pages > 200 then   // сравнение
   writeln(Book.author, '.', Book.title); // вывод

Объявление (выделение памяти):

var Book: record
    author: string[40]; // автор, строка
    title:  string[80]; // название, строка
    year:   integer;	// год издания, целое
    pages:  integer;    // кол-во страниц, целое
  end;

название

запись

поля

Обращение к полям:

alt: Массив записей Объявление (выделение памяти): const

description:
19

Массив записей

Объявление (выделение памяти):

const N = 10;
var aBooks: array[1..N] of record
    author: string[40];
    title:  string[80];
    year:   integer;
    pages:  integer;
  end;

Books[1]           ...            Books[10]

author

title

year

pages

alt: Массив записей for i:=1 to N do begin readln(aBooks[i]

description:
20

Массив записей

for i:=1 to N do begin
  readln(aBooks[i].author);
  readln(aBooks[i].title);
  ...
end;
for i:=1 to N do
  if aBooks[i].pages > 200 then
     writeln(aBooks[i].author, '.',
             aBooks[i].title);

Обращение к полям:

alt: Новый тип данных – запись const

description:
21

Новый тип данных – запись

const N = 10;
var Book: TBook; // одна запись
    aBooks: array[1..N] of TBook;  // массив

Объявление типа:

type TBook = record
    author: string[40]; // автор, строка
    title:  string[80]; // название, строка
    year: integer;	// год издания, целое
    pages : integer;    // кол-во страниц, целое
  end;

Объявление переменных и массивов:

TBook – Type Book («тип книга») – удобно!

alt: Записи в процедурах и функциях

description:
22

Записи в процедурах и функциях

Book.author := 'А.С. Пушкин';
ShowAuthor ( Book );
Book.year := 1800;
writeln( IsOld(Book) );

Процедура:

procedure ShowAuthor ( b: TBook );
begin
  writeln ( b.author );
end;

Основная программа:

function  IsOld( b: TBook ): boolean;
begin
  IsOld := b.year < 1900;
end;

Функция:

alt: Файлы записей Объявление указателя на файл: var

description:
23

Файлы записей

Объявление указателя на файл:

var F: file of TBook;

Assign(F, 'books.dat'); { связать с указателем }
Rewrite(F);        { открыть файл для запись }
writeln(F, Book);    { запись }
for i:=1 to 5 do
  writeln(aBook[i]); { запись }
Close(F);          { закрыть файл }

Запись в файл:

alt: Чтение из файла Известное число записей:

description:
24

Чтение из файла

Известное число записей:

Assign(F, 'books.dat'); { связать с указателем }
Reset(F);        { открыть для чтения }
Read(F, Book);       { чтение }
for i:=1 to 5 do
  Read(F, aBook[i]); { чтение }
Close(F);        { закрыть файл }

«Пока не кончатся»:

count := 0;
while not eof(F) do begin
  count := count + 1;     { счетчик }
  Read(F, aBook[count]);  { чтение }
end;

пока не дошли до конца файла F
EOF = end of file

alt: Пример программы Задача: в файле books

description:
25

Пример программы

Задача: в файле books.dat записаны данные о книгах в виде массива структур типа TBook (не более 100). Установить для всех 2008 год издания и записать обратно в тот же файл.

type Tbook  … ;
const MAX = 100;
var aBooks: array[1..MAX] of TBook;
    i, N: integer;
    F: file of TBook;
begin
  { прочитать записи из файла, N - количество }
  for i:=1 to N do
    aBooks[i].year := 2008;
  { сохранить в файле }
end.

type TBook  … ;

полное описание структуры

alt: Пример программы Чтение «пока не кончатся»:

description:
26

Пример программы

Чтение «пока не кончатся»:

 Assign(f, 'books.dat');
 Reset(f);
 N := 0;
 while not eof(F) and (N < MAX) do begin
   N := N + 1;
   read(F, aBooks[N]);
 end;
 Сlose(f);

 Assign(f, 'books.dat'); { можно без этого }
 Rewrite(f);
 for i:=1 to N do write(F, aBooks[i]);
 Close(f);

Сохранение:

чтобы не выйти за пределы массива

alt: Выделение памяти под запись var pB: ^TBook; begin

description:
27

Выделение памяти под запись

var pB: ^TBook;
begin
  New(pB);
  pB^.author := 'А.С. Пушкин';
  pB^.title := 'Полтава';
  pB^.year := 1990;
  pB^.pages := 129;
  Dispose(pB);
end.

New(pB);

выделить память под запись, записать адрес в pB

pB^

Dispose(pB);

освободить память

pB: ^TBook;

переменная-указатель на TBook

alt: Сортировка массива записей Ключ (ключевое поле) – это поле записи (или комбинация полей), по которому выполняется сортировка

description:
28

Сортировка массива записей

Ключ (ключевое поле) – это поле записи (или комбинация полей), по которому выполняется сортировка.

const N = 100;
var aBooks: array[1..N] of TBook;
    i, j, N: integer;
    temp: TBook; { для обмена }
begin
 { заполнить массив aBooks }
 { отсортировать = переставить }
 for i:=1 to N do
   writeln(aBooks[i].title,
           aBooks[i].year:5);
end.

alt: Сортировка массива записей for i:=1 to

description:
29

Сортировка массива записей

for i:=1 to N-1 do
   for j:=N-1 downto i do
     if aBooks[j].year > aBooks[j+1].year
     then begin
       temp := aBooks[j];
       aBooks[j] := aBooks[j+1];
       aBooks[j+1] := temp;
     end;

alt: Сортировка массива записей Проблема: как избежать копирования записи при сортировке?

description:
30

Сортировка массива записей

Проблема: как избежать копирования записи при сортировке?
Решение: использовать вспомогательный массив указателей, при сортировке переставлять указатели.

5

1

3

2

4

До
сортировки:

После
сортировки:

Вывод результата:

for i:=1 to N do
   writeln(p[i]^.title, p[i]^.year:5);

p[i]^

p[i]^

5

1

3

2

4

alt: Реализация в программе type PBook = ^TBook; { новый тип данных } var p: array[1

description:
31

Реализация в программе

type PBook = ^TBook; { новый тип данных }
var  p: array[1..N] of PBook;
begin
  { заполнение массива записей}
  for i:=1 to N do
     p[i] := @aBooks[i];

  for i:=1 to N do
     writeln(p[i]^.title, p[i]^.year:5);
end.

for i:=1 to N-1 do
  for j:=N-1 downto i do
    if p[j]^.year > p[j+1]^.year then begin
      temp := p[j];
      p[j] := p[j+1];
      p[j+1] := temp;
    end;

вспомогательные указатели

меняем только указатели, записи остаются на местах

начальная расстановка

alt: Тема 4. Списки Динамические структуры данных (язык

description:
Тема 4. Списки

Динамические структуры данных(язык Паскаль)

alt: Динамические структуры данных Строение: набор узлов, объединенных с помощью ссылок

description:
33

Динамические структуры данных

Строение: набор узлов, объединенных с помощью ссылок.
Как устроен узел:

данные

ссылки на другие узлы

Типы структур:

списки

деревья

графы

односвязный

двунаправленный (двусвязный)

циклические списки (кольца)

alt: Когда нужны списки? Задача (алфавитно-частотный словарь)

description:
34

Когда нужны списки?

Задача (алфавитно-частотный словарь).  В файле записан текст.       Нужно записать в другой файл в столбик все слова,        встречающиеся в тексте, в алфавитном порядке, и количество     повторений для каждого слова.
Проблемы:
количество слов заранее неизвестно (статический массив);
количество слов определяется только в конце работы (динамический массив).
Решение – список.
Алгоритм:
создать список;
если слова в файле закончились, то стоп.
прочитать слово и искать его в списке;
если слово найдено – увеличить счетчик повторений, иначе добавить слово в список;
перейти к шагу 2.

alt: Что такое список: пустая структура – это список; список – это начальный узел ( голова ) и связанный с ним список

description:
35

Что такое список:
пустая структура – это список;
список – это начальный узел (голова) и связанный с ним список.

Списки: новые типы данных

type PNode = ^Node;   { указатель на узел }
     Node = record    { структура узла }
       word: string[40]; { слово }
       count: integer;   { счетчик повторений }
       next: PNode;      { ссылка на следующий }
     end;

Новые типы данных:

Адрес начала списка:

var Head: PNode;
...
Head := nil;

alt: Что нужно уметь делать со списком?

description:
36

Что нужно уметь делать со списком?

Создать новый узел.
Добавить узел:
а) в начало списка;
б) в конец списка;
в) после заданного узла;
г) до заданного узла.
Искать нужный узел в списке.
Удалить узел.

alt: Создание узла function CreateNode(NewWord: string):

description:
37

Создание узла

function CreateNode(NewWord: string): PNode;
var NewNode: PNode;
begin
  New(NewNode);
  NewNode^.word := NewWord;
  NewNode^.count := 1;
  NewNode^.next := nil;
  Result := NewNode;
end;

Функция CreateNode  (создать узел):
    вход:    новое слово, прочитанное из файла;
    выход: адрес нового узла, созданного в памяти.

возвращает адрес созданного узла

новое слово

alt: Добавление узла в начало списка 1)

description:
38

Добавление узла в начало списка

1) Установить ссылку нового узла на голову списка:

NewNode^.next := Head;

2) Установить новый узел как голову списка:

Head := NewNode;

procedure AddFirst ( var Head: PNode; NewNode: PNode );
begin
  NewNode^.next := Head;
  Head := NewNode;
end;

var

адрес головы меняется

alt: Добавление узла после заданного 1)

description:
39

Добавление узла после заданного

1) Установить ссылку нового узла на узел, следующий за p:

NewNode^.next = p^.next;

2) Установить ссылку узла p на новый узел:

p^.next = NewNode;

procedure AddAfter ( p, NewNode: PNode );
begin
  NewNode^.next := p^.next;
  p^.next := NewNode;
end;

alt: Задача: сделать что-нибудь хорошее с каждым элементом списка

description:
40

Задача:
    сделать что-нибудь хорошее с каждым элементом списка.

Алгоритм:
установить вспомогательный указатель q на голову списка;
если указатель q  равен nil (дошли до конца списка), то стоп;
выполнить действие над узлом с адресом q ;
перейти к следующему узлу, q^.next.

Проход по списку

var q: PNode;
...
q := Head;  // начали с головы
while q <> nil do begin // пока не дошли до конца
  ...                   // делаем что-то хорошее с q
  q := q^.next;         // переходим к следующему
end;

alt: Добавление узла в конец списка

description:
41

Добавление узла в конец списка

Задача:  добавить новый узел в конец списка.
Алгоритм:
найти последний узел q, такой что q^.next  равен nil;
добавить узел после узла с адресом q  (процедура AddAfter).
Особый случай: добавление в пустой список.

procedure AddLast ( var Head: PNode; NewNode: PNode );
var q: PNode;
begin
  if Head = nil then
    AddFirst ( Head, NewNode )
  else begin
    q := Head;
    while q^.next <> nil do
      q := q^.next;
    AddAfter ( q, NewNode );
  end;
end;

особый случай – добавление в пустой список

ищем последний узел

добавить узел после узла q

alt: Проблема: нужно знать адрес предыдущего узла, а идти назад нельзя!

description:
42

Проблема:     нужно знать адрес предыдущего узла, а идти назад нельзя!
Решение: найти предыдущий узел q (проход с начала списка).

Добавление узла перед заданным

procedure AddBefore(var Head: PNode; p, NewNode: PNode);
var q: PNode;
begin
  q := Head;
  if p = Head then
    AddFirst ( Head, NewNode )
  else begin
    while (q <> nil)  and  (q^.next <> p) do
      q := q^.next;
    if q <> nil then AddAfter ( q, NewNode );
  end;
end;

в начало списка

ищем узел, следующий за которым – узел p

добавить узел после узла q

alt: Добавление узла перед заданным (II)

description:
43

Добавление узла перед заданным (II)

Задача: вставить узел перед заданным без поиска предыдущего.
Алгоритм:
поменять местами данные нового узла и узла p;

установить ссылку узла p на NewNode.

procedure AddBefore2 ( p, NewNode: PNode );
var temp: Node;
begin
  temp := p^; p^ := NewNode^;
  NewNode^ := temp;
  p^.next := NewNode;
end;

alt: Поиск слова в списке Задача: найти в списке заданное слово или определить, что его нет

description:
44

Поиск слова в списке

Задача: найти в списке заданное слово или определить, что его нет.
Функция Find:
вход:    слово (символьная строка);
выход: адрес узла, содержащего это слово или nil.
Алгоритм: проход по списку.

function Find(Head: PNode; NewWord: string): PNode;
var q: PNode;
begin
  q := Head;
  while (q <> nil) and (NewWord <> q^.word) do
    q := q^.next;
  Result := q;
end;

ищем это слово

результат – адрес узла или nil (нет такого)

while (q <> nil) and (NewWord <> q^.word) do
  q := q^.next;

пока не дошли до конца списка и слово не равно заданному

alt: Куда вставить новое слово? Задача: найти узел, перед которым нужно вставить, заданное слово, так чтобы в списке сохранился алфавитный порядок слов

description:
45

Куда вставить новое слово?

Задача: найти узел, перед которым нужно вставить, заданное слово, так чтобы в списке сохранился алфавитный порядок слов.
Функция FindPlace:
вход:    слово (символьная строка);
выход: адрес узла, перед которым нужно вставить это слово или         nil, если слово нужно вставить в конец списка.

function FindPlace(Head: PNode; NewWord: string): PNode;
var q: PNode;
begin
  q := Head;
  while (q <> nil) and (NewWord > q^.word) do
    q := q^.next;
  Result := q;
end;

>

слово NewWord стоит по алфавиту перед q^.word

alt: Удаление узла procedure DeleteNode ( var

description:
46

Удаление узла

procedure DeleteNode ( var Head: PNode; p: PNode );
var q: PNode;
begin
  if Head = p then
    Head := p^.next
  else begin
    q := Head;
    while (q <> nil) and (q^.next <> p) do
      q := q^.next;
    if q <> nil then q^.next := p^.next;
  end;
  Dispose(p);
end;

while (q <> nil) and (q^.next <> p) do
  q := q^.next;

if Head = p then
  Head := p^.next

Проблема: нужно знать адрес предыдущего узла q.

особый случай: удаляем первый узел

ищем узел, такой что q^.next = p

Dispose(p);

освобождение памяти

alt: Алфавитно-частотный словарь Алгоритм: открыть файл на чтение; прочитать очередное слово ( как? ) если файл закончился, то перейти к шагу 7; если слово найдено, увеличить…

description:
47

Алфавитно-частотный словарь

Алгоритм:
открыть файл на чтение;

прочитать очередное слово (как?)
если файл закончился, то перейти к шагу 7;
если слово найдено, увеличить счетчик (поле count);
если слова нет в списке, то
создать новый узел, заполнить поля (CreateNode);
найти узел, перед которым нужно вставить слово (FindPlace);
добавить узел (AddBefore);
перейти к шагу 2;
закрыть файл
вывести список слов, используя проход по списку.

var F: Text;
...
Assign(F, 'input.dat');
Reset ( F );

Close ( F );

alt: Как прочитать одно слово из файла? function

description:
48

Как прочитать одно слово из файла?

function GetWord ( F: Text ) : string;
var c: char;
begin
  Result := ''; { пустая строка }
  c := ' ';     { пробел – чтобы войти в цикл }
    { пропускаем спецсимволы и пробелы }
  while not eof(f) and (c <= ' ') do
    read(F, c);
    { читаем слово }
  while not eof(f) and (c > ' ') do begin
    Result := Result + c;
    read(F, c);
  end;
end;

Алгоритм:
пропускаем все спецсимволы и пробелы (с кодами <= 32)
читаем все символы до первого пробела или спецсимвола

alt: Полная программа type PNode = ^Node;

description:
49

Полная программа

type PNode = ^Node;
     Node = record ... end; { новые типы данных }
var Head: PNode;       { адрес головы списка }
    NewNode, q: PNode; { вспомогательные указатели }
    w: string;         { слово из файла }
    F: text;           { файловая переменная }
    count: integer;    { счетчик разных слов }
{ процедуры и функции }
begin
  Head := nil;
  Assign ( F, 'input.txt' );
  Reset ( F );
    { читаем слова из файла, строим список }
  Close ( F );
    { выводим список в другой файл }
end.

alt: Полная программа (II) { читаем слова из файла, строим список } while

description:
50

Полная программа (II)

{ читаем слова из файла, строим список }
while True do begin      { бесконечный цикл }
  w := GetWord ( F );    { читаем слово }
  if w = '' then break;  { слова закончились, выход }
  q := Find ( Head, w ); { ищем слово в списке }
  if q <> nil then       { нашли, увеличить счетчик }
    q^.count := q^.count + 1
  else begin          { не нашли, добавить в список }
    NewNode := CreateNode ( w );
    q := FindPlace ( Head, w );
    AddBefore ( Head, q, NewNode );
  end;
end;

alt: Полная программа (III) { выводим список в другой файл } q :=

description:
51

Полная программа (III)

{ выводим список в другой файл }
q := Head;     { проход с начала списка }
count := 0;    { обнулили счетчик слов }
Assign(F, 'output.txt');
Rewrite(F);
while q <> nil do begin  { пока не конец списка }
  count := count + 1;    { еще одно слово }
  writeln ( F, q^.word, ': ', q^.count );
  q := q^.next;          { перейти к следующему }
end;
writeln ( F, 'Найдено ',
              count, ' разных слов.' );
Close(F);

alt: PNode = ^Node; { указатель на узел }

description:
type PNode = ^Node;   { указатель на узел }
     Node = record    { структура узла }
       word: string[40]; { слово }
       count: integer;   { счетчик повторений }
       next: PNode;    { ссылка на следующий }
       prev: PNode;    { ссылка на предыдущий }
     end;

52

Двусвязные списки

Структура узла:

Адреса «головы» и «хвоста»:

var Head, Tail: PNode;
...
Head := nil; Tail := nil;

alt: Задания «4»: «Собрать» из этих функций программу для построения алфавитно-частотного словаря

description:
53

Задания

«4»: «Собрать» из этих функций программу для построения алфавитно-частотного словаря. В конце файла вывести общее количество разных слов (количество элементов списка).
«5»: То же самое, но использовать двусвязные списки.
«6»: То же самое, что и на «5», но вывести список слов в порядке убывания частоты, то есть, сначала те слова, которые встречаются чаще всего.

alt: Тема 5. Стеки, очереди, деки Динамические структуры данных (язык

description:
Тема 5. Стеки, очереди, деки

Динамические структуры данных(язык Паскаль)

alt: Стек Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца ( вершины стека )

description:
55

Стек

Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца (вершины стека). Stack = кипа, куча, стопка (англ.)
LIFO = Last In – First Out
«Кто последним вошел, тот первым вышел».
Операции со стеком:
добавить элемент на вершину (Push = втолкнуть);
снять элемент с вершины(Pop = вылететь со звуком).

alt: Пример задачи Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [] , {} и ()

description:
56

Пример задачи

Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы). Примеры:
        [()]{}   ][    [({)]}
Упрощенная задача: то же самое, но с одним видом скобок.
Решение: счетчик вложенности скобок. Последовательность правильная, если в конце счетчик равен нулю и при проходе не разу не становился отрицательным.

alt: Решение задачи со скобками Алгоритм: в начале стек пуст; в цикле просматриваем все символы строки по порядку; если очередной символ – открывающая скобка, заносим ее…

description:
57

Решение задачи со скобками

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

[   (   (   )   )   ]   {   }

alt: Реализация стека (массив) Структура-стек: const

description:
58

Реализация стека (массив)

Структура-стек:

const MAXSIZE = 100;
type Stack = record  { стек на 100 символов }
      data: array[1..MAXSIZE] of char;
      size: integer; { число элементов }
     end;

Добавление элемента:

procedure Push( var S: Stack; x: char);
begin
  if S.size = MAXSIZE then Exit;
  S.size := S.size + 1;
  S.data[S.size] := x;
end;

ошибка: переполнение стека

добавить элемент

alt: Реализация стека (массив) function

description:
59

Реализация стека (массив)

function Pop ( var S:Stack ): char;
begin
  if S.size = 0 then begin
    Result := char(255);
    Exit;
  end;
  Result := S.data[S.size];
  S.size := S.size - 1;
end;

Снятие элемента с вершины:

Пустой или нет?

function isEmpty ( S: Stack ): Boolean;
begin
  Result := (S.size = 0);
end;

ошибка: стек пуст

alt: Программа var br1, br2, expr: string; i, k: integer; upper: char; { то, что сняли со стека } error:

description:
60

Программа

var br1, br2, expr: string;
    i, k: integer;
    upper: char;    { то, что сняли со стека }
    error: Boolean; { признак ошибки }
    S: Stack;
begin
  br1 := '([{'; br2 := ')]}';
  S.size := 0;
  error := False;
  writeln('Введите выражение со скобками');
  readln(expr);
  ...  { здесь будет основной цикл обработки }
  if not error  and  isEmpty(S) then
       writeln('Выражение правильное.')
  else writeln('Выражение неправильное.')
end.

открывающие скобки

закрывающие скобки

alt: Обработка строки (основной цикл) for i:=1 to length(expr) do begin for k:=1 to 3 do begin if expr[i] = br1[k] then begin { откр

description:
61

Обработка строки (основной цикл)

 for i:=1 to length(expr)
 do begin
    for k:=1 to 3 do begin
      if expr[i] = br1[k] then begin { откр. скобка }
        Push(S, expr[i]); { втолкнуть в стек}
        break;
      end;
      if expr[i] = br2[k] then begin { закр. скобка }
        upper := Pop(S); { снять символ со стека }
        error := upper <> br1[k];
        break;
      end;
    end;
    if error then break;
  end;

цикл по всем символам строки expr

цикл по всем видам скобок

ошибка: стек пуст или не та скобка

была ошибка: дальше нет смысла проверять

alt: Реализация стека (список) Добавление элемента:

description:
62

Реализация стека (список)

Добавление элемента:

Структура узла:

type PNode = ^Node; { указатель на узел }
     Node = record
       data: char;  { данные }
       next: PNode; { указатель на след. элемент }
     end;

procedure Push( var Head: PNode; x: char);
var NewNode: PNode;
begin
  New(NewNode);          { выделить память }
  NewNode^.data := x;    { записать символ }
  NewNode^.next := Head; { сделать первым узлом }
  Head := NewNode;
end;

alt: Реализация стека (список) Снятие элемента с вершины: function

description:
63

Реализация стека (список)

Снятие элемента с вершины:

function Pop ( var Head: PNode ): char;
var q: PNode;
begin
  if Head = nil then begin { стек пуст }
    Result := char(255); { неиспользуемый символ }
    Exit;
  end;
  Result := Head^.data;  { взять верхний символ }
  q := Head;             { запомнить вершину }
  Head := Head^.next; { удалить вершину из стека }
  Dispose(q);            { удалить из памяти }
end;

q := Head;
Head := Head^.next;
Dispose(q);

alt: Реализация стека (список) Изменения в основной программе: var

description:
64

Реализация стека (список)

Изменения в основной программе:

var S: Stack;
...
S.size := 0;

var S: PNode;

S := nil;

Пустой или нет?

function isEmpty ( S: Stack ): Boolean;
begin
  Result := (S = nil);
end;

alt: Вычисление арифметических выражений a b + c d + 1 - /

description:
65

Вычисление арифметических выражений

a b + c d + 1 - /

Как вычислять автоматически:

Инфиксная запись
(знак операции между операндами)

(a + b) / (c + d – 1)

необходимы скобки!

Постфиксная запись (знак операции после операндов)

польская нотация,
Jan Łukasiewicz (1920)

скобки не нужны, можно однозначно вычислить!

Префиксная запись (знак операции до операндов)

/ + a b - + c d 1

обратная польская нотация,
F. L. Bauer and E. W. Dijkstra

a + b

a + b

c + d

c + d

c + d  -  1

c + d  -  1

description:
66

Запишите в постфиксной форме

(32*6-5)*(2*3+4)/(3+7*2)

(2*4+3*5)*(2*3+18/3*2)*(12-3)

(4-2*3)*(3-12/3/4)*(24-3*12)

alt: Вычисление выражений Постфиксная форма: a b + c d + 1 - /

description:
67

Вычисление выражений

Постфиксная форма:

a b  +  c   d   +   1   -   /

Алгоритм:
взять очередной элемент;
если это не знак операции, добавить его в стек;
если это знак операции, то
взять из стека два операнда;
выполнить операцию и записать результат в стек;
перейти к шагу 1.

a

b

a

a+b

c

a+b

d

c

a+b

c+d

a+b

1

c+d

a+b

c+d-1

a+b

X

X =

alt: Системный стек ( Windows – 1 Мб )

description:
68

Системный стек (Windows – 1 Мб)

Используется для
размещения локальных переменных;
хранения адресов возврата (по которым переходит программа после выполнения функции или процедуры);
передачи параметров в функции и процедуры;
временного хранения данных (в программах на языке Ассмеблер).

Переполнение стека (stack overflow):
слишком много локальных переменных(выход – использовать динамические массивы);
очень много рекурсивных вызовов функций и процедур (выход – переделать алгоритм так, чтобы уменьшить глубину рекурсии или отказаться от нее вообще).

alt: Очередь Очередь – это линейная структура данных, в которой добавление элементов возможно только с одного конца ( конца очереди ), а удаление элементов – только…

description:
69

Очередь

Очередь – это линейная структура данных, в которой добавление элементов возможно только с одного конца (конца очереди), а удаление элементов – только с другого конца (начала очереди).
FIFO = First In – First Out
«Кто первым вошел, тот первым вышел».
Операции с очередью:
добавить элемент в конец очереди (PushTail = втолкнуть в конец);
удалить элемент с начала очереди (Pop).

alt: Реализация очереди (массив) самый простой способ нужно заранее выделить массив; при выборке из очереди нужно сдвигать все элементы

description:
70

Реализация очереди (массив)

самый простой способ

нужно заранее выделить массив;
при выборке из очереди нужно сдвигать все элементы.

alt: Реализация очереди (кольцевой массив)

description:
71

Реализация очереди (кольцевой массив)

alt: Реализация очереди (кольцевой массив)

description:
72

Реализация очереди (кольцевой массив)

В очереди 1 элемент:

Очередь пуста:

Очередь полна:

Head = Tail + 1

размер массива

Head = Tail + 2

Head = Tail

alt: Реализация очереди (кольцевой массив) type

description:
73

Реализация очереди (кольцевой массив)

type Queue = record
       data: array[1..MAXSIZE] of integer;
       head, tail: integer;
     end;

Структура данных:

Добавление в очередь:

procedure PushTail( var Q: Queue; x: integer);
begin
  if Q.head = (Q.tail+1) mod MAXSIZE + 1     then Exit; { очередь полна, не добавить }
  Q.tail := Q.tail mod MAXSIZE + 1;
  Q.data[Q.tail] := x;
end;

замкнуть в кольцо

mod MAXSIZE

alt: Реализация очереди (кольцевой массив)

description:
74

Реализация очереди (кольцевой массив)

Выборка из очереди:

function Pop ( var S: Queue ): integer;
begin
  if Q.head = Q.tail mod MAXSIZE + 1 then begin
    Result := MaxInt;
    Exit;
  end;
  Result := Q.data[Q.head];
  Q.head := Q.head mod MAXSIZE + 1;
end;

очередь пуста

взять первый элемент

удалить его из очереди

максимальное целое число

alt: Реализация очереди (списки) type

description:
75

Реализация очереди (списки)

type PNode = ^Node;
     Node = record
       data: integer;
       next: PNode;
     end;

type Queue = record
       head, tail: PNode;
     end;

Структура узла:

Тип данных «очередь»:

alt: Реализация очереди (списки) procedure

description:
76

Реализация очереди (списки)

procedure PushTail( var Q: Queue; x: integer );
var NewNode: PNode;
begin
  New(NewNode);
  NewNode^.data := x;
  NewNode^.next := nil;
  if Q.tail <> nil then
    Q.tail^.next := NewNode;
  Q.tail := NewNode; { новый узел – в конец}
  if Q.head = nil then Q.head := Q.tail;
end;

Добавление элемента:

создаем новый узел

если в списке уже что-то было, добавляем в конец

если в списке ничего не было, …

alt: Реализация очереди (списки) function

description:
77

Реализация очереди (списки)

function Pop ( var S: Queue ): integer;
var top: PNode;
begin
  if Q.head = nil then begin
    Result := MaxInt;
    Exit;
  end;
  top := Q.head;
  Result := top^.data;
  Q.head := top^.next;
  if Q.head = nil then Q.tail := nil;
  Dispose(top);
end;

Выборка элемента:

если список пуст, …

запомнили первый элемент

если в списке ничего не осталось, …

освободить память

alt: Дек Дек ( deque = d ouble e nded que ue , очередь с двумя концами) – это линейная структура данных, в которой добавление и…

description:
78

Дек

Дек (deque = double ended queue, очередь с двумя концами) – это линейная структура данных, в которой добавление и удаление элементов возможно с обоих концов.

Операции с деком:
добавление элемента в начало (Push);
удаление элемента с начала (Pop);
добавление элемента в конец (PushTail);
удаление элемента с конца (PopTail).

Реализация:
кольцевой массив;
двусвязный список.

alt: Задания «4»: В файле input.dat находится список чисел (или слов)

description:
79

Задания

«4»: В файле input.dat находится список чисел (или слов). Переписать его в файл output.dat в обратном порядке.
«5»: Составить программу, которая вычисляет значение арифметического выражения, записанного в постфиксной форме, с помощью стека. Выражение правильное, допускаются только однозначные числа и знаки +, -, *, /.
«6»: То же самое, что и на «5», но допускаются многозначные числа.

alt: Тема 6. Деревья Динамические структуры данных (язык

description:
Тема 6. Деревья

Динамические структуры данных(язык Паскаль)

alt: 81 Деревья

description:
81

Деревья

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

description:
82

Деревья

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

корень

Какие структуры – не деревья?

alt: Деревья Предок узла x – это узел, из которого существует путь по стрелкам в узел x

description:
83

Деревья

Предок узла x – это узел, из которого существует путь по стрелкам в узел x.
Потомок узла x – это узел, в который существует путь по стрелкам из узла x.
Родитель узла x – это узел, из которого существует дуга непосредственно в узел x.

Сын узла x – это узел, в который существует дуга непосредственно из узла x.
Брат узла x (sibling) – это узел, у которого тот же родитель, что и у узла x.
Высота дерева – это наибольшее расстояние от корня до листа (количество дуг).

alt: Дерево – рекурсивная структура данных

description:
84

Дерево – рекурсивная структура данных

Рекурсивное определение:
Пустая структура – это дерево.
Дерево – это корень и несколько связанных с ним деревьев.

Двоичное (бинарное) дерево – это дерево, в котором каждый узел имеет не более двух сыновей.

Пустая структура – это двоичное дерево.
Двоичное дерево – это корень и два связанных с ним двоичных дерева (левое и правое поддеревья).

alt: Двоичные деревья Структура узла: type

description:
85

Двоичные деревья

Структура узла:

type PNode = ^Node;        { указатель на узел }
     Node = record
       data: integer;      { полезные данные }
       left, right: PNode; { ссылки на левого и                              правого сыновей }
     end;

Применение:
поиск данных в специально построенных деревьях(базы данных);
сортировка данных;
вычисление арифметических выражений;
кодирование (метод Хаффмана).

alt: Двоичные деревья поиска Слева от каждого узла находятся узлы с меньшими ключами, а справа – с бóльшими

description:
86

Двоичные деревья поиска

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

Ключ – это характеристика узла, по которой выполняется поиск (чаще всего – одно из полей структуры).

Как искать ключ, равный x:
если дерево пустое, ключ не найден;
если ключ узла равен x, то стоп.
если ключ узла меньше x, то искать x в левом поддереве;
если ключ узла больше x, то искать x в правом поддереве.

alt: Двоичные деревья поиска Поиск в массиве (N элементов):

description:
87

Двоичные деревья поиска

Поиск в массиве (N элементов):

При каждом сравнении отбрасывается 1 элемент.
Число сравнений – N.

Поиск по дереву (N элементов):

При каждом сравнении отбрасывается половина оставшихся элементов.
Число сравнений ~ log2N.

быстрый поиск

нужно заранее построить дерево;
желательно, чтобы дерево было минимальной высоты.

alt: Реализация алгоритма поиска { Функция

description:
88

Реализация алгоритма поиска

{ Функция Search – поиск по дереву
  Вход: Tree - адрес корня,
           x  - что ищем
  Выход: адрес узла или nil (не нашли) }
function Search(Tree: PNode; x: integer): PNode;
begin
  if Tree = nil then begin
    Result := nil;
    Exit;
  end;
  if x = Tree^.data then
     Result := Tree
  else
  if x < Tree^.data then
       Result := Search(Tree^.left, x)
  else Result := Search(Tree^.right, x);
end;

дерево пустое: ключ не нашли…

нашли, возвращаем адрес корня

искать в левом поддереве

искать в правом поддереве

alt: Как построить дерево поиска? {

description:
89

Как построить дерево поиска?

{ Процедура AddToTree – добавить элемент
  Вход: Tree - адрес корня,
          x  - что добавляем }
procedure AddToTree( var Tree: PNode; x: integer );
begin
  if Tree = nil then begin
    New(Tree);
    Tree^.data := x;
    Tree^.left := nil;
    Tree^.right := nil;
    Exit;
  end;
  if x < Tree^.data then
       AddToTree(Tree^.left, x)
  else AddToTree(Tree^.right, x);
end;

дерево пустое: создаем новый узел (корень)

адрес корня может измениться

добавляем к левому или правому поддереву

alt: Обход дерева Обход дерева – это перечисление всех узлов в определенном порядке

description:
90

Обход дерева

Обход дерева – это перечисление всех узлов в определенном порядке.

Обход ЛКП («левый – корень – правый»):

125

98

76

45

59

30

16

Обход ПКЛ («правый – корень – левый»):

Обход КЛП («корень – левый – правый»):

Обход ЛПК («левый – правый – корень»):

alt: Обход дерева – реализация { Процедура

description:
91

Обход дерева – реализация

{ Процедура LKP – обход дерева в порядке ЛКП
                (левый – корень – правый)
  Вход: Tree - адрес корня }
procedure LKP(Tree: PNode);
begin
  if Tree = nil then Exit;
  LKP(Tree^.left);
  write(' ', Tree^.data);
  LKP(Tree^.right);
end;

обход этой ветки закончен

обход левого поддерева

вывод данных корня

обход правого поддерева

alt: Разбор арифметических выражений a b + c d + 1 - /

description:
92

Разбор арифметических выражений

a b + c d + 1 - /

Как вычислять автоматически:

Инфиксная запись, обход ЛКП
(знак операции между операндами)

(a + b) / (c + d – 1)

необходимы скобки!

Постфиксная запись, ЛПК (знак операции после операндов)

a +  b / c  +  d  – 1

польская нотация,
Jan Łukasiewicz (1920)

скобки не нужны, можно однозначно вычислить!

Префиксная запись, КЛП (знак операции до операндов)

/ + a b - + c d 1

обратная польская нотация,
F. L. Bauer and E. W. Dijkstra

description:
93

Вычисление выражений

Постфиксная форма:

a b  +  c   d   +   1   -   /

Алгоритм:
взять очередной элемент;
если это не знак операции, добавить его в стек;
если это знак операции, то
взять из стека два операнда;
выполнить операцию и записать результат в стек;
перейти к шагу 1.

a

b

a

a+b

c

a+b

d

c

a+b

c+d

a+b

1

c+d

a+b

c+d-1

a+b

X

X =

alt: Вычисление выражений Задача: в символьной строке записано правильное арифметическое выражение, которое может содержать только однозначные числа и знаки операций +-*\

description:
94

Вычисление выражений

Задача: в символьной строке записано правильное арифметическое выражение, которое может содержать только однозначные числа и знаки операций +-*\. Вычислить это выражение.

Алгоритм:
ввести строку;
построить дерево;
вычислить выражение по дереву.

Ограничения:
ошибки не обрабатываем;
многозначные числа не разрешены;
дробные числа не разрешены;
скобки не разрешены.

alt: Построение дерева Алгоритм: если first=last (остался один символ – число), то создать новый узел и записать в него этот элемент; иначе

description:
95

Построение дерева

Алгоритм:
если first=last (остался один символ – число), то создать новый узел и записать в него этот элемент; иначе...
среди элементов от first до last включительно найти последнюю операцию (элемент с номером k);
создать новый узел (корень) и записать в него знак операции;
рекурсивно применить этот алгоритм два раза:
построить левое поддерево, разобрав выражение из элементов массива с номерами от first до k-1;
построить правое поддерево, разобрав выражение из элементов массива с номерами от k+1 до last.

5

+

7

*

6

-

3

*

2

first

last

k

k+1

k-1

alt: Как найти последнюю операцию? Порядок выполнения операций умножение и деление; сложение и вычитание

description:
96

Как найти последнюю операцию?

Порядок выполнения операций
умножение и деление;
сложение и вычитание.

5

+

7

*

6

-

3

*

2

Приоритет (старшинство) – число, определяющее последовательность выполнения операций: раньше выполняются операции с большим приоритетом:
умножение и деление (приоритет 2);
сложение и вычитание (приоритет 1).

alt: Приоритет операции { Функция Priority – приоритет операции

description:
97

Приоритет операции

{ Функция Priority – приоритет операции
  Вход:  символ операции
  Выход: приоритет или 100, если не операция }
function Priority ( c: char ): integer;
begin
  case ( c ) of
    '+', '-': Result := 1;
    '*', '/': Result := 2;
    else      Result := 100;
  end;
end;

сложение и вычитание: приоритет 1

умножение и деление: приоритет 2

это вообще не операция

alt: Номер последней операции { Функция

description:
98

Номер последней операции

{ Функция LastOperation – номер последней операции
  Вход:  строка, номера первого и последнего          символов рассматриваемой части
  Выход: номер символа - последней операции }
function LastOperation ( Expr: string;
                  first, last: integer): integer;
var MinPrt, i, k, prt: integer;
begin
  MinPrt := 100;
  for i:=first to last do begin
    prt := Priority ( Expr[i] );
    if prt <= MinPrt then begin
      MinPrt := prt;
      k := i;
    end;
  end;
  Result := k;
end;

проверяем все символы

вернуть номер символа

нашли операцию с минимальным приоритетом

alt: Построение дерева Структура узла type

description:
99

Построение дерева

Структура узла

type PNode = ^Node;
     Node = record
       data: char;
       left, right: PNode;
     end;

Создание узла для числа (без потомков)

function NumberNode(c: char): PNode;
begin
  New(Result);
  Result^.data := c;
  Result^.left := nil;
  Result^.right := nil;
end;

возвращает адрес созданного узла

один символ, число

alt: Построение дерева { Функция MakeTree – построение дерева

description:
100

Построение дерева

{ Функция MakeTree – построение дерева
  Вход:  строка, номера первого и последнего         символов рассматриваемой части
  Выход: адрес построенного дерева }
function MakeTree ( Expr: string;
                    first, last: integer): PNode;
var k: integer;
begin
 if first = last then begin
    Result := NumberNode ( Expr[first] );
    Exit;
 end;
 k := LastOperation ( Expr, first, last );
 New(Result);
 Result^.data  := Expr[k];
 Result^.left  := MakeTree ( Expr, first, k-1 );
 Result^.right := MakeTree ( Expr, k+1, last );
end;

осталось только число

новый узел: операция

alt: Вычисление выражения по дереву {

description:
101

Вычисление выражения по дереву

{ Функция CalcTree – вычисление по дереву
  Вход:  адрес дерева
  Выход: значение выражения                }
function CalcTree(Tree: PNode): integer;
var num1, num2: integer;
begin
  if Tree^.left = nil then begin
    Result := Ord(Tree^.data) - Ord('0');
    Exit;
  end;
 num1 := CalcTree(Tree^.left);
 num2 := CalcTree(Tree^.right);
 case Tree^.data  of
   '+': Result := num1+num2;
   '-': Result := num1-num2;
   '*': Result := num1*num2;
   '/': Result := num1 div num2;
   else Result := MaxInt;
 end;
end;

вернуть число, если это лист

вычисляем операнды (поддеревья)

выполняем операцию

некорректная операция

alt: Основная программа { Ввод и вычисление выражения с помощью дерева } program qq; var

description:
102

Основная программа

{ Ввод и вычисление выражения с помощью дерева }
program qq;
var Tree: PNode;
    Expr: string;
{ процедуры и функции }
begin
  write('Введите выражение > ');
  readln( Expr );
  Tree := MakeTree( Expr, 1, Length(Expr) );
  writeln(' = ', CalcTree(Tree) );
end.

alt: Дерево игры Задача. Перед двумя игроками лежат две кучки камней, в первой из которых 3, а во второй – 2 камня

description:
103

Дерево игры

Задача. Перед двумя игроками лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней.
       Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу.
       Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16.
       Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок?

description:
104

Дерево игры

3, 2

игрок 1

3, 6

27, 2

3, 18

3, 3

4, 2

12, 2

4, 6

5, 2

4, 3

9, 3

4, 3

36, 2

4, 18

15, 2

27, 3

игрок 1

игрок 2

игрок 2

9, 2

4, 3

4, 3

ключевой ход

выиграл игрок 1

alt: Задания «4»: «Собрать» программу для вычисления правильного арифметического выражения, включающего только однозначные числа и знаки операций +, -, * , /

description:
105

Задания

«4»: «Собрать» программу для вычисления правильного арифметического выражения, включающего только однозначные числа и знаки операций +, -, * , /.
«5»: То же самое, но допускаются также многозначные числа и скобки.
«6»: То же самое, что и на «5», но с обработкой ошибок (должно выводиться сообщение).

alt: Тема 7. Графы Динамические структуры данных (язык

description:
Тема 7. Графы

Динамические структуры данных(язык Паскаль)

alt: Определения Граф – это набор вершин (узлов) и соединяющих их ребер (дуг)

description:
107

Определения

Граф – это набор вершин (узлов) и соединяющих их ребер (дуг).

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

Да, без циклов!

alt: Определения Связный граф – это граф, в котором существует цепь между каждой парой вершин

description:
108

Определения

Связный граф – это граф, в котором существует цепь между каждой парой вершин.
k-cвязный граф – это граф, который можно разбить на k связных частей.

Полный граф – это граф, в котором проведены все возможные ребра (n вершин → n(n-1)/2 ребер).

alt: Описание графа Матрица смежности – это матрица, элемент

description:
109

Описание графа

Матрица смежности – это матрица, элемент M[i][j] которой равен 1, если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет.

0

1

0

1

0

1

0

1

0

1

1

0

1

2

3

4

5

1

2

3

4

5

0

1

0

1

1

1

2

3

4

5

1

2

3

4

5

Список смежности

2

3

4

1

4

5

2

5

2

4

1

2

3

4

5

2

3

4

4

5

5

1

2

3

4

5

alt: Матрица и список смежности 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1…

description:
110

Матрица и список смежности

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

alt: Построения графа по матрице смежности 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 2 3 4…

description:
111

Построения графа по матрице смежности

0

1

0

1

1

0

1

0

0

1

0

1

1

0

1

0

1

2

3

4

5

1

2

3

4

5

0

1

1

0

1

0

1

0

1

0

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

1

2

3

4

5

alt: Как обнаружить цепи и циклы? Задача: определить, существует ли цепь длины k из вершины i в вершину j (или цикл длиной k из вершины i…

description:
112

Как обнаружить цепи и циклы?

Задача: определить, существует ли цепь длины k из вершины i в вершину j (или цикл длиной k из вершины i в нее саму).

M2[i][j]=1, если  M[i][1]=1 и  M[1][j]=1

или

M[i][2]=1 и  M[2][j]=1

или

M[i][3]=1 и  M[3][j]=1

строка i

логическое умножение

столбец j

логическое сложение

0

1

0

1

0

0

1

0

1

1

0

1

2

3

4

1

2

3

4

M =

или

M[i][4]=1 и  M[4][j]=1

alt: Как обнаружить цепи и циклы? M2 =

description:
113

Как обнаружить цепи и циклы?

M2 = M  M

Логическое умножение матрицы на себя:

матрица путей длины 2

0

1

0

1

0

0

1

0

1

1

0

M2 =



0

1

0

1

0

0

1

0

1

1

0

=

0

1

0

1

1

0

1

0

0

1

0

1

2

3

4

1

2

3

4

M2[3][1] = 0·0 + 1·1 + 0·0 + 1·1 = 1

маршрут 3-2-1

маршрут 3-4-1

alt: Как обнаружить цепи и циклы? M3 =

description:
114

Как обнаружить цепи и циклы?

M3 = M2  M

Матрица путей длины 3:

0

1

0

1

0

0

1

0

1

1

0

M3 =



=

1

0

0

1

0

1

1

0

1

0

1

1

2

3

4

1

2

3

4

0

1

0

1

1

0

1

0

0

1

0

на главной диагонали – циклы!

0

1

0

1

0

0

1

0

1

1

0

M4 =



=

0

1

0

1

0

0

1

0

1

1

0

1

2

3

4

1

2

3

4

1

0

0

1

0

1

1

0

1

0

1

alt: Весовая матрица Весовая матрица – это матрица, элемент

description:
115

Весовая матрица

Весовая матрица – это матрица, элемент W[i,j] которой равен весу ребра из вершины i в вершину j (если оно есть), или равен ∞, если такого ребра нет.

0

7

3

5

∞

7

0

∞

4

8

3

∞

0

∞

5

4

∞

0

6

∞

8

6

0

1

2

3

4

5

1

2

3

4

5

0

7

3

5

∞

∞

0

∞

4

8

3

∞

0

∞

5

0

6

∞

8

∞

0

1

2

3

4

5

1

2

3

4

5

alt: Задача Прима-Краскала Задача: соединить

description:
116

Задача Прима-Краскала

Задача: соединить N городов телефонной сетью так, чтобы длина телефонных линий была минимальная.

Та же задача: дан связный граф с N вершинами, веса ребер заданы весовой матрицей W. Нужно найти набор ребер, соединяющий все вершины графа (остовное дерево) и имеющий наименьший вес.

0

7

3

5

∞

7

0

∞

4

8

3

∞

0

∞

5

4

∞

0

6

∞

8

6

0

1

2

3

4

5

1

2

3

4

5

alt: Жадный алгоритм Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее в данный момент

description:
117

Жадный алгоритм

Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее в данный момент.

Шаг в задаче Прима-Краскала – это выбор еще невыбранного ребра и добавление его к решению.

alt: Реализация алгоритма Прима-Краскала

description:
118

Реализация алгоритма Прима-Краскала

Проблема: как проверить, что 1) ребро не выбрано, и 2) ребро не образует цикла с выбранными ребрами.
Решение: присвоить каждой вершине свой цвет и перекрашивать вершины при добавлении ребра.

3

2

4

5

Алгоритм:
покрасить все вершины в разные цвета;
сделать N-1 раз в цикле:
выбрать ребро (i,j) минимальной длины из всех ребер, соединяющих вершины разного цвета;
перекрасить все вершины, имеющие цвет j, в цвет i.
вывести найденные ребра.

4

alt: Реализация алгоритма Прима-Краскала

description:
119

Реализация алгоритма Прима-Краскала

Структура «ребро»:

type rebro = record
       i, j: integer; { номера вершин }
     end;

const N = 5;
var W: array[1..N,1..N] of integer;
    Color: array[1..N] of integer;
    i, j, k, min, col_i, col_j: integer;
    Reb: array[1..N-1] of rebro;
begin
... 	 { здесь надо ввести матрицу W }
for i:=1 to N do { раскрасить в разные цвета }
  Color[i] := i;
... { основной алгоритм – заполнение массива Reb }
... { вывести найденные ребра (массив Reb)}
end.

Основная программа:

весовая матрица

цвета вершин

alt: Реализация алгоритма Прима-Краскала for k:=1 to

description:
120

Реализация алгоритма Прима-Краскала

for k:=1 to N-1 do begin
  min := MaxInt;
  for i:=1 to N do
    for j:=i+1 to N do
     if (Color[i] <> Color[j]) and
        (W[i,j] < min) then begin
    	 min := W[i,j];
  	 Reb[k].i := i;
       Reb[k].j := j;
       col_i := Color[i];
       col_j := Color[j];
     end;
  for i:=1 to N do
    if Color[i] = col_j then
       Color[i] := col_i;
end;

Основной алгоритм:

нужно выбрать всего N-1 ребер

цикл по всем парам вершин

учитываем только пары с разным цветом вершин

запоминаем ребро и цвета вершин

перекрашиваем  вершины цвета col_j

alt: Сложность алгоритма Основной цикл:

description:
121

Сложность алгоритма

Основной цикл:

O(N3)

for k:=1 to N-1 do begin
  ...
  for i:=1 to N do
    for j:=i+1 to N do
	...
end;

три вложенных цикла, в каждом число шагов <=N

растет не быстрее, чем N3

Требуемая память:

var W: array[1..N,1..N] of integer;
    Color: array[1..N] of integer;
    Reb: array[1..N-1] of rebro;

O(N2)

Количество операций:

alt: Кратчайшие пути (алгоритм Дейкстры)

description:
122

Кратчайшие пути (алгоритм Дейкстры)

Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти кратчайшие расстояния от заданного города до всех остальных городов.

Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных.

присвоить всем вершинам метку ∞;
среди нерассмотренных вершин найти вершину j с наименьшей меткой;
для каждой необработанной вершины i: если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние;
если остались необработанны вершины, перейти к шагу 2;
метка = минимальное расстояние.

Алгоритм Дейкстры (E.W. Dijkstra, 1959)

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

description:
123

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

alt: Реализация алгоритма Дейкстры Массивы: массив a , такой что a[i]=1 , если вершина уже рассмотрена, и a[i]=0 , если нет

description:
124

Реализация алгоритма Дейкстры

Массивы:
массив a, такой что a[i]=1, если вершина уже рассмотрена, и a[i]=0, если нет.
массив b, такой что b[i] – длина текущего кратчайшего пути из заданной вершины x в вершину i;
массив c, такой что c[i] – номер вершины, из которой нужно идти в вершину i в текущем кратчайшем пути.
Инициализация:
заполнить массив a нулями (вершины не обработаны);
записать в b[i] значение W[x][i];
заполнить массив c значением x;
записать a[x]=1.

1

0

0

7

9

∞

14

a

b

c

1

2

3

4

5

6

alt: Реализация алгоритма Дейкстры Основной цикл : если все вершины рассмотрены, то стоп

description:
125

Реализация алгоритма Дейкстры

Основной цикл:
если все вершины рассмотрены, то стоп.
среди всех нерассмотренных вершин (a[i]=0) найти вершину j, для которой b[i] – минимальное;
записать a[j]:=1;
для всех вершин k: если путь в вершину k через вершину j короче, чем найденный ранее кратчайший путь, запомнить его: записать b[k]:=b[j]+W[j,k] и c[k]=j.

1

0

0

7

9

22

∞

14

1

0

a

b

c

1

2

3

4

5

6

Шаг 1:

alt: Реализация алгоритма Дейкстры 1 0 0 7 9 20 ∞ 11 2 0 2 a b c 1 2 3 4 5 6

description:
126

Реализация алгоритма Дейкстры

1

0

0

7

9

20

∞

11

2

0

2

a

b

c

1

2

3

4

5

6

Шаг 2:

1

0

1

0

7

9

20

11

2

5

2

a

b

c

1

4

3

4

5

6

Шаг 3:

alt: Как вывести маршрут? 1 0 7 9 20 11 2 5 2 a b c 1 2 3 4 5 6

description:
127

Как вывести маршрут?

1

0

7

9

20

11

2

5

2

a

b

c

1

2

3

4

5

6

Результат работа алгоритма Дейкстры:

длины путей

Маршрут из вершины 0 в вершину 4:

4

0

5

2

5

2

0

Сложность алгоритма Дейкстры:

O(N2)

два вложенных цикла по N шагов

Вывод маршрута в вершину i (использование массива c):
установить z:=i;
пока c[i]<>x присвоить z:=c[z] и вывести z.

alt: Алгоритм Флойда-Уоршелла Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение

description:
128

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

Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов.

for  k: =1 to N
  for  i: = 1 to N
    for  j: = 1 to N
      if W[i,j]  >  W[i,k] + W[k,j]  then
           W[i,j] := W[i,k] + W[k,j];

Если из вершины i в вершину j короче ехать через вершину k, мы едем через вершину k!

alt: Алгоритм Флойда-Уоршелла Версия с запоминанием маршрута: for i:= 1 to

description:
129

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

Версия с запоминанием маршрута:

for  i:= 1 to N
  for  j := 1 to N
    c[i,j] := i;
...
for  k: =1 to N
  for  i: = 1 to N
    for  j: = 1 to N
      if W[i,j]  >  W[i,k] + W[k,j]  then begin
        W[i,j] := W[i,k] + W[k,j];
        c[i,j] := c[k,j];
      end;

i–ая строка строится так же, как массив c в алгоритме Дейкстры

в конце цикла c[i,j] – предпоследняя вершина в кратчайшем маршруте из вершины i в вершину j

c[i,j] := c[k,j];

O(N3)

alt: Задача коммивояжера Задача коммивояжера

description:
130

Задача коммивояжера

Задача коммивояжера. Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив по разу в неизвестном порядке города 2,3,...N, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Точные методы:
простой перебор;
метод ветвей и границ;
метод Литтла;
…
Приближенные методы:
метод случайных перестановок (Matlab);
генетические алгоритмы;
метод муравьиных колоний;
…

большое время счета для больших N

O(N!)

не гарантируется оптимальное решение

alt: Другие классические задачи Задача на минимум суммы

description:
131

Другие классические задачи

Задача на минимум суммы. Имеется N населенных пунктов, в каждом из которых живет pi школьников (i=1,...,N). Надо разместить школу в одном из них так, чтобы общее расстояние, проходимое всеми учениками по дороге в школу, было минимальным.
Задача о наибольшем потоке. Есть система труб, которые имеют соединения в N узлах. Один узел S является источником, еще один – стоком T. Известны пропускные способности каждой трубы. Надо найти наибольший поток от источника к стоку.
Задача о наибольшем паросочетании. Есть M мужчин и N женщин. Каждый мужчина указывает несколько (от 0 до N) женщин, на которых он согласен жениться. Каждая женщина указывает несколько мужчин (от 0 до M), за которых она согласна выйти замуж. Требуется заключить наибольшее количество моногамных браков.

title: Паскаль_ДинСтруктурыДанных.ppt


file_name: 2. Траектория, система отчета..pptx

alt: Самостоятельная работа Операции с векторами, проекции

description: Самостоятельная работаОперации с векторами, проекции

alt: Способы описания движения. Система отчета

description: Способы описания движения.Система отчета

description:
Цели и задачи:

Изучить понятия: тело отчета, радиус – вектор, система отчета, способы описания движения.

description:
Вопросы для повторения

Какие величины называются скалярными? (пример)
Какие величины называются векторными? (пример)
Как производится сложение векторов?
Как производится вычитание векторов?
Что называется проекцией вектора на ось?
Как вычислить модуль вектора по проекциям?

alt: Домашняя работа: Прочитать параграф 7

description:
Домашняя работа:

Прочитать параграф 7.

description:
О движении тела можно судить по движению всех его точек.

Что бы описать движение тела, нужно описать движение точки (рассчитывать положение точки любой момент времени, относительно тела отчета).

description:
1 способ: координатный.

Точка движется, значит, с течением времени, ее координаты меняются.
Так как координаты точки зависят от времени, то они являются функциями времени.

description:
2 способ: векторный.

При движении, с течением времени, радиус–вектор поворачивается и изменяет длину, т. е. радиус-вектор – это функция времени.

description:
Траектория – линия, по которой движется тело.

Прямая линия – прямолинейное движение.
Кривая линия – криволинейное движение.

description:
Система отчета – это совокупность следующих элементов:

Тело отчета – тело, относительно которого рассматривается движение;
Система координат;
Время.

alt: Задания на закрепление

description: Задания на закрепление

description:
Закрепление:

Что такое система координат, что в нее входит?
Какие есть способы описания движения? Охарактеризуйте их.
Что такое траектория движения?

title: Презентация, 10 класс, 2 урок


file_name: Математика 2А Величина - время.pptx

description:
секунда

минута

час

сутки

неделя

месяц

год

век

тысячелетие

60 секунд

60 минут

24 часа

Около 4 недели

7 суток

12 месяцев

100 лет

10 веков

title: Презентация к уроку математики. Занков. Тема: "Величина - время" 2 класс


file_name: Информатика 7 класс Подготовка к проекту. Презентация.pptx

alt: Тема урока: Программирование решений

description:
Тема урока:
Программирование решений. Подготовка к проекту

description:
Цель обучения

записывать алгоритм на языке программирования
записывать линейные и разветвляющиеся алгоритмы на языке программирования в визуальной среде (например, Lazarus)

alt: Критерии обучения умеет составлять блок-схемы на представленные задачи умеет правильно пояснить порядок действий, записанных в виде блок-схем умеет представлять условный оператор в виде блок-схемы

description:
Повторение

Алгоритм

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

description:
Повторение

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

Линейный алгоритм

description:
Повторение

Исполнитель - объект, который выполняет алгоритм.

Исполнитель

description:
Повторение

Команда – указание исполнителю выполнить отдельное действие

Команда

description:
Повторение

Как в блок-схемах обозначаются:

Начало и конец программ

Действие

Ввод и вывод данных

alt: Задание Составить алгоритм посадки дерева в виде блок схемы

alt: Возможное решение:

description: Возможное решение:

description: В жизни часто приходится принимать решение в зависимости от сложившейся обстановки.

description:
Задание

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

description:
Возможное решение:

Начало

На улице дождь?

Взять зонт и надеть плащ

Одеть легкую одежду

Выйти на улицу

Конец

Да

Нет

description: Условный (разветвляющийся) алгоритм – выполнение действия (или группы действий) в зависимости от истинности или ложности условия.

description:
Задание. Определить наибольшее из двух введенных чисел a и b.
Ответ представить в виде блок-схемы.

alt: Возможное решение:

description: Возможное решение:

alt: Рефлексия

description: Рефлексия

description:
Домашнее задание.
Определить модуль числа.
Ответ представить в виде блок-схемы.


description: «Использование цифровых образовательных систем в обучении школьников»

alt: Цифровая школа – это особый вид образовательного учреждения, которое осознанно и эффективно использует цифровое оборудование, программное обеспечение в образовательном процессе и тем самым повышает конкурентную…

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

description:
Современные цифровые технологии – это:
- Технология совместных экспериментальных исследований учителя и ученика.
- Технология «Виртуальная реальность».
- Технология «Панорамных изображений».
- Технология «3D моделирование».
- Технология «Образовательная робототехника».
- Технология МСИ (использования малых средств информатизации).
- Мультимедийный учебный контент.
- Интерактивный электронный контент.

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

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

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

alt: Данная технология позволяет: 1) познакомить обучающихся с процессом познания; 2) вооружить элементами знаний общего подхода, что важно для дальнейшего обучения и жизни; 3) вовлечь обучающихся…

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

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


file_name: Загадки.pptx

description:
«ОТГАДАЙ ЗАГАДКИ»

Объясните, как вы догадались, какие слова помогли найти отгадки?

description:
Под сугробом он растёт.
Снеговую воду пьёт

Он и мачеха, и мать,
Как цветочек этот звать?

ПОДСНЕЖНИК

МАТЬ-И-МАЧЕХА

description:
Прячет цветок сладкий.
И в названье мёд таится
Узнаёте?

Если я отправлюсь в путь,
Он посмотрит на меня
И шепнёт мне: «Не забудь
Про родимые края!»
Голубой цветочек хрупкий,
Он зовётся …

НЕЗАБУДКОЙ

МЕДУНИЦА

description:
В белой шапке стоит дед,
Если дунешь – шапки нет!

На каком цветке гадают
Лепесточки обрывают?

НА РОМАШКЕ

ОДУВАНЧИК

description:
Вдоль дороги у межи
В золотистой спелой ржи,
Словно синий глазок,
Смотрит в небо…

Золотист, красив на вид –
Для коровок ядовит

ЗВЕРОБОЙ

ВАСИЛЁК

alt: Малиновые свечки Зажёг он возле речки

description:
Малиновые свечки
Зажёг он возле речки

Хоть она и не печь,
Руку может нам обжечь

ИВАН-ЧАЙ

КРАПИВА

alt: Нет свежее аромата И приятней, чем у …

description:
Нет свежее аромата
И приятней, чем у …

Шарик розовый пушистый
Дарит пчёлам мёд душистый

КЛЕВЕР

МЯТЫ

description:
Она похожа на рябинку,
Соцветья  - жёлтые корзинки

В ельнике цветут густом,
Звенит белым бубенцом

ПИЖМА

ЛАНДЫШ

description:
Пышным розовым  султаном
Украшает он поляну

ПОДОРОЖНИК

ИВАН-ЧАЙ

Лекарь вырос у дороги –
Он больные лечит ноги

alt: Первым вылез из земли на проталинке!

description:
Первым вылез из земли на проталинке!
Он мороза не боится,
Хоть и маленький.
Стоит в белой шапчонке
И зелёной распашонке.

ПОДСНЕЖНИК

На глиняных откосах,
В оврагах, вдоль дорог
Появился первым
Жёлтый огонёк.

МАТЬ-И-МАЧЕХА

description:
Не успел сойти белый снег,
Появился ранний, смелый побег,
А цветочки у него все разные:
Фиолетовые, синие, голубые, красные…
Они меняют окраску, следуя моде,
Красуются при холодной погоде,
Цветы ароматные -
                       содержат много нектара,
Цветут в садах, очень любят дубравы.

МЕДУНИЦА

Полезен, приятен и ароматен чай,
Конечно, не с ватой, а с…

МЯТОЙ

description:
Спит в землице круглый год,
Лишь к весне она встаёт:
На невысоком стебелёчке,
В кружевном листочке,
Соцветие – сиреневые цветочки,
Отцветают быстро, виднеются стручочки,
А под землёй клубенёк,
Жёлтый, сочный огонёк.

ХОХЛАТКА

До поздней осени на нас
бросает взгляды смелые
Её весёлый жёлтый глаз через ресницы белые…

РОМАШКА

description:
Он родился в майский день,
И лес его хранит.
Мне кажется, его задень –
Он тихо зазвенит,
И этот звон услышит луг,
И птицы, и цветы.
Давай послушаем, а вдруг
Услышим я и ты.

ЛАНДЫШ

КАЛЕНДУЛА

Семена, как коготки,
Жёлто-красные цветки.
От горла помогают,
Кто же их не знает

description:
На зелёной крепкой ножке
Вырос шарик у дорожки

Стоят в лугах сестрички —
Золотой глазок,
Белые реснички.

ОДУВАНЧИК

ОДУВАНЧИК

alt: Рос шар бел, Дунул ветер – и шар улетел

description:
Рос шар бел,
Дунул ветер – и шар улетел

В майский день в тени лесной
Он раскрыл цветочек свой,
Яркий и душистый, бело-серебристый

ОДУВАНЧИК

ЛАНДЫШ

alt: Молодцы!

description: Молодцы!

title: Презентация "Загадки - лекарственные растения"


file_name: А,С,ПУШКИН 2 класс.ppt

alt: Урок литературного чтения во 2 классе

description:
Урок литературного чтения
во 2 классе
Подготовила :Фастова Е.С.

alt: Девиз урока Думать- коллективно

description:
Девиз урока

Думать- коллективно.
Решать- оперативно.
Отвечать- доказательно.
Работать- старательно.

alt: Тема урока: Пушкин «У лукоморья дуб зелёный»

description:
Цель:

Познакомиться с вступлением к поэме…
«Руслан и Людмила»

alt: Сказка о попе и его работнике Балде

description: Сказка о попе и его работнике Балде

alt: Сказка о золотом петушке

description: Сказка о золотом петушке

alt: Сказка о рыбаке рыбке

description: Сказка о рыбаке  рыбке

alt: Сказка о мёртвой царевне и о 7 богатырях

alt: Сказка о царе Салтане

description: Сказка о царе Салтане

alt: Сказка о медведихе

description: Сказка о медведихе

description:
Эту поэму Пушкин написал
в 1820 году, когда ему было
20 лет.

alt: Словарная работа

description: Словарная работа

alt: Морской залив. Лукоморье –

description:
сохнуть, изводить себя, страдать.

в старину: воин, богатырь.

такой изгиб морского берега , когда часть
моря вдается в сушу. Морской залив.

Лукоморье –

На неведомых дорожках –

на незнакомых дорожках.

Дол –

долина.

Витязь –

Чредой –

чередой, по очереди.

Дядька –

в старину: слуга-воспитатель
при мальчике в дворянской семье.

Мимоходом –

по пути, проходя мимо.

Пленяет –

берет в плен.

Чахнуть –

alt: Где стоял дуб?

description: Где стоял дуб?

alt: Какие значения может иметь слово «заводить»?

alt: Кто из героев поёт, рассказывает?

description: Кто из героев поёт, рассказывает?

alt: Кому верно служит бурый волк?

description: Кому верно служит бурый волк?

alt: Кто выходит из морских волн?

description: Кто выходит из морских волн?

alt: Что стоит без окон, без дверей?

description: Что стоит без окон, без дверей?

alt: Кто сидит на ветвях?

description: Кто сидит на ветвях?

alt: Кто над златом чахнет?

description: Кто над златом чахнет?

alt: Домашнее задание Выучить 12 строк, нарисовать иллюстрацию

description:
Итог урока
С каким произведением познакомились?
Чем оно вас заинтересовало?

intro: Презентация для урока литературное чтение А.С. Пушкин "У лукоморья дуб зеленый!"

русская литература

group: Дисциплины

title: Презентация А.С.ПУШКИН для 2 класса


file_name: Молярная масса.pptx

alt: Молярная масса 8 класс

description:
Молярная масса

8 класс

alt: Ответьте на вопрос: «Что нужно сделать, чтобы отмерить один моль вещества, например воды?»

description:
Заполните пропуски.
Молярная масса – это физическая величина, которая показывает ….., обозначается …, численно равна ….., измеряется в ….

description:
Заполните таблицу, вставив пропущенные числа и единицы.

Количество вещества

Молярная масса

Масса

n(H2O) = 1 моль

n (Ca) = 0,5 кмоль

m (CO2) == 44 мг

description:
Сколько молекул содержится в 180 мг воды?

2.   Сколько молекул содержится в 704 г сахара С12Р22О11?

3.   Найдите массу 24*1023 молекул хлора?

4.   Вычислите массу 3*1023 молекул озона.

5.   Вычислите массу 48*1023молекул азота.

title: презентация молярная масса


file_name: пп в крим сит.pptx

alt: Опасные ситуации криминального характера

description:
Что же это такое?

Криминальная ситуация — это система сложившихся условий и обстоятельств, в которых реализуется преступный замысел субъекта.

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

alt: В зависимости от этапов преступной деятельности можно выделить три основных вида криминальных ситуаций: ситуации, предшествующие преступлению (предкриминальные) ситуации совершения преступления ( собственно криминальные) ситуации, сложившиеся…

description:
В зависимости от этапов преступной деятельности можно выделить три основных вида криминальных ситуаций:

ситуации, предшествующие преступлению (предкриминальные)
ситуации совершения преступления (собственно криминальные)
ситуации, сложившиеся после совершения преступления (посткриминальные)

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

Как не оказаться жертвой преступления?

4

alt: На какой машине ты согласишься прокатиться с незнакомцем – на «БМВ», «Вольво», «Феррари»?

description: На какой машине ты согласишься прокатиться с незнакомцем – на «БМВ»,«Вольво», «Феррари»?

alt: СИТУАЦИЯ Заголовок презентации 6

description:
СИТУАЦИЯ

Заголовок презентации

6

Вы едете в автобусе. Рядом с Вами оказался чей-то пакет. Как
Вы поступите?

description:
ВОПРОСЫ:

Какие способы самозащиты от нападения вы знаете?
Какие приметы нападающего вы можете запомнить и описать при подачи заявления в полицию?
Почему козлят из «волк и 7 козлят» съели?- Была открыта дверь- Не было дверного глазка - Козлята глупые- Они не прочли учебник ОБЖ
Как следует отнестись к предложению к предложению незнакомого водителя подвести на машине?- Согласиться и сесть в машину- Посоветовать друзьям- Согласиться, если водитель внушает доверие- Не принимать предложение

оловок презентации

7

title: Правила поведения в ситуациях криминального характера


file_name: Лекция 21. Информационные технологии как инструмент управленческих решений.pptx

description:
Особенности ИТ в организациях различного типа

Информационные технологии как инструмент управленческих решений

1

description:
2

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

description:
3

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

description:
4

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

description:
5

Стратегический уровень ориентирован на руководителей высшего ранга.

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

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

description:
6

Существуют три тенденции их использования:
За основу первой принято положение, что сначала формулируются цели и стратегии их достижения, а только затем автоматизированная информационная технология приспосабливается к выработанной заранее стратегии;
Вторая тенденция основана на том, что организация использует стратегическую информационную систему при формулировании целей и стратегическом планировании;
За основу третьей тенденции принята методология синтеза двух предыдущих тенденций — встраивания стратегической информационной системы в существующую информационную технологию с совмещением выработки концепции развития организации в управленческом звене фирмы

description:
7

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

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

description:
8

Оперативный (операционный) уровень принятия решений является основой всех автоматизированных информационных технологий

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

description:
Особенности ИТ в организациях различного типа

9

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

description:
11

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


file_name: Презентация изобретения.ppt

alt: Alexander Popov Benjamin Franklin

description:
Alexander Popov

Benjamin Franklin

Galileo Galilei

James Watt

Percy LeBaron Spencer

Who invented the light bulb?

Leonardo da Vinci

Nikola Tesla

Thomas Edison

alt: Which thing was invented by Christian

description: Which thing was invented by Christian Huygens(1675)

alt: What parts do not fit the dishwasher?

description: What parts do not fit the dishwasher?

alt: What was not invented in the 19th century?

alt: What device was invented by Akito

description: What device was invented by Akito  Morita?

alt: Who invented the first TV receiver?

description: Who invented the first TV receiver?

alt: Who invented tetris?

description: Who invented tetris?

alt: What was invented by Lancelot de

description: What was invented by Lancelot de Mole?

alt: Who invented the Morse code

description: Who invented the Morse code

alt: Which country was invented nuclear weapons in?

alt: Which thing does not belong to the car

description: Which thing does not belong to the car

intro: Данную викторину можно использовать при изучении темы "Изобретения"

title: Викторина по теме "Изобретения"


file_name: ..БОГОРОДИЦЕ ДЕВО РАДУЙСЯ .ppt

description:
Образ матери в музыке, поэзии, изобразительном искусстве

«Радуйся, Мария!»
«Богородице Дево, радуйся!»

alt: Пусть ей вечно солнце рукоплещет!

description: Пусть ей вечно солнце рукоплещет!Так она и будет жить в векахСамая прекрасная из женщин,Женщина с ребенком на руках!С. Островский

description:
«Мама»

    1. Рано утром просыпаюсь я от глаз твоих,
       Мне они заменят солнце.
        Мир, поверь мне, существует лишь для нас двоих
       Солнышко в тебе смеётся.
ПРИПЕВ:
Мама, без ума тебя люблю я,
Мама, и тебя боготворю я,
Мама, я без взгляда твоего , как птица без крыла,
Птица без крыла!Мама, знаешь нет тебя роднее
Мама, обними меня скорее
Мама, дай погреться мама,
Возле рук твоих как – будто у огня.

    2. Пусть невзгоды и печали будут вдалеке.
        А поближе будет счастье.
        Мы с тобой не можем жить в печали и тоске
        И прогоним прочь ненастье!

alt: МАМА главное слово в каждой судьбе

description:
МАМА главное слово в каждой судьбе

      Кто пpишёл ко мне с yтpа?Мамочка.Кто сказал: "Вставать поpа"?Мамочка.Кашy кто yспел сваpить?Мамочка.Чаю - в пиалy налить?Мамочка.
      Кто косички мне заплёл?Мамочка.Целый дом один подмёл?Мамочка.Кто цветов в садy наpвал?Мамочка.Кто меня поцеловал?Мамочка.Кто pебячий любит смех?Мамочка.Кто на свете лyчше всех?Мамочка.

title: презентация к уроку музыки 3 класс по теме: Богородице Дево радуйся"


file_name: герои отечества.pptx

alt: Имя великого русского полководца

description:
Имя великого русского полководца Михаила Илларионовича Голенищева-Кутузова неотделимо от Отечественной войны 1812 года. Именно в этот завершающий период своей жизни он полностью проявил себя как стратег, государственный деятель, возглавивший народную войну
против иноземных захватчиков.Военная деятельность Кутузова началась в 1765 году. С 1770 года участвовал в походах против турок в армии фельдмаршала Румянцева. В июле 1774 года при штурме деревни Шумы близ Алушты Кутузов был ранен в голову, в результате правый глаз почти перестал видеть. В 1776 году служил в Крыму под командованием А. В. Суворова. Очаков, Аккерман, Каушаны, Бендеры и, наконец, штурм Измаила, после которого Суворов писал о нем: «...он шел на моем левом фланге,
 но был моей правой рукой».В 1793 году Кутузов — посол в Константинополе, затем командующий войсками и флотом в Финляндии, литовский генерал-губернатор, генерал-губернатор Петербурга. В 1805 году командовал русскими войсками в войне против Наполеона в союзе с австрийскими войсками. В 1811 — главнокомандующий в Бессарабии. Бессмертен подвиг Кутузова в Отечественной войне 1812 года, о котором Пушкин писал:... Когда народной веры гласВоззвал к святой твоей седине « Иди, спасай». Ты встал — и спас...

М. И. Голенищев-Кутузов,
1845-1813, генерал-фельдмаршал

description:
«Багратион — лучший генерал русской армии», — говорил Наполеон.Участник штурма Очакова, Варшавы, Багратион проделал с Суворовым весь Итальянский поход, был его правой рукой. Взятие Брешин, Бергамо, Лекко, Тортоны, Турина и Милана, битва при Треббии, при Нови — везде Багратион находился в самых трудных и решающих местах. Знаменитый Швейцарский поход Суворова принес славу и Багратиону, проявившему героизм, хладнокровие, волю к победе. 4 ноября 1805 года у деревни Шенграбен пятитысячный отряд Багратиона задержал тридцать тысяч французов, чтобы дать возможность отойти корпусу Кутузова. Выполнив задачу, Багратион, считавшийся обреченным, прорвал ряды противника и с половиной оставшихся солдат присоединился к русской армии. Отличился Багратион и в кампанию 1806—1807 годов взятием Прейсиш-Эйлау и победой у Анкендорфа.Войну 1812 года Багратион начал главнокомандующим 2-й Западной армией. После умело проведенного отхода, нанеся ряд поражений французам, Багратион соединился с армией Барклая.26 августа на Бородинском поле Багратион совершил свой последний подвиг. На левом фланге русской армии у деревни Семеновской были построены земляные укрепления: Багратионовы флеши. На них обрушился главный удар наполеоновской армии. Даву, Ней, Жюно ничего не смогли сделать, чтобы сломить отпор русских полков. Рукопашный бой шел с шести часов утра до полудня, после чего Багратион отдал приказ перейти в контратаку. Спустя несколько минут он был ранен осколком ядра, раздробившим ногу.Через три недели Багратион скончался.

П. И. Багратион,
1766-1812, генерал от инфантерии

description:
Военную службу начал в 15 лет унтер-офицером. В 1788—1789 годах участвовал в штурме Очакова, в бою под Каушанами, во взятии Аккермана и Бендер. В 1790-х годах сражался в Финляндии и Польше. В 1805—1807 годах Барклай отличился в войне против Наполеона под Пултуском и Прейсиш-Эйлау. Во время русско-шведской войны 1808—1809 годов командовал корпусом в Финляндии, а затем был главнокомандующим всеми русскими войсками в Финляндии. С января 1810 года — военный министр. С войны 1812 года — главнокомандующий 1-й Западной армией. 600-тысячной армии Наполеона противостояли 200 тысяч русских войск на границе. Барклай избрал единственно возможную тактику. Отступая и умело маневрируя, он стремился сконцентрировать русские войска, не дать Наполеону разбить их поодиночке. Эта стратегия не была понята патриотически настроенной армией. Не пользовавшийся популярностью полководец с иностранной фамилией, Барклай де Толли передал командование М. И. Кутузову, оставшись во главе 1-й армии. Руководя правым флангом при Бородине, Барклай проявил редкостную храбрость. После смерти Кутузова в 1813 году вновь был назначен главнокомандующим. В сражениях под Бауценом, Кульмом, Лейпцигом, Бриенном, Бар-Сюр-Об, Фершампенуазе показал себя талантливым полководцем. Был произведен в фельдмаршалы, получил княжеский титул. Умер в 1818 году на 57-м году жизни.

М. Б. Барклай де Толли, 1761-1818

description:
Начал службу в 1792 году унтер-офицером лейб-гвардии конного полка, в 1783 году произведен в корнеты. В 1801 году Васильчиков уже генерал-майор и генерал-адъютант. В 1803 году был командиром Ахтырского гусарского полка. В 1807 году участвовал в сражениях при Сороцке и Пултуске.В начале войны 1812 года был в арьергарде 2-й армии Багратиона до соединения с 1-й. Участвовал в Бородинском сражении, был ранен. Произведен в генерал-лейтенанты и назначен командиром 4-го кавалерийского корпуса. Участвовал в сражениях под Тарутином и Вязьмой. В 1813 году участвовал в боях под Бауценом, Кайзерсвальде, Кацбахом и Лейпцигом. Преследовал французов до самого Рейна. В 1814 году отличился в сражениях при Бриенне, Монмирале, Краоне, Лаоне и Фершампенуазе.После войны командовал отдельным гвардейским корпусом. В 1823 году произведен в генералы от кавалерии. Впоследствии был председателем Государственного совета и кабинета министров.

И. В. Васильчиков,
1777-1847, генерал от кавалерии

description:
П. X. Витгенштейн начал службу в лейб-гвардии Семеновском полку, в 1793 году перешел в армию в Украинский легкоконный полк. Участвовал в военных действиях в Польше и на Кавказе.В кампании 1805 года командовал кавалерийским отрядом под командованием сначала Багратиона, а затем Милорадовича. В 1806—1807 годах сражался в Молдавии против турок и в Восточной Пруссии против французов. В начале войны 1812 года Витгенштейн командовал 1-м пехотным корпусом на правом фланге армии Барклая. 19 июля у деревни Клястицы разгромил войска маршала Удино. В дальнейшем войска Витгенштейна заняли Полоцк, нанесли французам поражение под Чашниками, заняли Витебск. После перехода границ России, преследуя французов, войска Витгенштейна заняли Кенигсберг и 27 февраля 1813 года вступили в Берлин.После смерти Кутузова Витгенштейн недолгое время был главнокомандующим союзными русскими и прусскими войсками. Последнее сражение Витгенштейна в войне с французами произошло 15 февраля 1814 года в Бар-Сюр-Об и завершилось победой.

П. X. Витгенштейн, 1768-1843, генерал от инфантерии

description:
Волконский начал службу в 1806 году поручиком кавалергардского полка. Тогда же началась боевая жизнь в качестве адъютанта Остермана-Толстого.Участвовал в сражениях под Прейсиш-Эйлау и Фридландом. В 1810 году волонтером участвовал в боях на Дунае против турок под Батином, Рущуком и Шумлою, в 1810 году состоял при Кутузове — главнокомандующим Дунайской армией. В начале Отечественной войны в чине ротмистра служил в конном отряде генерала Винцингенроде. Во время отступления великой армии в чине полковника командовал отрядом из трех сотен казаков, вел партизанскую войну. В 1813—1814 годах за сражения под Люценом, Лейпцигом, Краоном вместе с боевыми наградами получил чин генерал-майора. В 1819 году вступил в «Союз благоденствия», а затем стал одним из руководителей Южного общества. После подавления восстания декабристов Волконский был арестован, приговорен к смертной казни, замененной двадцатилетней каторгой. В 1856 году после 30 лет тюрьмы и поселения вернулся в Европейскую Россию.

С. Г. Волконский,
1788-1865, генерал-майор

alt: Военное образование Голицын получил в г

description:
Военное образование Голицын получил в г. Страсбурге в военной академии, а затем продолжил в Париже. В 1794 году под командованием Суворова воевал в Польше, участвовал в штурме предместья Варшавы — Праги. В кампанию 1806—1807 годов командовал 4-й дивизией. Участвовал в сражениях при Голымине, Прейсиш-Эйлау, под Будштадтом, Фридландом. Участвовал в русско-шведской войне 1808—1809 годов. В 1812 году командовал кирасирским корпусом. Кирасиры Голицына отличились в сражениях при Бородине и Красном.После изгнания французов из пределов России Голицын во главе корпуса участвовал в сражениях под Дрезденом, Кульмом, Лейпцигом, Бриенном, Фершампенуазе, при взятии Парижа.По окончании войны Голицын в 1820 году был назначен московским генерал-губернатором и многое сделал для улучшения состояния больниц, приютов, богаделен. Пользовался всеобщим уважением и любовью.

Д. В. Голицын, 1771-1844,
генерал от кавалерии

description:
Андрей Иванович Горчаков начал свою службу блестяще — в девятнадцать лет был уже полковником. Племянник А. В. Суворова, Горчаков был послан Павлом I в Кончанское, где жил ссыльный фельдмаршал, которого император вызвал в Петербург. В чине генерал-майора в 1799 году он участвует в знаменитом Итальянском походе Суворова. Здесь, в битве при Тидоне, 20-летний генерал принял «боевое крещение». Затем служил под начальством Багратиона, сражался при Нови, отличился при взятии Сен-Готардского перевала. В кампанию 1807 года под Гейльсбергом генерал-лейтенант Горчаков героически командовал дивизией, а затем всеми русскими войсками вместо заболевшего Бенигсена. Покрыл себя славой под Фридландом. В 1812 году под начальством своего друга Багратиона оборонял Шевардинский редут с 11-ю тысячами против 35—40 тысяч французов.

А. И. Горчаков,
1779-1855, генерал-лейтенант

description:
«Я был рожден для рокового 1812 года», — писал в автобиографии прославленный поэт-партизан. Денис Васильевич Давыдов, сын командира Полтавского конного полка, в семнадцать лет начал военную службу эстандарт-юнкером в кавалергардском полку, а затем в армейском Белорусском гусарском полку. В 1806 году ротмистр Давыдов снова в гвардии. В кампанию 1807 года — адъютант Багратиона. В 1808—1809 годах участвовал в войне со Швецией, служил в отряде Кутузова. В качестве адъютанта Багратиона воевал на Дунае против турок.«Звездный час» Давыдова настал в Отечественную войну 1812 года. Будучи подполковником Ахтырского гусарского полка предложил Багратиону проект партизанской войны. Проект был одобрен Кутузовым, и 25 августа, накануне Бородинской битвы, Давыдов во главе отряда из пятидесяти гусар и восьмидесяти казаков направился в тыл врага. Успешные действия отряда Давыдова послужили примером для создания других партизанских отрядов. Во время отступления французов действия партизан приобрели еще более широкий размах. Возле села Ляхова отряды Давыдова, Сеславина, Фигнера и Орлова-Денисова окружили, атаковали и взяли в плен двухтысячную колонну французов во главе с генералом Ожеро. После изгнания французов из пределов России Давыдов в чине полковника сражался под Калишем, Бауценом и Лейпцигом. В начале 1814 года командовал Ахтырским гусарским полком и, произведенный в генерал-майоры за битву при Ларотьере, во главе гусарской бригады выступил в Париж. Давыдов служил до 1831 года. Скончался скоропостижно 23 апреля 1839 года.

Д. В. Давыдов, 1784-1839,
 генерал-майор

description:
К началу войны за плечами у генерал-майора Дорохова был уже большой военный опыт. Начав службу в 1787 году, он сражался против турок под командованием Суворова. Участник боев при Фокшанах, Рымнике, он воевал в Польше, где отличился при взятии Праги (предместье Варшавы). С 1803 года — шеф Изюмского гусарского полка. Участвовал в кампании 1806 года.Начал Отечественную войну, командуя авангардом в армии Барклая. Будучи отрезан во время отступления от 1-й армии, с боями, искусно маневрируя, пробился к армии Багратиона. Участвовал в боях под Смоленском. При Бородине отбросил смелой атакой французов от Багратионовых флешей. После оставления Москвы Дорохов командовал партизанским отрядом, состоявшим из драгунского, гусарского и трех казачьих полков. Нанеся врагу сильный урон, Дорохов возвратился к армии, захватив 1500 пленных, из них 48 офицеров. Блестящей военной операцией Дорохова явился захват Вереи. Подойдя скрытно ночью, Дорохов перед рассветом без единого выстрела ворвался в город, заняв его через полчаса. В сражении под Малоярославцем был тяжело ранен в ногу. В начале 1815 года скончался в Туле.

И. С. Дорохов, 1762-1815,
генерал-лейтенант

title: Герои Отечества