<!-- Macros: start -->
$\newcommand{\block}[2]{\begin{#1} #2 \end{#1}}$
$\newcommand{\cases}[1]{\block{cases}{#1}}$
$\newcommand{\up}[2]{\stackrel{#1}{#2}}$
$\def\dn#1#2{\mathrel{\mathop{#2}\limits_{#1}}}$
$\def\ident{\Longleftrightarrow}$
$\def\thus{\Rightarrow}$
$\newcommand{\set}[1]{ \{ #1 \} }$
$\newcommand{\bigset}[1]{ \left \{ #1 \right \} }$
$\newcommand{\bracs}[1]{ ( #1 ) }$
$\newcommand{\bigbracs}[1]{ \left ( #1 \right ) }$
$\newcommand{\bkets}[1]{\langle #1 \rangle}$
$\newcommand{\bigbkets}[1]{\left \langle #1 \right \rangle}$
$\newcommand{\mat}[1]{\block{Vmatrix}{#1}}$
$\newcommand{\det}[1]{\block{vmatrix}{#1}}$
$\newcommand{\pmat}[1]{\block{pmatrix}{#1}}$
$\newcommand{\emat}[1]{\block{matrix}{#1}}$
$\renewcommand{\geq}{\geqslant}$
$\renewcommand{\leq}{\leqslant}$
$\newcommand{\upline}[1]{\overline{#1}}$
$\newcommand{\dnline}[1]{\underline{#1}}$
$\def\ex{\exists}$
$\def\exo{\ex!}$
$\renewcommand{\fal}{\forall}$
$\renewcommand{\int}{\intop}$
$\def\inf{\infty}$
$\renewcommand{\tg}{\tan}$
$\renewcommand{\phi}{\varphi}$
$\renewcommand{\epsilon}{\varepsilon}$
$\def\alp{\alpha}$
$\def\lam{\lambda}$
$\def\gam{\gamma}$
$\def\eps{\epsilon}$
$\def\sig{\sigma}$
$\newcommand{\NN}{\mathbb{N}}$
$\newcommand{\ZZ}{\mathbb{Z}}$
$\newcommand{\RR}{\mathbb{R}}$
$\newcommand{\CC}{\mathbb{C}}$
$\newcommand{\FF}{\mathbb{F}}$
$\newcommand{\QQ}{\mathbb{Q}}$
$\newcommand{\EE}{\mathbb{E}}$
$\newcommand{\UU}{\mathcal{U}}$
$\newcommand\E{\mathbbold{e}}$
$\newcommand\F{\mathbbold{f}}$
$\newcommand\G{\mathbbold{g}}$
$\newcommand{\rawOlim}[3]{\dn{{#1}\rightarrow{#2}}{#3}}$
$\newcommand{\lim}[2]{\rawOlim{#1}{#2}{lim}}$
$\newcommand{\uplim}[2]{\rawOlim{#1}{#2}{\upline{lim}}}$
$\newcommand{\dnlim}[2]{\rawOlim{#1}{#2}{\dnline{lim}}}$
$\newcommand{\norm}[1]{\left \lVert #1 \right \rVert}$
$\newcommand{\ord}[1]{\operatorname{ord}(#1)}$
$\newcommand{\ans}[1]{\textbf{Ответ}: #1.}$
$\renewcommand{\gcd}{\text{НОД}}$
$\newcommand{\lcm}{\text{НОК}}$
$\newcommand{\proj}[2]{\text{пр.}_{#1}{#2}}$
$\newcommand{\U}[2]{U_{#1}(#2)}$
<!-- Macros: end -->  

# Информатика  

```{contents} Содержание  
---  
depth: 2  
```  

Балловая Ирина Филлиповна  
Доцент кафедры 12  

16 лекций, кажд мес-два 3-х часовые лабы  

## Литература  

- [Кормен Т.Х. и др - Алгоритмы: построение и анализ 3-е изд](https://docs.google.com/gview?url=https://mephi-tex.rtfd.io/ru/latest/_static/literature/АЛГОРИТМЫ_ПОСТРОЕНИЕ_И_АНАЛИЗ.pdf)  
- [Керниган Б.У. Ритчи Д.М. - Язык программирования С](https://docs.google.com/gview?url=https://mephi-tex.rtfd.io/ru/latest/_static/literature/T_Kormen_Ch_Leyzerson_R_Rivest_K_Shtayn_Algo.pdf)  <!-- Brian_Kernighan_Dennis_Ritchie_The_C_Programming_Language_RU.pdf) -->  
- [Шилдт Г.С. - полное руководство, классические издание](https://docs.google.com/gview?url=https://mephi-tex.rtfd.io/ru/latest/_static/literature/c_polnoerukovodstvo.pdf)  
- [Робачевский А.М. Немнюгин С.А. Стесик О.Л. - Операционная система UNIX -2-е издание](https://docs.google.com/gview?url=https://mephi-tex.rtfd.io/ru/latest/_static/literature/OS_UNIX_RUS.pdf)  <!-- Робачевский_Немнюгин_Стесик__Операционная_система_UNIX.pdf -->  
- [Вавренюк А.Б., Кутепов С.В. - Операционные система. Основы UNIX. Учебное пособие](https://docs.google.com/gview?url=https://mephi-tex.rtfd.io/ru/latest/_static/literature/операционные_систеиы_основы_UNIX_А_Б_Вавренюк.pdf)  
- [Вирт Н. - Алгоритмы и структуры данных. Новая версия для Оберон + CD / Перевод с англ](https://docs.google.com/gview?url=https://mephi-tex.rtfd.io/ru/latest/_static/literature/Никлаус_Вирт_Алгоритмы_и_структуры_данных_Новая_версия_для_Оберона_CD.pdf)  
- http://bigor.bmstu.ru/?cnt/?doc=OP2/OP_T.cou  
- [(доп) Д. Кнут том 1-3 - Искусство программирования](https://docs.google.com/gview?url=https://mephi-tex.rtfd.io/ru/latest/_static/literature/Knut_D_Iskusstvo_Programmirovania_Tom_1_3-E.pdf)  

## ЛЕК 1  

Надо научиться:  
- Анализировать формулировку задачи  
- Определить типы данных для решение задачи на компьютере  
- Разрабатывать алгоритм решения поставленной задачи  
- Разрабатывать программу на языке программирования в соответствии с созданным аллгоритмом  
- Отлаживать решение задачи на достаточном количестве тестов  
- Получать правильное решение задачи  
- Изучатб язык Си и правила работы в операционной среде Linux  

Программа - записанная на языке, понятном для компьютеру, последовательность действий для получения конкретного результата  
Алгоритм + структура данных (Орпеледение по Никлаусу Вирту) = программа  

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

Алгоритм:  

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

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

## СЕМ 1  

### Элементы схемы  

```{mermaid}  
flowchart LR;  
	A[дейстие, x=5];  
	B{условие, x!=0};  
	C{{цикл, i=1, n}};  
	D[[предопределённый процесс, имя]];  
	E((коннектор));  
	F([конец]);  
	G[/ввод/вывод/];  
```  

Правила соединения элементов:  
1) все блоки имеют координаты  
2) координаты по горизонтали - цифры  
3) координаты по вертикали - буквы  

```{mermaid}  
flowchart TD;  
	a[ ];  
	b[ ];  
	c(( ));  
	d[ ];  
	start([ ]) --> a --> b --> c --> d --> en([ ]);  
```  

### Цикл "пока"  

```{mermaid}  
flowchart LR;  
	Start([Start]);  
	End([End]);  
	Q{?};  
	B[S];  
	C[/ /];  
	Start --> Q;  
	Q --> B;  
	B --> Start;  
	Q --> C;  
	C --> End;  
```  

```c  
while P do {  
	S1;  
	S2  
}  
```  
### Цикл "до"  

```{mermaid}  
flowchart LR;  
	Start([Start]);  
	End([End]);  
	Start --> S;  
	S[S];  
	P{P};  
	S --> P;  
	P --> Start;  
	P -->|True| End;  
```  

```c  
do {  
	S1;  
	S2  
} while P  
```  

### Алгоритмизация операция с целимыми числами  
Число в любой системе счисления - некий многочлен  
$X = a_mp^m + a_{m-1}p^{m-1} + \dots + a_0p^0 + a_{-1}p^{-1} + \dots + a_{m-n+1}p^{m-n+1}$  
$p$ - основание системы счисления  
$m$ - наивысшая степень основании системы счисления в записи числа  
$n$ - количество разрядов в записи числа  

$\underline{4743}$  
$m=3$  
$0, \dots, 9$  

$395,76 = 3\cdot10^2+9\cdot10^1+5\cdot10^0+7\cdot10^{-1}+6\cdot10^{-2}$  

$$x = \sum^{n-1}_{i=0}a_ip^i$$  
$$x = \sum^{0}_{i=n-1}a_ip^i =$$  
$395 \rightarrow 593$  
$3\cdot10^2+9\cdot10^1+5\cdot10^0 = 5\cdot10^2+9\cdot10^1+3\cdot10^0$  

Задача: из произвольного целого числа получить палиндромное  
$48$  
$48 + 84 = 132$  
$132 + 231 = 363$  

```{mermaid}  
flowchart TD;  
	Start([Start]);  
	End([End]);  
	N[/n/];  
	Init[f=0, t=n];  
	Start --> N;  
	N --> Init;  
	Q{f == 0};  
	Init --> Q;  
	F[f=1];  
	Q --> |False|F;  
	F --> End;  
	init2[a=t, p=0];  
	q2{a!=0};  
	init2-->q2;  
	B[p=p*10];  
	b2[k=a%10];  
	q2 --> |True|B;  
	B-->b2;  
	Q-->|True|init2;  
	b3[p=p+k];  
	b2-->b3;  
	b4[a=a/10];  
	b3-->b4;  
	b4-->q2;  
	q3{p==t};  
	q2-->|False|q3;  
	b5[f=1];  
	b6[t=t+p];  
	q3-->|True|b5;  
	q3-->|False|b6;  
	u(( ));  
	b5 & b6 -->u;  
	u-->Q;  
```  

```c  
#include <studio.h>  

int main() {  
	int t, f = 0, p;  
	int a, n;  

	printf("Введите число n\n");  
	scanf("%d", &n);  
	t = n;  

	while (f == 0) {  
		a = t;  
		p = 0;  
		while (a != 0) {  
			p = p * 10;  
			k = a % 10;  
			p = p + k;  
			a = a / 10;  
		}  
		if (a != k) {  
			t = t + p;  
		} else {  
			f = 1;  
		}  
	}  

	printf("результат\n");  
	printf("%10d %10d", n, p);  

	return 0;  
}  
```  

```{mermaid}  
flowchart TD;  
	i([inv]) --> b1[a=t, p=0] --> q1{a!=0};  
	en([end]);  
	q1 --> |False| en;  
	q1 --> |True| b2[p=p*10] --> b3[k=a%10] --> b4[p=p+k] --> b5[a=a/10] --> q1;  

	m([alg]) --> b7[/begin/] --> b8[f=0, i=0] --> q2{f==0};  
	q2 --> b9[[inv n]] --> q3{p==0};  
	q3 --> b10[f=0] & b11[p=p+b];  
```  

```c  
#inlcude <studio.h>  
int inv( int n ) {  
	int t, f = 0, p;  
	int a;  

	t = n;  
	while (f == 0) {  
		a = t;  
		p = 0;  
		int k;  
		while (a != 0) {  
			p = p * 10;  
			k = a % 10;  
			p = p + k;  
			a = a / 10;  
		}  
		if (p != t) {  
			t = t + p;  
		} else {  
			f = 1;  
		}  
	}  
	return p;  
}  

int main() {  
	int aa = 1, n;  
	printf("Начало!\n");  

	printf("Число ...");  
	scanf("%d", &n);  

	int nepal = inv(n);  
	printf("...");  
	return 0;  
}  
```  

ДЗ:  
- Из заданного числа получить число состоящее только из четных цифр числа  
- Из цифр числа составить минимальное число  

## ЛЕК 20/09/22  

Данные для заходи на сервер  
samos.dozen.mephi.ru  
@DozenBot  

C  
- простой  
- быстрый  
- контролит память  
- сложный в разработке  
- недостаточная стандартизация  

Pascal  
- компилируемый  
- строгая статическая типизация  
- простой, понятный c-c  
- проиграл (лох, как cobol / fortran)  

Python  
- удобный  
- популярный  
- дофига библотек  
- динамический  
- не прыткий  
- не субер простой  
- не низкоуровненый  

Java  
- есть  


уровень япа  
- низкий (ассемблер, машинный код)  
- высокий (с, с++, жава)  

способ реализации  
- компилируемые (с, с++, раст)  
- интерпретируемые (питон, луа, жс)  
- встраиваемые (DSL)  

по системе типизации  
- со статический (с, с++, жава)  
- с динамической (питон, луа, жс)  

```{mermaid}  
flowchart TB  
	a[заголовочные\nфайлы *.h] & b[исходные\nфайлы *.c] --> k[компилятор С] --> o[объектые файлы] --> kk[компоновщик] --> e[исполняемый файл];  
	k --> d[диангостическая информация];  
	kk --> dd[диагностическая информация];  
	bb[библиотеки *.a, *.so] --> kk;  
```  

```  
тип имя_функции(тип параментпараметр_1...)  
{  
	предложение_описания_типа_1  
	...  
	предложение_языка_1  
	...  
	return [выражение];  
}  
```  

`;` - конец предложения  

Программа:  
- описание данных  
	- базовые типы  
		- char  
		- int  
		- float  
		- double  
	- модификаторы  
		- длинны  
			- short  
			- long  
			- long long  
		- знака  
			- signed  
			- unsigned  
- описание алгоритма  
	- предложение  
		- пустое  
		- условное  
		- составное  
		- переключатель  
		- итерационные циклы  
		- параметрический цикл  
		- объявление данных  

## СЕМ 22.09.22  

```{mermaid}  
flowchart TB  
	n[начало] --> b[/ввод x,n/] --> c(["S=exp1(x,n)"]) --> d[/вывод S/] --> e[конец];  
	ss("exp(x,n)") --> dd[y=x*x] --> ee["i=1;i\leqn;i++"] --> hh(return S);  
	ee --> ff[t=-ty/i] --> gg[S+=t] --> ee;  
```  


```c  
#include <stdio.h>  
#include <math.h>  

double exp1(double x, int n) {  
	double S = 1, t=1, y=x*x;  
	for (int i = 1; i \leq n; i++) {  
		t = t*(y/i);  
		s+=t;  
	}  
	return S;  
}  

int main() {  
	double x = 0;  
	int n = 0;  
	scanf("%ff", &x);  
	scanf("%d", &n);  
	double S = exp1(x, n);  
	double S1 = exp(-x*x);  
	printf("S: %f, S1 %f", S, S1);  
	return 0;  
}  
```  
## СЕМ 13.10.22  

```c  
#include <stdlib.h>  
#include <time.h>  

int * array_input(int * len) {  
    scanf("%d", len);  
    int * a = (int * ) malloc( * len * sizeof(int));  
    if (!a)  
        return NULL;  
    for (int i = 0; i < * len; i++) {  
        scanf("%d", & a[i]); // &a[i] = a + i  
    }  
    return a;  
}  

void array_print(const int * a, int len) {  
    for (int i = 0; i < len; i++) {  
        printf("%d ", a[i]); // a[i] = *(a+i)  
    }  
    printf("\n");  
}  

void array_remove_dup(int * data, int * len) {  
    for (int i = 0; i < * len - 1; i++) {  
        for (int j = i + 1; j < * len; j++) {  
            if (data[i] == data[j]) {  
                for (int k = j; k < * len - 1; k++) {  
                    data[k] = data[k + 1];  
                }  
                --( * len);  
                --i;  
            }  
        }  
    }  
}  

int main() {  
    int len = 0;  
    int * array = array_input( & len);  
    array_print(array, len);  
    clock_t start = 0, end = 0;  
    start = clock();  
    array_remove_dup(array, & len);  
    end = clock();  
    array_print(array, len);  
    printf("%lf\n", (double)(end - start) / CLOCKS_PER_SEC);  
    free(array);  
    return 0;  
}  

```