ДСо18-13-Заключение (Лекции Северов Часть 3)

Carnegie MellonЗаключениеАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 17, 7 декабря, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771Carnegie MellonВведение2Понятия программированияПрограммаопределённый наборпредписанийпрограммистДанныенеопределённый наборинформацииПрограммаПроцессожидаемый набор событийДанныеПрограммируемаясистема(исполнитель)РесурсыПроцессРесурсыВремя работы¢§§¢¢ПрограммистаСистемыЭнергияПространство3[Около]компьютерные явления¢¢¢Модель – упрощённоепредставление законовповедения частей иотношений системыЯзык модели - знаковаяподсистема фиксации,переработки и передачиинформацииМашина – модельныйисполнитель, которомунаправленыпредписания на языкемоделиРынки¢ Потребители¢ Задачи¢Алгоритмы¢ Программы¢ Система/Аппаратура¢ Цифровые схемы¢ Аналоговые схемы¢Физические явления в[не]линейных структурах¢4Некоторые [около]компьютерные языки¢Задачи¢Языки спецификаций¢Языки проектирования¢Алгоритмы¢Алгоритмические языки¢Программы¢Языки программирования¢Архитектура «системы»¢Языки обращений к «системе»¢Архитектура аппаратуры¢Языки команд аппаратуры¢Блоки архитектуры¢Языки микрокоманд¢Цифровые схемы¢Языки цифровых схем¢Аналоговые схемы¢Языки аналоговых схем¢Языки физических моделей¢Физические явления в[не]линейных структурах5Свойства алгоритмаДискретность данных и действий над нимиПонятность: доступность и однозначность правилКонечность: решение задачи за конечное число шаговОпределённость: воспроизводимость результатаМассовость: применимость к различным данным6Алгоритм формально: итог§A={a1,a2,…,ap} - алфавит§A* = A0 È A1 È A2 È …È An –множество всех слов,состоящих не более чем из n символов.§F: A* ® A*7ПрограммаРеализация алгоритма на языкепрограммирования, определяющем…1.2.3.4.Действия - операции и операторыДанные - типы и экземплярыКонструкцию сложных данных и действийВзаимодействие со средой8Масштабы событий вашей программы¢Ваш исполнительЯдропроцессораПамятьУBBУBBУBBУBBКрупнее:§ Среда разработк觧§§СоединительРедактированиеТрансляцияСвязывание…§ Среда исполненияЗагрузка§Выделение ресурсов§Нормирование работы иреагирование на запросы§Освобождение ресурсов§…Мельче – за рамками семестра§¢Ваш процесс§§¢Выполнение операцийИзменение состоянияДругие процессы9Создание программы в окруженииРедактированиеG Предписания редактору⇓ Текст программы⇐ Ваши изменения вручнуюТрансляцияE Предписания трансляции⇓ Объектный код⇐ Библиотечный исходный текстКомпоновкаE Предписания компоновки⇓ Загрузочный код⇐ Библиотечный машинный кодЗагрузкаE Предписания загрузки⇓ Исполняемый код⇐ Решения среды исполненияВыполнение, отладка E Предписания исполнения⇓ Результат⇐ Внешние данные, коды, события10Carnegie Mellon(Само)обман¢Что есть (само)обман ?§§§§§¢Брать чужой код: копируя, перенабирая, подглядывая, принимая файлыПересказывать: устное описание кода одним человеком другомуНатаскивание: помощь другу в построчном написании заданийПоиск решения в сетиКопирование кода предыдущих кусов и экзаменовЧто НЕ есть (само)обман?§ Объяснять как использовать инструменты или системы§ Помогать другим в вопросах конструкции верхнего уровня11Carnegie MellonМашина Тьюринга12УСТРОЙСТВО МАШИНЫ ТЬЮРИНГАконечный алфавит символов a = {a0,a1,…an};2.

конечный список Q={q0,q1,…,qm} элементарныхсостояний;3. программа, составленная из команд Tij, видаaiqj"a’iq’jM,где M - один из символов движения L, R или S.NB: результат работы машины зависит от её начальногосостояния1.… l l l l l l a* a* a* a* a* a* l l l l l l l l l …q#13)(lXX(lXq0q1q0q2q0LRLRАЛФАВИТa = {(,),0,1,X})X0Xq1q1qoq1LRSLq2--0 - S1 - SX q2 LСостоянияq0 – от начала вправо до )q1 – влево до парной (q2 - влево до конца14Разновидности машинТьюрингак доказательству существованияалгоритмически неразрешимых задач15КОМПОЗИЦИЯ МАШИН ТЬЮРИНГА…lllXXXXXXXXXXXXXXl()()lll…¢) 0 -> X 1 L( 0 -> ( 0 RX 0 -> X 0 Rl 0 -> l 2 L¢) 4 -> X 5 L( 4 -> ( 4 RX 4 -> X 4 Rl 4 -> 0 6 LX 3 -> l 3 Rl 3 -> l 4 R¢( 1 -> X 0 RX 1 -> X 1 Ll 1 -> 0 0 S¢( 5 -> X 4 RX 5 -> X 5 Ll 5 -> n 0 S¢( 2 -> 0 0 SX 2 -> X 2 Ll 2 -> l 3 R¢( 6 -> n 0 SX 6 -> X 6 Ll 6 -> y 0 S16Двоичная машина Тьюринга¢¢¢Пусть алфавит a машины Т состоит из k символов,тогда для их кодирования машине Т* потребуется n =élog2(k+1)ù двоичных разрядов.Анализ кортежей из n бит при движении Т* вправобудет приводить к состоянию, соответствующемусчитыванию символа из a машиной Т.И наоборот: с каждым из k символов будемассоциировать набор из n движений влево Т* сзаписью 0 или 1, которые составят двоичный кодсимвола, который записала бы машина Т.17МАШИНА ТЬЮРИНГА С ЛЕНТОЙ, БЕСКОНЕЧНОЙ ВОДНОМ НАПРАВЛЕНИИ.………18Универсальная Машина ТьюрингаЕсли машина Т: sx ® Sf(x)sx…то существует машина U: DT,sx ® Sf(x)DTstqtОписаниемашины ТСимволТСостояниеТsx…Рабочая лента19Проблема остановаT:10®11R00®11RDT11 ®10L01 ®00SDT101TA1 10TA……$ ли анализатор А: " T и " t выдает результат1 – в случае, если останов Т на наборе t произойдет,0 – в противном случае ?20АЛГОРИТМИЧЕСКИ НЕ РАЗРЕШИМАНе существует алгоритма (машины Тьюринга),• позволяющего определить по описанию• произвольного алгоритма• и его исходных данных• останавливается или работает бесконечно• этот алгоритм• на этих данных.21Доказательство¢¢¢¢¢¢Предположение обратного – существование «анализатора»Шаг 1.

На вход анализируемой машине – её описаниеОпределение самоприменимой машиныШаг 2. Композиция «анализатора» и «копира»Шаг 3. Модернизация композиции цикломШаг 4. Парадокс свойств модернизированной композиции22ШАГ 4DB*…q0«НЕТ»SB*«ДА»xRxLВ* самоприменимая машина?Если да, то попадаем в циклЕсли нет, то попадаем на остановПротиворечия опровергают исходное предположение23Carnegie MellonАлгоритмыМаркова24Нормальный алгоритм МарковаУпорядоченное множество подстановок видовb " b’ и b * b’Исполнитель, просматривая слово s слева направо,пытается последовательно применить к нему правилаиз множества подстановок.1.

Если удается применить правило вида b " b’, топроцесс повторяется со словом s’;2. Если – вида b * b’ – происходит результативныйостанов.3. Если не удается применить ни одно из правил –останов не результативный (аварийный).25Композиция алгоритмов Маркова1.Удвоим алфавит, добавив для каждогосимвола алфавита x его близнеца x2.Добавим еще два символа a и b,которые не входили в исходный алфавит.3.Преобразуем R в Ra заменойправил вида … * z на …®azПреобразуем S в Sb заменой4.1.2.x на xправил вида … * z на …®zb26Проблема самоприменимостиНевозможно построить НАМ, которыйдля любого другого НАМ выносил бырешение о том, произойдет или нетостанов этого НАМ при его работе надданными, представляющимиописание этого НАМ.27Carnegie MellonОперации и данныеС/С++28Модель исполнителяЦПОУОсновнаяпамятьУУУBBУBBУBBУBBРегистрыСреда взаимодействия29ПеременнаяИменованная область памяти типизованныхзначений.1.

Имя (адрес начала),2. Тип (размер и правила операций),3. Значение (содержимое памяти)30Эволюция базовых типов данных¢Базовые типы данных§ Целые (char, int)§ Вещественные (float, double)§ Никакой (void)¢Модификаторы типа§ Без/Знаковые (un/signed)§ Короткие/Длинные (short, long)¢Спецификаторы класса памяти:§ Статические/Автоматические (static, auto)§ Регистровые, Внешние (register, extern)¢Квалификаторы изменчивости:§ Неизменяемые (const),§ Изменчивые (volatile), исключаемые из оптимизации3119 приоритетов операцийПриоритет Обозначениеи порядокНазначение1ð::Разрешения контекста2ï()Вызов или описание функции()Конструкция значения[]Индекс массива->Косвенная принадлежность.Прямая принадлежность++Инкремент (постфиксная)--Декремент (постфиксная)!Логическое отрицание~Битовое отрицание (сумма по модулю 2)+Унарный плюс-Унарный минус3ð++Инкремент (префиксная)32Составные типы данныхМассивы – наборынумерованных однородных данных• СтрокиСтруктуры – наборыименованных разнородных данных• Объединения• ПеречисленияУказатели – переменные содержащиеадрес• Ссылки33Объединениесовмещение полей – точек зренияunion тег { список_полей } имя_объекта;ПеречислениеНабор именованных целых константenum тег { список_имен } имя_объекта;Битовые поляНабор целых полей определённой длиныstruct тег { поле:число_бит; } имя;union тег { поле:число_бит; } имя;34Carnegie MellonФункции иввод/вывод С/С++35УКАЗАТЕЛИ¢¢¢Переменные, содержащие адресОписание и инициализацияint *Pc, **Pd;int a=5, b[]={1,2,3}, *Pa=&a, *Pb=b;char *s=²String²;Присваивание значенияconst int *b ={1,2,3};Pd=&Pb; Pc=&b[1];36Операции с указателямиint n, b, a[10], *pb=&a[0], *pe=&a[9], *pc;¢¢Арифметическиеn = pe - pb; // кол-во элементов (не байт!)pb++;// &a[1] (адрес следующего// элемента но не байта!)pc = pe – 1; // &a[8]pb + pe;// ОШИБКА !!!Разыменованияb = *pc;// b = a[8];NB: операции с указателями являютсяразмерными!!!37Ссылки*)Другое имя переменной (псевдоним)¢ Описание и инициализацияint a=5, &b=a;// a и b – разные имена одной// и той же области памяти¢*)только в С++38Тип FILE*struct _iobuf {typedef struct _iobuf FILE;char *_ptr;Илиint _cnt;#define FILE struct _iobufchar *_base;int _flag;FILE *a;int _file;FILE* fopen(int _charbuf;const char* name,int _bufsiz;const char* accesschar);*_tmpfname; };int fclose(FILE* a);39Определение новых действийФункции40Соглашения функции1.

Имеет список аргументов (параметров)2. Возвращает значение3. Объявляется указанием своего имени и типавозвращаемого значения4. Определяется перечислением операторов41Пример 1: решето ЭратосфенаСоздание динамического массива2345678910111213141516171811010101010101010Создание двумерного динамического массиваconst int n=3, m=5;int (*a)[m] = new int[n][m]; // *b[m]// a = (int(*)[m])malloc(n*m*4);4 байта20 байт42Операции Инкремента и Декремента1. *++Ptr // *(Ptr += 1) – перевод указания наследующий элемент с использованием его значения привычислении выражения2.

--*Ptr // *Ptr -= 1 – уменьшение текущего элементана единицу с использованием этого значения в вычислениивыражения3. *Ptr++ // (t=Ptr,Ptr+=1,*t) – использованиезначения текущего элемента и перевод указания наследующий элемент4. (*Ptr)-// (t=*Ptr,*Ptr-=1,t) –использование в вычислении текущего значения элемента споследующим его уменьшением на единицу43Пример 2: операции со строками¢¢¢¢Вычисление длины строки (strlen(a))*)char *b=a; while(*b++); return b-a-1;Копирование (strcpy(a,b))while(*a++ = *b++);Сравнение (strcmp(a,b))while(*a++ == *b++) if(!*(a-1)) return 0;return *(a-1) - *(b-1);Конкатенация (strcat(a,b))char a[N]={…,’\0’},*p=a;while(*p)p++; while(*p++=*b++);*)#include <string.h> - библиотечные функции Си44Основные функции ввода/вывода¢int getchar(void);¢int putchar(int);¢¢¢int getche(void);int getch(void);int putch(int);int [f]putc(int, FILE*);¢int [f]getc(FILE*);¢¢int printf("%s", char*);int puts(const char*);¢int fputs(char*, FILE*);¢¢int scanf("%s", char*);char* gets(char*);¢char* fgets(char*, int, FILE*);¢45Вывод на экран и в поток#include <stdio.h>#include <conio.h>#include <string.h>int main() {const char *s1="This isoutput into the stdout stream",*s="to the console";char *p, s2[]="This is output intothe stdout stream";// *s1='a';while(*s1) putchar(*s1++);}putchar('\n');p=strstr(s2,"stdout");*(p+3)='e'; *(p+5)=*(p+4)='r';p=s2;while(*p) fputc(*p++,stderr);fputc('\n',stderr);p=strstr(s2,"into");while(*p++=*s++); p=s2;while(*p) putch(*p++);putch('\n');return 0;46Пример 3: потеря быстродействия¢¢¢Для заданных строк s1 и s2 найти номер символа, с которогоначинается вхождение строки s2 в строку s1.int strncmp(char* s1, char* s2, int n) – производит сравнение неболее n символов из двух строк и возвращает значение 0 –только в случае если строки совпадают.int main(int argn, char* argv[ ])§ argn – количество слов в командной строке§ argv – параметры, переданные программе47Carnegie MellonАбстрактныетипы данных С++48«ЧТО ПОЗВОЛЕНО ЮПИТЕРУ …»#include <stdio.h>#define N …struct { int a[N];} a,b;int main() {…a=b;//разрешено…return 0; }#include <stdio.h>#define N …int a[N],b[N];int main() {…a=b;// ошибка…return 0; }49Пример 4: односвязный список¢¢Определение формата узла спискаstruct node {My_type item;struct node *next;x->item};typedef struct node *link;x………x->nextВыделение памяти для узла спискаlink x = (link)malloc(sizeof(struct node));¢Инициализация элементов узла(*x).item = … , x->next = NULL;50СПИСОК, ОЧЕРЕДЬ, СТЕКОчередьFIFO – First In First OutСтекLIFO – Last In First OutСписокCasual In Casual Out51РЕАЛИЗАЦИЯ МАССИВАМИ52РЕАЛИЗАЦИЯ СТРУКТУРАМИ53Полиморфизмразные функции с одинаковым именем и различнымипараметрамиint abs(int a) { return a>=0?a:-a; }double abs(double a) { return a>=0?a:-a; }54Шаблоны функцийtemplate<typename T> T abs(T a) {return a>=0?a:-a; }int x; …y = abs(x); // int abs(int);float u; … v = abs(u); // float abs(float);55Инкапсуляцияcomplex a, b(1.,2.);struct complex { float Re,Im;complex() { Re = Im = 0; }complex(float R, float I) { Re=R; Im=I; }float abs() { return sqrt(Re*Re + Im*Im); }complex operator+(complex a) {return complex(Re+a.Re, Im+a.Im);}};ostream& operator<<(ostream& a,const complex& b){return a << ′(′ << b.Re << ′,′ << b.Im << ′)′<< endl; }a.abs();a.operator+(b); // a+b;56Классclass complex { float Re,Im;public:complex() { Re = Im = 0; }complex(float R, float I) { Re=R; Im=I; }float abs() { return sqrt(Re*Re + Im*Im); }complex operator+(complex a) {return complex(Re+a.Re, Im+a.Im); }friend ostream& operator<<(ostream& a, const complex& b) {return a << ′(′ << b.Re << ′,′ << b.Im << ′)′<< endl; }};57Шаблон классаtemplate<typename T> class complex {T Re,Im;public:complex(T R=0, T I=0) { Re=R; Im=I; }T abs() { return sqrt(Re*Re + Im*Im); }complex operator+(complex a) {return complex(Re+a.Re, Im+a.Im); }friend ostream& operator<<(ostream& a, constcomplex& b) {return a << ′(′ << b.Re << ′,′ << b.Im <<′)′;}};58РЕАЛИЗАЦИЯ ШАБЛОНАМИ59Пример 2: вычисление площади прямоугольнойфигуры, заданной произвольным перечислениемкоординат вершин#include <iostream>#include <fstream>#include “SQL.h» /* Файл с описанием шаблоновСтека, Очереди и Cписка*/using namespace std;60Типы данных¢Базовые¢Указатели¢Составные§ Массивы, строки,§ Структуры, объединения, перечисления¢Абстрактные§ Списки§ Очереди§ Стеки§…61ДЛИННЫЙ ФАКТОРИАЛn! = n10! = 10(n − 1)9......332211 = 3628800,сумма цифр числа 10! есть …3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.Найдите сумму цифр числа N!62ДЛИННОЕ 2NКакова сумма цифр числа 2n?0 £ n £ 10001000k2 ≈10k ≈ 1000*lg2 k ≈ 30263АСТЕРОИДЫ64Три астероида летят в космическом пространстве.