Форум программистов, компьютерный форум CyberForum.ru

Подскажите литературу где встречаются данные темы - C++

Восстановить пароль Регистрация
 
Ruska95
0 / 0 / 0
Регистрация: 12.11.2012
Сообщений: 5
02.01.2013, 14:03     Подскажите литературу где встречаются данные темы #1
вот данные темы.нужно найти лекции или хотя бы краткие конспекты,хоть что-нибудь
Кликните здесь для просмотра всего текста
1. Основные понятия информатики. Структура информатики.
2. Языки программирования. Основные понятия ЯП. Архитектура фон Неймана. Абстрактный и машинно-зависимый вычислители.
3. Грамматика ЯП. Синтаксис, семантика, прагматика ЯП. Методы определения формальной семантики: операционная, детонационная, пропозициональная.
4. Теория алгоритмов. Определение. Свойства алгоритмов. Требования к алгоритмам. Способы задания алгоритмов. Основные направления теории алгоритмов. Стандартные программные контексты. Модели вычислений. Машина Тьюринга. Основные компоненты. Тезис Чёрча-Тьюринга. Теория рекурсивных функций. ПРФ. ЧРФ. Оператор примитивной рекурсии. Оператор суперпозиции. Нормальные алгоритмы Маркова.
Теория сложности вычислений. Алгоритмическая разрешимость. Асимтотическая сложность. Асимтотические обозначения. Классы сложности. NP, P.
5. Парадигмы программирования. Структурное программирование. Операторный метод. Методология декомпозиции.
6. Алгоритмы поиска. Линейный поиск. Двоичный поиск. Анализ алгоритмов.
7. Базовые типы данных С++. Выражения, операторы С++
8. Линейная управляющая конструкция С++
9. Логические выражения.
10. Управляющие конструкции выбора С++
11. Функции. Структурная парадигма С++
12. Стандартные программные контексты
13. Одномерные массивы. Операции с массивами С++
14. Многомерные массивы С++
15. Алгоритмы поиска в массивах
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.01.2013, 14:03     Подскажите литературу где встречаются данные темы
Посмотрите здесь:

C++ Подскажите литературу где хорошо расписаны способы работы с типом string
Подскажите литературу... C++
Подскажите литературу C++
C++ Подскажите литературу
Подскажите литературу C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
m1Rr0r
 Аватар для m1Rr0r
247 / 230 / 15
Регистрация: 05.02.2010
Сообщений: 3,213
Завершенные тесты: 2
02.01.2013, 14:07     Подскажите литературу где встречаются данные темы #2
Цитата Сообщение от Ruska95 Посмотреть сообщение
вот данные темы.нужно найти лекции или хотя бы краткие конспекты,хоть что-нибудь
Ruska95, телепаты в отпуске =)
Ruska95
0 / 0 / 0
Регистрация: 12.11.2012
Сообщений: 5
02.01.2013, 14:09  [ТС]     Подскажите литературу где встречаются данные темы #3
увы,первый раз не вставился документ,счас все в норме)
Issues
429 / 364 / 37
Регистрация: 06.08.2012
Сообщений: 961
02.01.2013, 18:21     Подскажите литературу где встречаются данные темы #4
Ruska95, в гугле легко найти ответы на ваши вопросы.
David Sylva
 Аватар для David Sylva
1281 / 943 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
02.01.2013, 18:27     Подскажите литературу где встречаются данные темы #5
Ruska95 Соглашусь с SeregaC++ в гугле будет легче найти ответы, чем искать конкретные книги и искать в книгах конкретные разделы. Не забивайте себе голову, просто ищите каждый вопрос в гугле.
asidorchenko
379 / 205 / 25
Регистрация: 09.04.2012
Сообщений: 635
03.01.2013, 09:49     Подскажите литературу где встречаются данные темы #6
7. Базовые типы данных С++. Выражения, операторы С++
Существует два вида типов: фундаментальные типы и составные типы. Типы описывают объекты, ссылки или функции. Арифметические типы, типы перечисления, типы указания, типы указания на члены, std::nullptr_ ( нулевой указатель) называются скалярными типами. Есть пять стандартных знаковых типа: signed char, short int, int, long int, long long int. Есть соответствующие беззнаковые типы: unsigned char, unsigned short int, unsigned int, unsigned long int, unsigned long long int. В беззнаковом типе все биты представляют число. Есть три типа с плавающей точкой: float, double и long double. void тип имеет пустое множество значений. Составные типы: массивы из объектов заданного типа, функции, указатели, ссылки, классы, объединения, перечисления.

Выражение - это последовательность операторов и операндов, которая определяет вычисление.

Операторы в порядке убывания приоритета:
:: ( область видимости)
. ( селектор компонента класса)
-> ( доступ к члену класса по указателю)
[] ( индексирование )
() (вызов функции)
++ (инкремент постфиксный)
-- (декремент постфиксный)
sizeof (размер объекта. размер типа.)
++ (префиксный инкремент)
-- (префиксный декремент)
~ (побитовое НЕ)
! (логическое НЕ)
- ( унарный минус)
+ ( унарный плюс)
* (разыменование)
& ( адрес)
() (приведение типа)
new ( выделение типа)
new[] ( выделение памяти под массив)
delete ( освобождение памяти)
delete[] (освобождение памяти из-зпод массива)
->* (разыменование указателя на компонент класса по указателю)
.* ( разыменование указателя на компонент класса)
* ( умножение)
/ (деление)
% ( деление по модулю)
+ ( сложение)
- ( вычитание)
<< ( сдвиг влево)
>> ( сдвиг вправо)
< ( меньше)
<= ( меньше или равно)
> ( больше)
>= (больше или равно)
== (равно)
!= ( не равно)
& ( побитовое И)
^ (побитовое ИСКЛЮЧАЮЩЕЕ ИЛИ)
| (побитовое ИЛИ)
&& (логическое И)
|| (логическое ИЛИ)
?: ( условная операция)
= (присваивание)
*= /= %= += -= <<= >>= &= |= ^= (составное присваивание)
, (запятая)

Литература:
1. В.В.Лаптев - C++ Объектно-ориентированное программирование
2. Стандарт языка C++ ( working draft, standard for programming language C++)

Добавлено через 10 минут
9. Логические выражения.
Логическое И - если хоть один из элементов выражение ложен, то ложно все выражение.
Обозначается &&
Таблица истинности для двух операндов:
операнд1 операнд2 результат
1 1 1
1 0 0
0 1 0
0 0 0
где 1 обозначает ИСТИНА, 0 обозначает ЛОЖЬ

Логическое ИЛИ - есть хоть один из элементов выражения истинен, то истинно все выражение.
Обозначается ||
Таблица истинности для двух операндов:
операнд1 операнд2 результат
1 1 1
1 0 1
0 1 1
0 0 0

Логическое НЕ
Обозначается !
Таблица истинности:
операнд результат
1 0
0 1
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11836 / 6815 / 770
Регистрация: 27.09.2012
Сообщений: 16,904
Записей в блоге: 2
Завершенные тесты: 1
03.01.2013, 10:02     Подскажите литературу где встречаются данные темы #7
Забыли про "alternative tokens"
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<%      {
%>      }
<:      [
:>      ]
%:      #
%:%:    ##
&&      and
bitor   |
or      ||
xor     ^
compl   ~
bitand  &
and_eq  &=
or_eq   |=
xor_eq  ^=
not     !
not_eq  !=
и про "trigraph sequences"
C++
1
2
3
4
5
6
7
8
9
??=     #
??/     \
??'     ^
??(     [
??)     ]
??!     |
??<     {
??>     }
??-     ~
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2013, 18:51     Подскажите литературу где встречаются данные темы
Еще ссылки по теме:

C++ Подскажите литературу
C++ Подскажите литературу по C++
Подскажите литературу, где основной уклон - на работу с потоками C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
asidorchenko
379 / 205 / 25
Регистрация: 09.04.2012
Сообщений: 635
05.01.2013, 18:51     Подскажите литературу где встречаются данные темы #8
Машина Тьюринга это кортеж из 7 элементов http://www.cyberforum.ru/cgi-bin/latex.cgi?<Q,\Gamma,b,\Sigma,\delta {q}_{0},F>, где
http://www.cyberforum.ru/cgi-bin/latex.cgi?Q - конечное непустое множество состояний
http://www.cyberforum.ru/cgi-bin/latex.cgi?\Gamma - конечный непустой набор символов, называемых алфавитом
http://www.cyberforum.ru/cgi-bin/latex.cgi?b\in \Gamma - пустой символ ( единственный символ, который может быть на ленте после любого шага процесса вычисления)
http://www.cyberforum.ru/cgi-bin/latex.cgi?\Sigma \subseteq \Gamma \ {http://www.cyberforum.ru/cgi-bin/latex.cgi?b} - набор входных символов
http://www.cyberforum.ru/cgi-bin/latex.cgi?{q}_{0}\in Q - начальное состояние
http://www.cyberforum.ru/cgi-bin/latex.cgi?F\subseteq  Q - множество конечных ( или допускающих) состояний
http://www.cyberforum.ru/cgi-bin/latex.cgi?\delta : Q \ http://www.cyberforum.ru/cgi-bin/latex.cgi?F x http://www.cyberforum.ru/cgi-bin/latex.cgi?\Gamma \rightarrow Q x http://www.cyberforum.ru/cgi-bin/latex.cgi?\Gamma x {http://www.cyberforum.ru/cgi-bin/latex.cgi?L, R} - функция переходов, где http://www.cyberforum.ru/cgi-bin/latex.cgi?L - левый сдвиг, http://www.cyberforum.ru/cgi-bin/latex.cgi?R - правый сдвиг
То, что оперирует в соответствии с данной спецификацией называется машиной Тьюринга. Определение в соответствии с [Хопкрофт, Ульман, 1979, стр 148].

Неформально это машина, которая оперирует лентой, на которой находятся символы, которые машина может считывать и записывать по одному за раз, используя головку ленты.
[img] http://upload.wikimedia.org/wikipedi...ine_2b.svg.png [/img]
Элементы машины:
1. лента, разбитая на ячейки, располагающиеся рядом друг с другом. Каждая ячейка содержит символ из какого-то конечного алфавита. Алфавит содержит специальный пустой символ. Лента расширяема налево или направо настолько, насколько требуется для вычисления. В ячейках, в которых еще не было ничего записано, находится пустой символ. В некоторых случаях левый конец ленты маркируется специальным символом, а машина расширяется направо.
2. головка двигается по ленте налево или направо и записывает символы в ячейки или считывает их оттуда.
3. регистр состояния, в котором находится состояние машины Тьюринга. В начальном состоянии машины регистр состояния инициализируется
4. конечная таблица инструкций вида http://www.cyberforum.ru/cgi-bin/latex.cgi?{q}_{i}{a}_{j}\rightarrow {q}_{i1}{a}_{j1}{d}_{k}, каждая из которых обозначает, что при нахождении машины в состоянии http://www.cyberforum.ru/cgi-bin/latex.cgi?{q}_{i} и из ячейки считан символ http://www.cyberforum.ru/cgi-bin/latex.cgi?{a}_{j} машина должна выполнить следующую последовательность операций
- стереть или записать символ ( заменить http://www.cyberforum.ru/cgi-bin/latex.cgi?{a}_{j} на http://www.cyberforum.ru/cgi-bin/latex.cgi?{a}_{j1}
- сдвинуть головку в соответствии с http://www.cyberforum.ru/cgi-bin/latex.cgi?{d}_{k}, которое может принмиать значения L для сдвига влево и R для сдвига вправо
- перейти в состояние http://www.cyberforum.ru/cgi-bin/latex.cgi?{q}_{i1}

Кратко, машина Тьюринга имитирует работу CPU компьютера.

Литература:
- http://en.wikipedia.org/wiki/Turing_machine

Добавлено через 14 минут
Тезис Чёрча-Тьюринга в теории вычислений это гипотеза о природе функций, которые вычислимы эффективно, или точнее функции которые вычислимы алгоритмически. Тезис Чёрча-Тьюринга утверждает, что функция вычислима алгоритмически, если она вычислима на машине Тьюринга.

Американский математик Алонсо Чёрч создал метод определения функций, называемый лямбда-исчислением. Он совместно с Стивеном Клини и Джоном Россером создал формальное определение класса функций, которые могут быть вычислены рекурсивно.

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

Тезис Чёрча-Тьюринга не может быть формально доказан.

"Эффективно вычислимо" означает, что каждый шаг метода может быть в точности предопределен и даст ответ за конечное число шагов. Другими словами это означает что метод осуществляется на машине Тьюринга или на другом эквивалентном механическом устройстве.

Литература:
- http://en.wikipedia.org/wiki/Church%...3Turing_thesis
- http://en.wikipedia.org/wiki/Lambda_calculus

Добавлено через 36 минут
Формальная грамматика (согласно Хомскому) это кортеж из 4 элементов <N, \Sigma, P, S>, где
N - конечный набор нетерминальных символов
http://www.cyberforum.ru/cgi-bin/latex.cgi?\Sigma - конечный набор терминальных символов, не пересекающийся с N
P - конечный набор правил производства http://www.cyberforum.ru/cgi-bin/latex.cgi?(\Sigma \bigcup N)*N(\Sigma \bigcup N)*\rightarrow (\Sigma \bigcup N)* где * - оператор "звездочка Клини", http://www.cyberforum.ru/cgi-bin/latex.cgi?\bigcup - "объединение множеств"
S\in N - начальный символ

Звездочка Клини
Пусть задано множество http://www.cyberforum.ru/cgi-bin/latex.cgi?V, определяемое следующим образом
http://www.cyberforum.ru/cgi-bin/latex.cgi?{V}_{0}=\begin{Bmatrix}\varepsilon \end{Bmatrix}
http://www.cyberforum.ru/cgi-bin/latex.cgi?{V}_{1}=V
и рекурсивно определено множество
http://www.cyberforum.ru/cgi-bin/latex.cgi?{V}_{i+1}=\begin{Bmatrix}wv \mid w\in {V}_{i}   v\in V\end{Bmatrix}, i>0
Тогда оператор "звездочка Клини" определяется следующим образом:
http://www.cyberforum.ru/cgi-bin/latex.cgi?V* = \bigcup_{i\in N}^{}{V}_{i}=\begin{Bmatrix}\varepsilon \end{Bmatrix}\bigcup V\bigcup {V}_{2}\bigcup {V}_{3}\bigcup {V}_{4}\bigcup...

Пример применения звездочки Клини:
{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}.

Литература:
- http://en.wikipedia.org/wiki/Formal_grammar
- http://en.wikipedia.org/wiki/Kleene_star

Добавлено через 1 час 58 минут
Термин "Архитектура фон Неймана" берет свое начало от работы 1945 года фон Неймана и других "Первый черновик доклада об EDVAC", которая описывает дизайн архитектуры электронного цифрового компьютера. Его частями должны являться:
- процессор, состоящий из арифметическо-логического устройства и регистров
- управляющий автомат, включающий регистр инструкции и счётчик команд
- память для хранения данных и инструкций
- внешнее устройство для хранения данных
- механизмы ввода-вывода.

По другому, это означало компьютер с хранимой в нем программой, в котором получение данных и инструкции не может происходить в одно и то же время, так как шина единая. Это ограничение получило название "бутылочное горлышко фон Неймана" и оно снижает производительность системы.

Современная архитектура - Гарвардская, в которой разделены наборы адресов и шин для памяти и инструкций.

Литература:
- http://en.wikipedia.org/wiki/Von_Neumann_architecture

Язык программирования - искусственный язык для передачи инструкций машине.

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

У ЯП две части - синтаксис("форма") и семантика("значение").

Некоторые языки определяются спомощью спецификаций.
Например:
- стандарт языка С : http://www.open-std.org/jtc1/sc22/wg...docs/n1124.pdf
- стандарт языка С++ : open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3376.pdf

Литература:
- http://en.wikipedia.org/wiki/Programming_language
- http://en.wikipedia.org/wiki/Lexical_grammar
- http://en.wikipedia.org/wiki/Abstract_syntax_tree
- http://en.wikipedia.org/wiki/Parsing
- http://en.wikipedia.org/wiki/Visual_...mming_language
- http://en.wikipedia.org/wiki/Context-free_grammar


Синтаксис ЯП - это набор правил, определяющих какие комбинации символов являются корректными. Есть текстовые и визуальные языки программирования. Лексическая структура может быть определена с помощью регулярных выражений. Синтаксическая структура может быть записана в форме Бэкуса-Наура.

Литература:
- http://en.wikipedia.org/wiki/Syntax_...ming_languages)
- http://en.wikipedia.org/wiki/Regular_expression
- http://en.wikipedia.org/wiki/Backus%E2%80%93Naur_Form

Семантика определяет значение синтаксически корректных строк, определенных конкретным ЯП.
Детонационная семантика, когда каждая фраза языка интерпретируется как детонация, т.е концептуальное значение, которое может быть представлено абстрактно. Подобные детонации могут быть математическими объектами и описываться математической нотацией.
Операционная семантика, когда выполнение языка описывается прямо (без трансляции). Это похоже на интерпретирование, хотя язык реализации интерпретатора является математическим формальным языком. Семантика может определять абстрактную машину, которая дает значение фразам описывая переходы, которые осуществляются над состояниями машины.
Пропозициональная семантика, когда значение фразы определяется применением к ним логических аксиом. Нет разделения между значением фразы и логчисекой формулой, которая она описывается.

- http://en.wikipedia.org/wiki/Semanti...ming_languages
- http://en.wikipedia.org/wiki/Denotational_semantics
- http://en.wikipedia.org/wiki/Operational_semantics
- http://en.wikipedia.org/wiki/Axiomatic_semantics

Добавлено через 4 часа 10 минут
13-14 вопросы.

Одномерный массив это n-мерный вектор. Объекты реального мира описываются множествами векторов (двухмерный массив). Вектор задает координаты точки в пространстве (скаляры) или отношение между точками. Задание с помощью векторов позволяет понять, как объекты ориентированы по отношению друг к другу(например, вычислением скалярного или векторного произведения). Вычисление скалярного произведение это определение угла между векторами. Преобразованием координат векторов задаются перемещение, вращение, масштабирование объектов. Реальный мир представляет векторное пространство. Объем занятый газом, жидкостью это векторное пространство. Газодинамика, динамика жидкости. Интегрирование это вычисление площадей, объемов.

Двухмерный массив - это матрица размерности mxn. Матрица это набор векторов. Матрицами описываются технические и реальные объекты реального мира и пространство. Преобразование матриц описывает изменение объекта реального мира. Ландшафт описывается матрицами (создается карта высот).

Двухмерный массив это пространство памяти процесса Windows (виртуальное адресное пространство) при представлении в ядре. Это разреженная матрица. Первая размерность массива - это страница, вторая страница матрицы - это данные страницы (т.н. страничная организация памяти операционной системы)

Изображение, фотография могут быть представлена битовым массивом ( битовой картой). Ряды Фурье используются для преобразования сигналов ( при передачи по линиям связи как то ADSL, GPON, Ethernet и т.п.)

Поиск пересечений объектов это решение систем линейных уравнений.

Треугольная матрица это граф (набор вершин и ребер). Графы используются для поиска пути, моделирования ИИ. Поиск пути в графе описывается рекурсивными функциями. Дерево представляет собой частный случай графа. Отсечение многоугольников.

Файл может представлять массив структур. База данных это набор массивов структур.

Массив может хранить мета-данные другого массива. Таблица переходов грамматики ЯП это многомерный массив. Массив это множество. Ассоциативный массив - хэш.

Статическое выделение памяти под массив. Массив хранится в exe и в образе exe в памяти. В exe создаются ячейки для хранения значений элементов массива (и переменных). После компиляции наборы байтов в исполняемом файле представляют собой место для хранения значения переменной. При исполнении программы в эти ячейки записываются значения. В exe предусмотрена секция .data для записи значений переменных и .rdata для записи констант.

Динамическое выделение памяти под массив. Массив хранится в оперативной памяти. Оперативная память представляет из себя разреженную матрицу. Операция над оперативной памятью это операция над разреженной матрицей.

Выделение памяти под динамический массив осуществляется:
- функциями malloc / free в языке C ( язык процедурно(структурно) ориентирован)
- операторами new / delete в языке C++ ( язык объектно-ориентирован)

Размерность массива может быть задана явно и неявно. Явное задание осуществляется константами, указывающими размерности. Неявное задание осуществляется значениями элементов массива.

Пример динамического задания матрицы:
C++
1
2
3
4
int** m;
m = new int*[5];
for(int i=0;i<5;i++)
m[i] = new int[4];
Пример динамического задания вектора
C++
1
2
int* m;
m = new int[10];
Добавлено через 36 минут
В соответствии с классификацией Хомского существует 4 вида формальных грамматик:
1. регулярные (выполняется конечным автоматом)
2. контекстно-свободные
3. контекстно-зависимые
4. неограниченные (выполяются машиной Тьюринга)
http://ru.wikipedia.org/wiki/Иерархия Хомского

Алгоритм - конечный набор инструкций для вычисления функции. После входа в начальное состояние вычисление осуществляется инструкциями, которые после перехода через конечное множество состояний производят данные вывода, завершая выполнение в конечнои состоянии.
http://en.wikipedia.org/wiki/Algorithm
http://en.wikipedia.org/wiki/Analysis_of_algorithms

Нотация О большое используется для описания предельного поведения функции. Алгоритмы классифицируются в соответствии с данной нотацией по изменению времени выполнения в зависимости от объема входных данных.
http://en.wikipedia.org/wiki/Big_O_notation

Деление алгоритмов по времени выполнения:
- константное O(const)
- линейное O(n)
- логарифмическое O(log n)
- полиномиальное 2^O(log n)
- экспоненциальное 2^poly(n)
http://en.wikipedia.org/wiki/Time_complexity

Р класс при выполнении алгоритма на машине Тьюринга за полиномиальное время
http://en.wikipedia.org/wiki/P_(complexity)

NP класс если неизвестно выполняется ли алгоритм за полиномиальное время
http://en.wikipedia.org/wiki/NP_(complexity)
Yandex
Объявления
05.01.2013, 18:51     Подскажите литературу где встречаются данные темы
Ответ Создать тему
Опции темы

Текущее время: 12:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru