11бд

Графы

Как в С++ прочитать числа с каждой строки, если количество чисел в строке заранее не известно?
k=0;
do
{
cin>> A[k];
k++;
}while(cin.get()!=10);

Объектно-ориентированное программирование в С++


#include <iostream>

using namespace std;
//описание класса
class TName_class
{
public:
//свойства
    string name;
//конструктор по умолчанию
    TName_class(){name="?";};
//конструктор с параметрами
    TName_class(string N){name=N;};
  //методы
    void show(){cout<<"name="<<name<<endl;};
    string getname(){return name;};
};

int main()
{
    TName_class T,X("my name");
    X.show();
    cout<<"name T:"<<T.getname()<<endl;
    return 0;
}

Профессии, связанные с IT.

Знаете ли вы, что такое IT?

Выберите одну из профессий, связанных с IT:

Информационные технологии (IT)

  • 3D-аниматор
    3D-аниматор — профессионал в области трехмерной графики, который настраивает компьютерные персонажи для игровой анимации, обеспечивает движение рисованных моделей и объектов. Говоря высоким слогом, искусство 3D-аниматора заключается в том, чтобы вдохнуть в персонажа душу и сотворить живой, одушевленный мир вокруг.
  • ERP-консультант
    ERP-консультант (консультант по внедрению ERP-систем) – специалист по внедрению и наладке систем планирования предприятия.


  • ERP-программист
    ERP-программист — это специалист, который обеспечивает функционирование ERP-системы. ERP-программисты работают в консалтинговых компаниях или в IT-отделах крупных компаний, например, банков, торговых предприятий.

  • IT-евангелист
    IT-евангелист — специалист, отвечающий за продвижение программных продуктов.

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

  • Администратор базы данных
    Администратор базы данных — специалист, обслуживающий базы данных.

  • Администратор сайта
    Администраторы сайтов отвечают за поддержку работоспособности сайта и обеспечение сетевой безопасности, управляют размещением, обновлением, модерацией контента.

  • Гейм-дизайнер
    Гейм-дизайнер (game designer, геймдиз) — это создатель игр в широком смысле этого слова. Его можно назвать продюсером игр, ответственным за игровой дизайн проекта. Профессия гейм-дизайнера находится на стыке творческих идей и технического документирования.
  • Киберспортсмен
    Киберспортсмен – участник компьютерных видеоигр.


  • Контент-менеджер
    Можно ли объединить четыре творческих профессии в одной и при этом зарабатывать 60-100 тысяч рублей в месяц? А всегда быть уверенным в завтрашнем дне и открытой вакансии? Регулярно учиться за счет компании и иметь авторитет среди коллег и руководства? Да, можно, если ваша профессия — контент менеджер. Дочитайте эту статью до конца и получите пошаговую инструкцию, как добраться до места под солнцем.
  • Модератор форума
    Модератор форума отвечает за работу форума, отвечает на вопросы посетителей, выступает в роли цензора (следит за поведением участников форума, пресекает попытки некорректных или нецензурных высказываний или рекламных сообщений).

  • Монтажник РЭА
    Монтажник РЭА – специалист по монтажу радиоэлектронной аппаратуры.

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

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

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

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

  • Тестировщик программного обеспечения (ПО)
    Тестировщик ПО – это специалист, который занимается тестированием программного обеспечения, контролирует его качество.




Подготовьте презентацию об этой профессии:
  1. Чем занимается, какие вопросы решает на работе этот специалист?
  2. Где, в каких областях науки, производства можно этим заниматься?
  3. Что нужно знать, чтобы быть успешным специалистом?
  4. Где этому можно научиться?
  5. Хотели бы вы этим заниматься?
  6. Продемонстрируйте работу этого специалиста (домашнее задание)

Домашнее задание:

В множестве из n человек каждый может знать или не знать другого (если A знает B, отсюда не следует, что B знает A). Все знакомства заданы булевой матрицей n × n. В этом множестве может найтись или не найтись знаменитость — человек, который никого не знает, но которого знают все. Предложите алгоритм, который бы находил в множестве знаменитость или говорил, что ее в этом множестве нет. Сложность по времени — O(n), сложность по памяти — O(1). 

Создание сайта с помощью сервиса Google

Виртуальная рабочая тетрадь учителя (с примерами и заданиями)

При создании своего сайта обратите внимание на цветовое сочетание: http://colorscheme.ru/ 

Работа с фотографиями в GIMP (растровый редактор)

Домашнее задание:
1. Оформить свою фотографию на память.
2. Отсканировать старую распечатанную фотографию из семейного альбома (сохранить для сравнения) и откорректировать ее. Если фотография черно-белая - сделать ее цветной.
3. На своей отсканированной фотографии выделить какой-нибудь объект или лицо, используя маску.
4. Сделать анимацию (не менее 3-5 картинок, размером 100х100 пикселей).

Дерево

Обычно в программировании рассматривается  двоичное (бинарное) дерево, у которого есть корень и два связанных с ним отдельных двоичных дерева («левое» и «правое» поддеревья) или листья (пустое дерево).

Области применения:
  • поиск в большом массиве неменяющихся данных;
  • сортировка данных;
  • вычисление арифметических выражений;
  • оптимальное сжатие данных (метод Хаффмана).
Обойти дерево - это «посетить» все узлы по одному разу, т.е. получить значения ключей в каждом узле.
                           Рис. 1                                           Рис. 2
Узлы и листья дерева можно обойти одним из следующих способов:
  • в прямом порядке (поиск в глубину):  
рис. 1: 6 3 1 4 8 7 9
рис. 2: * + 1 4 - 9 5 (префиксная запись)
  • в симметричном порядке: 
рис. 1: 1 3 4 6 7 8 9 (в порядке возрастания)
рис. 2: 1 + 4 * 9 - 5 (инфиксная запись)
  •  в обратном порядке (поиск в ширину): 
рис. 1: 1 4 3 7 9 8 6
рис. 2: 1 4 + 9 5 - * (постфиксная запись)
Задача: перевести инфиксную запись арифметического выражения в постфиксную и префиксную.

// описание структуры дерева:
struct TNode
  {
  string data;
  TNode *left;
  TNode *right;
  };
// объявление указателя на корень дерева
TNode *p;
// обратный порядок
void Search_LPK(TNode *p){
    if(p!=NULL){
        Search_LPK(p->left);
        Search_LPK(p->right);
        cout << p->data << ' ';
    }
}
// симметричный порядок
void Search_LKP(TNode *p){
    if(p!=NULL){
        Search_LKP(p->left);
        cout << p->data << ' ';
        Search_LKP(p->right);
     }
}
// прямой порядок
void Search_KLP(TNode *p){
    if(p!=NULL){
        cout << p->data << ' ';
        Search_KLP(p->left);
        Search_KLP(p->right);
    }
}

int Priority ( char op ){
  switch ( op )
    {
    case '+':
    case '-': return 1;
    case '*':
    case '/': return 2;
    }
  return 100;
}
int LastOp ( string s ){
  int i, minPrt, res;
  minPrt = 50; 
  res = -1;
  for ( i = 0; i < s.size(); i++ )
    if ( Priority(s[i]) <=   minPrt )
      {
      minPrt = Priority(s[i]);
      res = i;
      }
  return res;
}
TNode *MakeTree ( string s ){
  TNode *Tree;
  Tree = new struct TNode;
  int k = LastOp ( s );
  if ( k == -1 ) {
    Tree->data = s;
    Tree->left = NULL;
    Tree->right = NULL;
  }
  else {
    Tree->data = s[k];
    Tree->left =   MakeTree ( s.substr(0,k) );
    Tree->right = MakeTree ( s.substr(k+1) );
}
  return Tree;
}

int main ()
{
    string s;
    cin>>s;
    p = MakeTree(s);
    cout<<"LPК:"; Search_LPK(p); cout<<endl;
    cout<<"LKP:"; Search_LKP(p); cout<<endl;
    cout<<"KLP:"; Search_KLP(p); cout<<endl;
    delete p;
    return 0;
}

Домашнее задание: (на informatics.mccme.ru задачи I-L раздела "Стеки, очереди, деки")
1. Перевести инфиксную запись арифметического выражения со скобками в постфиксную и префиксную: (5+23*16)/(8-28*(9+34)/5)
2. Перевести инфиксную запись арифметического выражения с функциями и переменными в постфиксную и префиксную: sqrt(count-(42*part))
3. Вычислить значение арифметического выражения, представленное в инфиксной форме: 12+cos(sqrt(12+sin(2)))
4. Вычислить значение арифметического выражения с переменными, представленное в инфиксной форме: cos(z+abs(sqrt(r*sin(x+4)))) при r=5, z=10, x=3

Дек

Это линейный список со свойствами стека и очереди.

Очередь 

Это линейный список, добавление элементов в конец, а чтение с начала: «первый пришел – первым ушел» (FIFO = First In – First Out).


Основные операции с очередью:
  • push – добавить элемент в конец очереди
  • pop – удалить элемент с начала очереди
  • front – вернуть элемент с начала очереди (без удаления)
  • empty – вернуть true, если очередь пуста, и false в противном случае.

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

  • инфиксная форма (знак операции между данными): (5+15)/(4+7-1) 
  • префиксная форма (знак операции перед данными): / + 5 15 - + 4 7 1
  • постфиксная форма (знак операции после данных): 5 15 + 4 7 + 1 - /
Задание: По инфиксной форме записи арифметического выражения написать программу вычисления, используя стек.

Стек

Стек (англ. stack – стопка) – это линейный список, в котором элементы добавляются и удаляются только с одного конца: «последним пришел – первым ушел» (LIFO = Last In – First Out).

Задача: Дан массив чисел. Вывести его в обратном порядке без нулевых.
#include <iostream>
#include <stack>
#include <fstream>
using namespace std;
int main()
{
    ifstream cin("input.txt" );
    ofstream cout("output.txt") ;
    stack <int> S;
    int a,n=0;
//ввод массива
    while(cin >> a) S.push(a); 
//вывод массива
    while ( !S.empty() )
    {
        a=S.top();
        if (a<>0) cout<<a<<" ";
        S.pop();
    }
return 0;
}

Основные операции со стеком:
  • push – добавить элемент на вершину стека
  • pop – удалить элемент с вершины стека
  • top – вернуть элемент с вершины стека (без удаления)
  • empty – вернуть true, если стек пуст, и false в противном случае.
Дополнительно:
  • перевод из строки (string str;) в число x:
    stringstream(str)>>x; /* подключите библиотеку sstream */
  • перевод из вещественного числа (float x;) в строку (char c[100];) с форматом 3 знака после запятой:
    sprintf(c, "%0.3f", x); /* подключите библиотеку stdio.h */
  • прочитать строку (string str;) до конца со всеми пробелами до символа конца строки:
    getline(cin,str);
  • прочитать строку (string str;) до первого пробела или символа конца строки:
    cin>>str;

Ассоциированные массивы (множества)

Чтобы вывести частотный анализ слов в файле, можно воспользоваться ассоциированным массивом, в котором вместо индекса будет строка (first), а значение элементов массива - количество слов (повторений) в файле (second). Для вывода элементов массива - используем итератор (указатель на текущий элемент массива).

#include <iostream>
#include <fstream>
#include <map>
using namespace std;

int main()
{
    map <string,int> L; //ассоциированный массив
    map <string,int>::iterator it; // итератор
    string s;
    ifstream cin("input.txt");
    ofstream cout("output.txt");
// ввод и добавление в ассоциированный массив
// если строки нет, то она добавиться.
    while(cin>>s) L[s] ++;

// вывод элементов массива по итератору
    for ( it = L.begin(); it !=  L.end(); it++ )
       cout << it->first << " " << it->second << endl;

    return 0;
}

Другие функции по работе с ассоциированным массивом:
  1. количество записей: int p=L.count ( s ); 
  2. добавление новой записи: L.insert ( pair <string,int> (s, 1) );
  3. поиск записи: it = L.find(s);
  4. удаление записи по итератору: L.erase (it);
  5. количество элементов в массиве: int n=L.size();
  6. указатель на начало массива: it = L.begin();
  7. указатель на конец массива: it = L.end();

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

1 вариант - если массив очень большой 
int *A;
int N;

cin>>N;
A=new int [N];

for (i=0; i<N;i++)
cin>>A[i];

sort(A, A+N); // сортировка по возрастанию #include <algorithm>

for (i=0; i<N;i++)
cout<<A[i]<<" ";

delete [] A;

2 вариант - если размер массива заранее не известен

#include <vector>

vector <int> A;
int a, N;
cin >>N;
for (i=0; i<N;i++)
{ cin>>a; A.push_back(a); }

sort(A.begin(), A.end());

for (i=0; i<A.size();i++)
cout<<A[i]<<" ";

Темы к зачету по информатике 11 д класс

Указатель

Указатель – это переменная, в которой можно сохранить адрес любой переменной заданного типа.
TBook *p; // переменная типа указатель

Можно присвоить адрес в переменную типа указатель:
p = &B; //запись в p адрес переменной В
Теперь обращение к полям структуры p->author равнозначно B.author.

Можно выделить в памяти определенное количество байт по заданному типу и сохранить этот адрес в переменную р:
p = new TBook; // выделение памяти
delete p; //освобождение памяти

Нулевой адрес NULL ни на что не указывает. Это можно использовать при удалении записей.
p=NULL; // удаление адреса из переменной
Если выделяли память под запись с помощью new, то для удаления записи лучше использовать delete p;

Аналогично с массивом:
TBook *P[N];
for ( i = 0; i < N; i++ )
  P[i] = &Books[i];

или

// выделяем память
for ( i = 0; i < N; i++ )
  P[i] =new TBook;

//освобождаем память
for ( i = 0; i < N; i++ )
 delete P[i];

Вывод элементов массива через указатели:
for ( i = 0; i < N; i++ )
cout << P[i]->author << " " << P[i]->title << ". " << P[i]->count << " шт." << endl;

 При сохранении в файл без учета удаленных записей, проверяем: если указатель не нулевой, то записываем в файл.
  ofstream Fout;
  Fout.open ( "books.dat", ios::binary);
  for ( i = 0; i < N; i++ )
    if (P[i] != NULL) Fout.write ( (char*) P[i], sizeof(TBook) );
  Fout.close ();

Сортировка по указателям не меняет порядок записей в массиве:
TBook *p1;
for ( int i = 0; i < N-1; i++ )
for ( int j = N-2; j >= i; j-- )
   if (strcmp(P[j]->author, P[j+1]->author)>0) /* т.е. P[j]->author > P[j+1]->author;  для strcmp() не забудьте подключить библиотеку stdio.h и string.h */
  {
       p1 = P[j]; P[j]= P[j+1]; P[j+1]= p1; //перестановка указателей
   }

Создание базы данных с помощью структур в С++

Повторите тему базы данных и пройдите тест.
Презентация (см. раздел 39. Структуры. Базы данных)

Пример рабочей программы:
#include <iostream>
#include <fstream>
using namespace std;
typedef struct
    {
    char author[10];  // автор, строка из 10 символов
    char title[10];   // название, строка из 10 символов
    int count;      // количество книг, целое число
    } TBook;

 int main()
{
   TBook B;
cout << sizeof(B.author) << endl; //размер в байтах
cout << sizeof(B.title) << endl;
cout << sizeof(B.count) << endl;

 //ввод с клавиатуры
cin >> B.author;
cin >> B.title;
cin >> B.count;

 //вывод на экран
cout << B.author << " " << B.title << ". "
     << B.count << " kol.";

 //вывод в бинарный файл с добавлением
ofstream Fout;
Fout.open ( "books.dat", ios::binary | ios::app);
Fout.write ( (char*) &B, sizeof(TBook) );
Fout.close ();

 //чтение из бинарного файла
ifstream Fin;
Fin.open ( "books.dat", ios::binary );
int i=0;
int m=sizeof(TBook); //кол-во байт на одну запись
for (i=0;!Fin.eof();i++)
{
    Fin.read ( (char*) &B, sizeof(TBook) );
    if(Fin.eof()) break;
    cout << "author:"<<B.author << "\ntitle:" << B.title
     << "\ncount:" << B.count << " kol.\n";
}
cout << "kol.rekord: "<< i << endl;

 //считать сразу все записи в массив
int N;
TBook Books[100];
Fin.read ( (char*) Books, 100*sizeof(TBook) );
N=Fin.gcount()/sizeof(TBook); // сколько записей считали

 //редактирование k-й записи
   int k=2;
   fstream F;
   F.open ( "books.dat", ios::binary | ios::in | ios::out); //открываем файл для записи и чтения
   F.clear();  F.seekp((k-1)*m);//считываем k-ю запись
   F.read ((char*) &B, sizeof(TBook));
   cout << "author:"<<B.author << "\ntitle:" << B.title
     << "\ncount:" << B.count << " kol.\n";
   B.count++; // изменение данных в k-й записи

 // сохранение изменений на то же место
   F.clear();  F.seekp((k-1)*m);//считываем k-ю запись
   F.write ((char*) &B, sizeof(TBook));
   F.close();

 //очистить бинарный файл
ofstream Fout;
Fout.open ( "books.dat", ios::binary);
Fout.close ();
    return 0;
}

Домашнее задание:

1. Опишите структуру, в которой хранится информация о 
а) видеозаписи;
б) сотруднике фирмы «Кролики Великаны»;
в) самолёте;
г) породистой собаке
д) свой вариант

2.Постройте программу, которая работает с  базой данных в виде двоичного файла. 
Ваша СУБД (система управления базой данных) должна иметь следующие возможности:
а) просмотр записей;
б) добавление записей;
в) удаление записей;
г) редактирование записей;
д) поиск записи по заданному запросу;
е) сортировка по одному из полей (через указатели).


Размещение заданий в таблице продвижения

На данном этапе все выполненные задания Вы загружаете на свой Google-диск в свою папку и ссылку из совместного доступа копируете в таблицу продвижения.

Моделирование 

1 этап - составление программы, реализующая имитацию работы объекта моделирования, и руководства к ее применению. Тестовые задания оформить в виде таблицы.

2 этап - тестирование программы другим пользователем и составление акта проверки работы программы. Тестовые задания оформить в виде таблицы.

3 этап - защита программы.

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

Требования к составлению текста: шрифт -Times New Roman 14 пт, абзац - первая строка отступ - 1 см, слева, справа, перед и после абзаца - 0 см, междустрочный интервал - 1.5, выравнивание - по ширине. Рисунки и таблицы с подписями (в тексте ссылка на рисунок или таблицу). В конце - список источников. 

Системный подход в моделировании

Пройдите тест 8, 9, 10 на сайте kpolyakov.narod.ru. Решение оформите в текстовом процессоре. Документ загрузите на Google-диск в свою папку и ссылку из совместного доступа скопируйте в таблицу продвижения.

Домашнее задание от 17/21.11.14:

Выполните задание 4 в таблице продвижения. Номер задания соответствует номеру в списке таблицы. Решение оформите в текстовом процессоре. Документ загрузите на Google-диск в свою папку и ссылку из совместного доступа скопируйте в таблицу продвижения.

Построение графика функции

На странице блога http://computer-graphics-in-c.blogspot.ru/ выполнить Задание 2. Ссылку на программу добавить в Таблицу продвижения для графики.

Домашнее задание от 14/15.11.14:

Построить график параметрической функции (п.9 в списке заданий).

Модели и моделирование

Подготовить ответ на вопрос (стр. 64-65) в виде документа на 1 страницу: шрифт -Times New Roman 14 пт, абзац - первая строка отступ - 1 см, слева, справа, перед и после абзаца - 0 см, междустрочный интервал - 1.5, выравнивание - по ширине. Рисунки с подписями (в тексте ссылка на рисунок). В конце - список источников. Документ загрузить на свой Google-диск в свою папку и ссылку из совместного доступа копируете в таблицу продвижения.

Домашнее задание от 10.11.14: Написать программу по задаче 2 (стр. 65 учебника т. 1)

Смоделировать работу процессора, у которого есть 4 регистра - R0, R1, R2, R3. Все команды состоят из трех десятичных цифр: код операции, номер первого регистра и номер второго регистра или число от 0 до 9. Результат команды записывается во второй регистр. 
Команды вводятся последовательно, как символьные строки. После ввода команды программа показывает значения всех регистров.
Коды команд:
0 - стоп
1 - присвоение 
2 - копирование значения регистра
3 - сложение
4 - вычитание
5 - умножение
6 - деление
7 - логическое И (&)
8 - логическое ИЛИ (|)
9 - логическое исключающее ИЛИ (^)

Моделирование движения 

Компьютерная графика в С++, с использованием библиотеки OpenGL

Домашнее задание от 24-25.10.2014

Зарегистрироваться, настроить CodeBlocks и выполнить Задание 1 (нарисовать фигуру). Вставить ссылку на файл main.cpp в Ссылку на программу добавить в Таблицу продвижения для графики, предварительно загрузив на Google-Диск.

Тема: Целочисленная арифметика.
Решето Эратосфена. Длинные числа

http://kpolyakov.spb.ru//download/ch11-6_c_cpp.pdf

Перевод целого числа int k в строку char c[10]:
sprintf(c, "%d", k); //#include <stdio.h>

Перевод цифры в строке в число:
k=c[i]-'0';

Размер строки:
strlen(c);//#include <string>

Домашнее задание от 18-19.10.2014

Решить задачу: Сумма длинных чисел.

Домашнее задание от 10-11.10.2014

Решить задачи от А до I:
http://informatics.mccme.ru/mod/statements/view.php?id=11528

Тема: Доказательство правильности программ

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

Домашнее задание от 03.10.14

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

Написать программы для следующих алгоритмов (без использования встроенных функций С++):

  1. Перестановка элементов массива в обратном порядке
  2. Нахождение наибольшего элемента среди 4-х значений (без цикла, с наименьшим количеством операций)
  3. Найти НОД(m,n) по алгоритму Евклида
  4. Найти а в степени n
  5. Найти сумму всех делителей числа
  6. Определить количество слов в строке
  7. Преобразовать целое (дробное) число из строки символов


Тема: Сложность вычислений

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

Домашнее задание от 26.09.14

Составить таблицу с полями:
- № алгоритма
- Количество сравнений
- Количество арифметический операций
- Количество записей в память
- Количество элементов массива (100)
- Время выполнения программы

Написать программы для следующих алгоритмов и заполнить таблицу:

  1. Линейный поиск элемента в массиве
  2. Сортировка по возрастанию (по убыванию) элементов массива
  3. Двоичный поиск элемента в массиве
  4. Вывод делителей каждого числа в массиве
  5. Нахождение минимального и максимального элементов в массиве
  6. Количество положительных элементов в массиве
  7. Проверка на простоту каждого числа в массиве

Тема: Алгоритмически неразрешимые задачи

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

Домашнее задание от 19/22/26.09.14 

Напишите программу для машин Тьюринга и Поста, а также для НАМ для вычислимой функции: 

f(n)=1, если n делится на 3;
         0,если n не делится на 3.

Тема: Сжатие данных

Для экономии места на носителях или времени при передачи данных по сети Интернет используют разные алгоритмы сжатия.
Существуют алгоритмы сжатия без потерь (алгоритм RLE, код Шеннона-Фано, алгоритм Хаффмана) и с потерями (алгоритм JPEG для картинок, MP3 - для звука, MJPEG - для видео). 

Домашнее задание от 22/27.09.14

1. С помощью алгоритма RLE закодируйте сообщение (представьте в виде последовательности байтов с первым управляющим байтом): "АААДДДАББББББРРРРРРРРРААААААБРАХММММААММММ"
2. После кодирования методом RLE получилась следующая последовательность байтов (первый байт - управляющий)
00000011 10101100 00000010 10001111 11111111 10001001 10101110
Сколько байтов будет содержать данная последовательность после распаковки?
3. Раскодируйте сообщение, которое закодировано с помощью кода Шеннона-Фано (составьте коды для следующих символов: А-10, Б-22, В-7, Г-15, Д-34):
1111101001001111101110100000110
4. Постройте дерево Хаффмана и закодируйте сообщение:"В ЧЕТВЕРГ ЧЕТВЕРТОГО ЧИСЛА В ЧЕТЫРЕ С ЧЕТВЕРТЬЮ ЧАСА ЧЕТЫРЕ ЧЁРНЕНЬКИХ ЧУМАЗЕНЬКИХ ЧЕРТЁНКА ЧЕРТИЛИ ЧЁРНЫМИ ЧЕРНИЛАМИ ЧЕРТЁЖ"

Домашнее задание от 15.09.14

1. Написать программу на С++, реализующая алгоритм RLE (перед каждым повторяющимся символом вставить количество его повторений). Здесь можно найти информации по программированию на С++.
2. Подготовить реферат на тему (можно взять эту тему на конференцию):
"Коды Хэмминга"
"Алгоритмы CRC"
"Программы для сжатия данных"
"Алгоритмы сжатия изображения"
"Аудиокодеки"
"Видеокодеки"

Тема: Передача данных

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

Тема: Универсальный исполнитель. Машина Тьюринга. Машина Поста.  Нормальные алгорифмы Маркова.

Универсальный исполнитель - это исполнитель, который может моделировать работу любого другого исполнителя.

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

Тезис Чёрча-Тьюринга: Любой алгоритм может быть представлен как программа для машины Тьюринга.

Домашнее задание от 12-13.09.14

Составьте программу для машины Тьюринга:
5. Сложение двух чисел в двоичной системе, разделенные на ленте знаком +. Результат вывести вместо одного из слагаемого, удалив другое слагаемое.
6.  Сложение и вычитание двух десятичных чисел.
Полученные файлы отправить по почте или сохранить в своей папке на Google-диске.

Тема: Измерение информации. Формула Хартли. Вероятностный подход. Формула Шеннона.

В содержательном подходе: количество информации показывает уменьшение неопределенности знаний в два раза.     В алфавитном подходе:
 N = 2i, 
    где i - количество информации, N - количество символов в алфавите.
 
   Формула Хартли: 
log2N = i.
Вероятность появления какого-либо события из N возможных равновероятных событий равна:
 p=1/N.
Вероятностный подход дает следующую формулу:
 -log2p = log21/p = i.
При вычислении логарифма по основанию a можно воспользоваться следующей формулой:
logax=ln x/ ln a=lg x/ lg a.
Если в сообщение информация дается неполная (например, "достали карандаш из коробки" вместо "достали красный карандаш из коробки"), то возникает неопределенность знаний, которую можно вычислить по формуле Шеннона:
H=p1 log21/p1+p2 log21/p2+...+pn log21/pn=
=p1 I1+p2 I2+...+pn In,
где Ii=log21/pi - количество информации, полученной при возникновении i-го события,
pi - вероятность появления i-го события. Причем сумма вероятностей должна быть равна 1. 

Домашнее задание от 08-12.09.14

На Google-диске открыть файл Задание и выполнить его. 

Домашнее задание от 06.09.14

5. Ученик задумал целое число от -10 до 10. Какова вероятность того, что квадрат этого числа больше 25? Меньше 10? Равен 49? Определить количество информации.
6. В корзине лежат 8 черных шаров и 24 белых. Какова вероятность вытащить черный шар? Сколько бит информации несёт сообщение о том, что достали черный шар?
13. В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несёт 2 бита информации. Сколько всего шаров было в корзине?
14. В алфавите племени тумба-юмба 4 буквы: гласные О и А, согласные Ш и Щ. Вероятность их появления в тексте: А - 0,35; О - 0,4; Ш - 0,1; Щ - 0,15. Сколько битов информации несёт сообщение о том, что очередной символ текста - согласная?

Комментариев нет :

Отправить комментарий

Подписаться на: Сообщения ( Atom )